Compressed sensing and dynamic mode decomposition

Steven L. Brunton; Joshua L.  Proctor; Jonathan H.  Tu; J. Nathan Kutz

doi:10.3934/jcd.2015002

Article Contents

2015, Volume 2, Issue 2: 165-191. Doi: 10.3934/jcd.2015002 open access

This issue Previous Article A posteriori error bounds for two point boundary value problems: A green's function approach Next Article Variational integrators for mechanical control systems with symmetries

Compressed sensing and dynamic mode decomposition

1.
Dept. of Applied Mathematics, University of Washington, Seattle, WA 98195
2.
Institute for Disease Modeling, Intellectual Ventures Laboratory, Bellevue, WA 98004
3.
Department of Electrical Engineering and Computer Science, University of California, Berkeley, Berkeley, CA 94720

Received: December 2013

Revised: August 2015

Published: June 2015

Abstract / Introduction Related Papers Cited by

Abstract

This work develops compressed sensing strategies for computing the dynamic mode decomposition (DMD) from heavily subsampled or compressed data. The resulting DMD eigenvalues are equal to DMD eigenvalues from the full-state data. It is then possible to reconstruct full-state DMD eigenvectors using $\ell_1$-minimization or greedy algorithms. If full-state snapshots are available, it may be computationally beneficial to compress the data, compute DMD on the compressed data, and then reconstruct full-state modes by applying the compressed DMD transforms to full-state snapshots.
These results rely on a number of theoretical advances. First, we establish connections between DMD on full-state and compressed data. Next, we demonstrate the invariance of the DMD algorithm to left and right unitary transformations. When data and modes are sparse in some transform basis, we show a similar invariance of DMD to measurement matrices that satisfy the restricted isometry property from compressed sensing. We demonstrate the success of this architecture on two model systems. In the first example, we construct a spatial signal from a sparse vector of Fourier coefficients with a linear dynamical system driving the coefficients. In the second example, we consider the double gyre flow field, which is a model for chaotic mixing in the ocean.

A video abstract of this work may be found at: http://youtu.be/4tLSq_PEFms.

Keywords:

Mathematics Subject Classification: Primary: 65P99, 37M99, 37M10, 68P30, 94A99; Secondary: 76M99, 90C25, 94A08.

Citation:

Related Papers

Cited by

References

[1]	R. Abraham, J. E. Marsden and T. Ratiu, Manifolds, Tensor Analysis, and Applications, volume 75 of Applied Mathematical Sciences, Springer-Verlag, 1988.doi: 10.1007/978-1-4612-1029-0.
[2]	E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammerling and A. McKenney, et al, LAPACK Users' Guide, volume 9. Siam, 1999.
[3]	S. Bagheri, Effects of small noise on the DMD/Koopman spectrum, Bulletin Am. Phys. Soc., 58 (2013), p230.
[4]	S. Bagheri, Koopman-mode decomposition of the cylinder wake, Journal of Fluid Mechanics, 726 (2013), 596-623.doi: 10.1017/jfm.2013.249.
[5]	Z. Bai, T. Wimalajeewa, Z. Berger, G. Wang, M. Glauser and P. K. Varshney, Physics Based Compressive Sensing Approach Applied to Airfoil Data Collection and Analysis, AIAA Paper 2013-0772, 51st Aerospace Sciences Meeting, January 2013.
[6]	Z. Bai, T. Wimalajeewa, Z. Berger, G. Wang, M. Glauser and P. K. Varshney, Low-dimensional approach for reconstruction of airfoil data via compressive sensing, AIAA Journal, 53 (2015), 920-933.doi: 10.2514/1.J053287.
[7]	R. G. Baraniuk, Compressive sensing, IEEE Signal Processing Magazine, 24 (2007), 118-120.
[8]	R. G. Baraniuk, V. Cevher, M. F. Duarte and C. Hegde, Model-based compressive sensing, IEEE Transactions on Information Theory, 56 (2010), 1982-2001.doi: 10.1109/TIT.2010.2040894.
[9]	G. Berkooz, P. Holmes and J. L. Lumley, The proper orthogonal decomposition in the analysis of turbulent flows, Annual Review of Fluid Mechanics, 23 (1993), 539-575.
[10]	I. Bright, G. Lin and J. N. Kutz, Compressive sensing and machine learning strategies for characterizing the flow around a cylinder with limited pressure measurements, Physics of Fluids, 25 (2013), 127102.doi: 10.1063/1.4836815.
[11]	B. W. Brunton, S. L. Brunton, J. L. Proctor and J. N. Kutz, Optimal sensor placement and enhanced sparsity for classification, arXiv preprint arXiv:1310.4217, 2013.
[12]	B. W. Brunton, L. A. Johnson, J. G. Ojemann and J. N. Kutz, Extracting spatial-temporal coherent patterns in large-scale neural recordings using dynamic mode decomposition, Journal of Neuroscience Methods, 258 (2016), 1-15.doi: 10.1016/j.jneumeth.2015.10.010.
[13]	S. L. Brunton and B. R. Noack, Closed-loop turbulence control: Progress and challenges, Applied Mechanics Reviews, 67 (2015), 050801.doi: 10.1115/1.4031175.
[14]	S. L. Brunton, J. L. Proctor and J. N. Kutz, Discovering governing equations from data by sparse identification of nonlinear dynamical systems, Proceedings of the National Academy of Sciences, 113 (2016), 3932-3937.doi: 10.1073/pnas.1517384113.
[15]	S. L. Brunton, J. H. Tu, I. Bright and J. N. Kutz, Compressive sensing and low-rank libraries for classification of bifurcation regimes in nonlinear dynamical systems, SIAM Journal on Applied Dynamical Systems, 13 (2014), 1716-1732.doi: 10.1137/130949282.
[16]	M. Budišić, R. Mohr and I. Mezić, Applied Koopmanism a), Chaos: An Interdisciplinary Journal of Nonlinear Science, 22 (2012), 047510, 33pp.doi: 10.1063/1.4772195.
[17]	E. J. Candès, Compressive sensing, Proceedings of the International Congress of Mathematics, 3 (2006), 1433-1452.
[18]	E. J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory, 52 (2006), 489-509.doi: 10.1109/TIT.2005.862083.
[19]	E. J. Candès, J. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Communications in Pure and Applied Mathematics, 59 (2016), 1207-1223.doi: 10.1002/cpa.20124.
[20]	E. J. Candès and T. Tao, Near optimal signal recovery from random projections: Universal encoding strategies?, IEEE Transactions on Information Theory, 52 (2006), 5406-5425.doi: 10.1109/TIT.2006.885507.
[21]	E. J. Candès and M. B. Wakin, An introduction to compressive sampling, IEEE Signal Processing Magazine, pages 21-30, 2008.
[22]	K. K. Chen, J. H. Tu and C. W. Rowley, Variants of dynamic mode decomposition: Boundary condition, Koopman, and Fourier analyses, Journal of Nonlinear Science, 22 (2012), 887-915.doi: 10.1007/s00332-012-9130-9.
[23]	S. Dawson, M. Hemati, M. Williams and C. Rowley, Characterizing and correcting for the effect of sensor noise in the dynamic mode decomposition, Experiments in Fluids, 57 (2016), p42, arXiv:1507.02264.doi: 10.1007/s00348-016-2127-7.
[24]	D. L. Donoho, Compressed sensing, IEEE Transactions on Information Theory, 52 (2006), 1289-1306.doi: 10.1109/TIT.2006.871582.
[25]	J. E. Fowler, Compressive-projection principal component analysis, IEEE Transactions on Image Processing, 18 (2009), 2230-2242.doi: 10.1109/TIP.2009.2025089.
[26]	M. Gavish and D. L. Donoho, The optimal hard threshold for singular values is $4/\sqrt{3}$, IEEE Transactions on Information Theory, 60 (2014), 5040-5053.doi: 10.1109/TIT.2014.2323359.
[27]	A. C. Gilbert and P. Indyk, Sparse recovery using sparse matrices, Proceedings of the IEEE, 98 (2010), 937-947.doi: 10.1109/JPROC.2010.2045092.
[28]	A. C. Gilbert, J. Y. Park and M. B. Wakin, Sketched SVD: Recovering spectral features from compressive measurements. ArXiv e-prints, 2012.
[29]	J. Gosek and J. N. Kutz, Dynamic mode decomposition for real-time background/foreground separation in video, arXiv preprint, arXiv:1404.7592, 2014.
[30]	M. Grilli, P. J. Schmid, S. Hickel and N. A. Adams, Analysis of unsteady behaviour in shockwave turbulent boundary layer interaction, Journal of Fluid Mechanics, 700 (2012), 16-28.
[31]	F. Gueniat, L. Mathelin and L. Pastur, A dynamic mode decomposition approach for large and arbitrarily sampled systems, Physics of Fluids, 27 (2015), 025113.doi: 10.1063/1.4908073.
[32]	Maziar S Hemati and Clarence W Rowley, De-biasing the dynamic mode decomposition for applied Koopman spectral analysis, arXiv preprint, arXiv:1502.03854, 2015.
[33]	B. L. Ho and R. E. Kalman, Effective construction of linear state-variable models from input/output data, In Proceedings of the 3rd Annual Allerton Conference on Circuit and System Theory, (1965), 449-459.
[34]	P. J. Holmes, J. L. Lumley, G. Berkooz and C. W. Rowley, Turbulence, Coherent Structures, Dynamical Systems and Symmetry, Cambridge Monographs in Mechanics. Cambridge University Press, Cambridge, England, 2nd edition, 2012.doi: 10.1017/CBO9780511919701.
[35]	W. B. Johnson and J. Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, Contemporary mathematics, 26 (1984), 189-206.doi: 10.1090/conm/026/737400.
[36]	M. R. Jovanović, P. J. Schmid and J. W. Nichols, Low-rank and sparse dynamic mode decomposition, Center for Turbulence Research, 2012.
[37]	J. N. Juang and R. S. Pappa, An eigensystem realization algorithm for modal parameter identification and model reduction, Journal of Guidance, Control, and Dynamics, 8 (1985), 620-627.doi: 10.2514/3.20031.
[38]	I. G. Kevrekidis, C. W. Gear, J. M. Hyman, P. G. Kevrekidis, O. Runborg and C. Theodoropoulos, Equation-free, coarse-grained multiscale computation: Enabling microscopic simulators to perform system-level analysis, Communications in Mathematical Science, 1 (2003), 715-762.doi: 10.4310/CMS.2003.v1.n4.a5.
[39]	B. O. Koopman, Hamiltonian systems and transformation in Hilbert space, Proceedings of the National Academy of Sciences, 17 (1931), 315-318.doi: 10.1073/pnas.17.5.315.
[40]	J. N. Kutz, Data-Driven Modeling & Scientific Computation: Methods for Complex Systems & Big Data, Oxford University Press, 2013.
[41]	J. N. Kutz, X. Fu and S. L. Brunton, Multi-resolution dynamic mode decomposition, SIAM Journal on Applied Dynamical Systems, 15 (2016), 713-735, Available: arXiv:1506.00564.doi: 10.1137/15M1023543.
[42]	J. L. Lumley, Stochastic Tools in Turbulence, Academic Press, 1970.
[43]	Z. Ma, S. Ahuja and C. W. Rowley, Reduced order models for control of fluids using the eigensystem realization algorithm, Theoretical and Computational Fluid Dynamics, 25 (2011), 233-247.doi: 10.1007/s00162-010-0184-8.
[44]	A. Mackey, H. Schaeffer and S. Osher, On the compressive spectral method, Multiscale Modeling & Simulation, 12 (2014), 1800-1827.doi: 10.1137/140965909.
[45]	I. Mezić, Analysis of fluid flows via spectral properties of the Koopman operator, Annual Review of Fluid Mechanics, 45 (2013), 357-378.doi: 10.1146/annurev-fluid-011212-140652.
[46]	I. Mezić, Spectral properties of dynamical systems, model reduction and decompositions, Nonlinear Dynamics, 41 (2005), 309-325.doi: 10.1007/s11071-005-2824-x.
[47]	D. Needell and J. A. Tropp, CoSaMP: iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal., 26 (2009), 301-321.doi: 10.1016/j.acha.2008.07.002.
[48]	B. R. Noack, K. Afanasiev, M. Morzynski, G. Tadmor and F. Thiele, A hierarchy of low-dimensional models for the transient and post-transient cylinder wake, Journal of Fluid Mechanics, 497 (2003), 335-363.doi: 10.1017/S0022112003006694.
[49]	H. Nyquist, Certain topics in telegraph transmission theory, Transactions of the A. I. E. E., (1928), 617-644.
[50]	V. M. Patel and R. Chellappa, Sparse Representations and Compressive Sensing for Imaging and Vision, Briefs in Electrical and Computer Engineering. Springer, 2013.doi: 10.1007/978-1-4614-6381-8.
[51]	C. Penland, Random forcing and forecasting using Principal Oscillation Pattern analysis, Mon. Weather Rev., 117 (1989), 2165-2185.
[52]	C. Penland and T. Magorian, Prediction of Niño 3 sea-surface temperatures using linear inverse modeling, J. Climate, 6 (1993), 1067-1076.
[53]	J. L. Proctor, S. L. Brunton and J. N. Kutz, Dynamic mode decomposition with control, SIAM Journal on Applied Dynamical Systems, 15 (2016), 142-161.doi: 10.1137/15M1013857.
[54]	H. Qi and S. M. Hughes, Invariance of principal components under low-dimensional random projection of the data, IEEE International Conference on Image Processing, (2012), 937-940.doi: 10.1109/ICIP.2012.6467015.
[55]	C. W. Rowley, I. Mezić, S. Bagheri, P. Schlatter and D. S. Henningson, Spectral analysis of nonlinear flows, Journal of Fluid Mechanics, 641 (2009), 115-127.doi: 10.1017/S0022112009992059.
[56]	A. C. Sankaranarayanan, P. K. Turaga, R. G. Baraniuk and R. Chellappa, Compressive acquisition of dynamic scenes, In Computer Vision-ECCV, (2010), 129-142.
[57]	S. Sargsyan, S. L. Brunton and J. N. Kutz, Nonlinear model reduction for dynamical systems using sparse sensor locations from learned libraries, Physical Review E, 92 (2015), 033304.doi: 10.1103/PhysRevE.92.033304.
[58]	H. Schaeffer, R. Caflisch, C. D. Hauck and S. Osher, Sparse dynamics for partial differential equations, Proceedings of the National Academy of Sciences USA, 110 (2013), 6634-6639.doi: 10.1073/pnas.1302752110.
[59]	P. J. Schmid, Dynamic mode decomposition of numerical and experimental data, Journal of Fluid Mechanics, 656 (2010), 5-28.doi: 10.1017/S0022112010001217.
[60]	P. J. Schmid, Application of the dynamic mode decomposition to experimental data, Experiments in Fluids, 50 (2011), 1123-1130.doi: 10.1007/s00348-010-0911-3.
[61]	P. J. Schmid and J. Sesterhenn, Dynamic mode decomposition of numerical and experimental data, In 61st Annual Meeting of the APS Division of Fluid Dynamics, American Physical Society, November 2008.
[62]	P. J. Schmid, D. Violato and F. Scarano, Decomposition of time-resolved tomographic PIV, Experiments in Fluids, 52 (2012), 1567-1579.doi: 10.1007/s00348-012-1266-8.
[63]	C. E. Shannon, A mathematical theory of communication, Bell System Technical Journal, 27 (1948), 379-423.doi: 10.1002/j.1538-7305.1948.tb01338.x.
[64]	J. V. Shi, W. Yin, A. C. Sankaranarayanan and R. G. Baraniuk, Video compressive sensing for dynamic MRI, BMC Neuroscience, 13 (2012), p183.doi: 10.1186/1471-2202-13-S1-P183.
[65]	L. Sirovich, Turbulence and the dynamics of coherent structures, parts I-III, Q. Appl. Math., 45 (1987), 561-571.
[66]	T. H. Solomon and J. P. Gollub, Chaotic particle transport in time-dependent Rayleigh-Bénard convection, Physical Review A, 38 (1988), 6280-6286.doi: 10.1103/PhysRevA.38.6280.
[67]	G. Tissot, L. Cordier, N. Benard and B. R. Noack, Model reduction using dynamic mode decomposition, Comptes Rendus Mécanique, 342 (2014), 410-416.doi: 10.1016/j.crme.2013.12.011.
[68]	J. A. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Transactions on Information Theory, 50 (2004), 2231-2242.doi: 10.1109/TIT.2004.834793.
[69]	J. A. Tropp, J. N. Laska, M. F. Duarte, J. K. Romberg and R. G. Baraniuk, Beyond Nyquist: Efficient sampling of sparse bandlimited signals, IEEE Transactions on Information Theory, 56 (2010), 520-544.doi: 10.1109/TIT.2009.2034811.
[70]	J. H. Tu, C. W. Rowley, D. M. Luchtenburg, S. L. Brunton and J. N. Kutz, On dynamic mode decomposition: Theory and applications, Journal of Computational Dynamics, 1 (2014), 391-421.doi: 10.3934/jcd.2014.1.391.
[71]	J. H. Tu, C. W. Rowley, E. Aram and R. Mittal, Koopman spectral analysis of separated flow over a finite-thickness flat plate with elliptical leading edge, 49th AIAA Aerospace Sciences Meeting including the New Horizons Forum and Aerospace Exposition, (2011), p2864.doi: 10.2514/6.2011-38.
[72]	J. H. Tu, C. W. Rowley, J. N. Kutz and J. K. Shang, Spectral analysis of fluid flows using sub-Nyquist rate PIV data, Experiments in Fluids, 55 (2014), p1805.doi: 10.1007/s00348-014-1805-6.