A survey of compressed sensing. (English) Zbl 1333.94015
Boche, Holger (ed.) et al., Compressed sensing and its applications. MATHEON workshop, Berlin, Germany, December 2013. Cham: Birkhäuser/Springer (ISBN 978-3-319-16041-2/hbk; 978-3-319-16042-9/ebook). Applied and Numerical Harmonic Analysis, 1-39 (2015).
Summary: Compressed sensing was introduced some ten years ago as an effective way of acquiring signals, which possess a sparse or nearly sparse representation in a suitable basis or dictionary. Due to its solid mathematical backgrounds, it quickly attracted the attention of mathematicians from several different areas, so that the most important aspects of the theory are nowadays very well understood. In recent years, its applications started to spread out through applied mathematics, signal processing, and electrical engineering. The aim of this chapter is to provide an introduction into the basic concepts of compressed sensing. In the first part of this chapter, we present the basic mathematical concepts of compressed sensing, including the Null Space Property, Restricted Isometry Property, their connection to basis pursuit and sparse recovery, and construction of matrices with small restricted isometry constants. This presentation is easily accessible, largely self-contained, and includes proofs of the most important theorems. The second part gives an overview of the most important extensions of these ideas, including recovery of vectors with sparse representation in frames and dictionaries, discussion of (in)coherence and its implications for compressed sensing, and presentation of other algorithms of sparse recovery.
For the entire collection see [Zbl 1320.94007].
For the entire collection see [Zbl 1320.94007].
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 94-02 | Research exposition (monographs, survey articles) pertaining to information and communication theory |
References:
| [1] | Achlioptas, D., Database-friendly random projections: Johnson-Lindenstrauss with binary coins, J. Comput. Syst. Sci., 66, 671-687 (2003) · Zbl 1054.68040 · doi:10.1016/S0022-0000(03)00025-4 |
| [2] | Arora, S.; Barak, B., Computational Complexity: A Modern Approach (2009), Cambridge: Cambridge University Press, Cambridge · Zbl 1193.68112 · doi:10.1017/CBO9780511804090 |
| [3] | Baraniuk, R.; Cevher, V.; Duarte, M. F.; Hegde, C., Model-based compressive sensing, IEEE Trans. Inf. Theory, 56, 1982-2001 (2010) · Zbl 1366.94215 · doi:10.1109/TIT.2010.2040894 |
| [4] | Baraniuk, R.; Davenport, M.; DeVore, R.; Wakin, M., A simple proof of the restricted isometry property for random matrices, Constr. Approx., 28, 253-263 (2008) · Zbl 1177.15015 · doi:10.1007/s00365-007-9003-x |
| [5] | Baraniuk, R., Steeghs, P.: Compressive radar imaging. In: Proc. IEEE Radar Conf., Boston, pp. 128-133 (2007) |
| [6] | Baron, D.; Duarte, M. F.; Sarvotham, S.; Wakin, M. B.; Baraniuk, R., Distributed compressed sensing of jointly sparse signals (2005), Proc. Asilomar Conf. Signals, Systems, and Computers, Pacic Grove: In, Proc. Asilomar Conf. Signals, Systems, and Computers, Pacic Grove |
| [7] | Becker, S.; Candés, E. J.; Grant, M., Templates for convex cone problems with applications to sparse signal recovery, Math. Program. Comput., 3, 165-218 (2010) · Zbl 1257.90042 · doi:10.1007/s12532-011-0029-5 |
| [8] | Blumensath, T.; Davies, M., Iterative hard thresholding for compressive sensing, Appl. Comput. Harmon. Anal., 27, 265-274 (2009) · Zbl 1174.94008 · doi:10.1016/j.acha.2009.04.002 |
| [9] | Cai, T.; Wang, L.; Xu, G., New bounds for restricted isometry constants, IEEE Trans. Inf. Theory, 56, 4388-4394 (2010) · Zbl 1366.94181 · doi:10.1109/TIT.2010.2054730 |
| [10] | Cai, T.; Wang, L.; Xu, G., Shifting inequality and recovery of sparse vectors, IEEE Trans. Signal Process., 58, 1300-1308 (2010) · Zbl 1392.94117 · doi:10.1109/TSP.2009.2034936 |
| [11] | Candés, E. J., The restricted isometry property and its implications for compressed sensing. C. R. Acad. Sci., Paris, Ser, I, 346, 589-592 (2008) · Zbl 1153.94002 |
| [12] | Candés, E. J.; Plan, Y., A probabilistic and RIPless theory of compressed sensing, IEEE Trans. Inf. Theory, 57, 7235-7254 (2011) · Zbl 1365.94174 · doi:10.1109/TIT.2011.2161794 |
| [13] | Candés, E. J.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 489-509 (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083 |
| [14] | Candés, E. J.; Romberg, J.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math., 59, 1207-1223 (2006) · Zbl 1098.94009 · doi:10.1002/cpa.20124 |
| [15] | Candés, E. J.; Tao, T., Decoding by linear programming, IEEE Trans. Inf. Theory, 51, 4203-4215 (2005) · Zbl 1264.94121 · doi:10.1109/TIT.2005.858979 |
| [16] | Candés, E. J.; Tao, T., Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inf. Theory, 52, 5406-5425 (2006) · Zbl 1309.94033 · doi:10.1109/TIT.2006.885507 |
| [17] | Candés, E.J., Tao, T.: The Dantzig selector: statistical estimation when p is much larger than n. Ann. Stat. 35, 2313-2351 (2007) · Zbl 1139.62019 |
| [18] | Cevher, V., Tyagi, H.: Active learning of multi-index function models. In: Proc. NIPS (The Neural Information Processing Systems), Lake Tahoe, Reno (2012) |
| [19] | Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20, 33-61 (1998) · Zbl 0919.94002 · doi:10.1137/S1064827596304010 |
| [20] | Cohen, A.; Dahmen, W.; DeVore, R., Compressed sensing and best k-term approximation, J. Am. Math. Soc., 22, 211-231 (2009) · Zbl 1206.94008 · doi:10.1090/S0894-0347-08-00610-3 |
| [21] | Cohen, A.; Daubechies, I.; DeVore, R.; Kerkyacharian, G.; Picard, D., Capturing ridge functions in high dimensions from point queries, Constr. Approx., 35, 225-243 (2012) · Zbl 1318.62286 · doi:10.1007/s00365-011-9147-6 |
| [22] | Dasgupta, S.; Gupta, A., An elementary proof of a theorem of Johnson and Lindenstrauss, Random Struct. Algorithm., 22, 60-65 (2003) · Zbl 1018.51010 · doi:10.1002/rsa.10073 |
| [23] | Davenport, M.A., Duarte, M.F., Eldar, Y.C., Kutyniok, G.: Introduction to compressed sensing. Compressed sensing, pp. 1-64. Cambridge University Press, Cambridge (2012) |
| [24] | DeVore, R.; Petrova, G.; Wojtaszczyk, P., Approximation of functions of few variables in high dimensions, Constr. Approx., 33, 125-143 (2011) · Zbl 1210.41009 · doi:10.1007/s00365-010-9105-8 |
| [25] | Donoho, D. L., Compressed sensing, IEEE Trans. Inf. Theory, 52, 1289-1306 (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582 |
| [26] | Donoho, D. L.; Tsaig, Y.; Drori, I.; Starck, J.-L., Sparse solution of underdetermined systems of linear equations by stagewise Orthogonal Matching Pursuit, IEEE Trans. Inf. Theory, 58, 1094-1121 (2012) · Zbl 1365.94069 · doi:10.1109/TIT.2011.2173241 |
| [27] | Dorfman, R., The detection of defective members of large populations, Ann. Math. Stat., 14, 436-440 (1943) · doi:10.1214/aoms/1177731363 |
| [28] | Du, D.; Hwang, F., Combinatorial group testing and its applications (2000), Singapore: World Scientic, Singapore · Zbl 0952.90001 |
| [29] | Duarte, M.; Davenport, M.; Takhar, D.; Laska, J.; Ting, S.; Kelly, K.; Baraniuk, R., Single-pixel imaging via compressive sampling, IEEE Signal Process. Mag., 25, 83-91 (2008) · doi:10.1109/MSP.2007.914730 |
| [30] | Duarte, M., Wakin, M., Baraniuk, R.: Fast reconstruction of piecewise smooth signals from random projections. In: Proc. Work. Struc. Parc. Rep. Adap. Signaux (SPARS), Rennes (2005) |
| [31] | Duarte, M., Wakin, M., Baraniuk, R.: Wavelet-domain compressive signal reconstruction using a hidden Markov tree model. In: Proc. IEEE Int. Conf. Acoust., Speech, and Signal Processing (ICASSP), Las Vegas (2008) |
| [32] | Eldar, Y.; Mishali, M., Robust recovery of signals from a structured union of subspaces, IEEE Trans. Inf. Theory, 55, 5302-5316 (2009) · Zbl 1367.94087 · doi:10.1109/TIT.2009.2030471 |
| [33] | Elad, M., Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing (2010), New York: Springer, New York · Zbl 1211.94001 · doi:10.1007/978-1-4419-7011-4 |
| [34] | Figueiredo, M.; Nowak, R.; Wright, S., Gradient projections for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE J. Select. Top. Signal Process., 1, 586-597 (2007) · doi:10.1109/JSTSP.2007.910281 |
| [35] | Fornasier, M.; Rauhut, H.; Scherzer, O., Compressive sensing, Handbook of Mathematical Methods in Imaging, 187-228 (2011), Heidelberg: Springer, Heidelberg · Zbl 1259.94017 · doi:10.1007/978-0-387-92920-0_6 |
| [36] | Fornasier, M.; Rauhut, H., Recovery algorithms for vector valued data with joint sparsity constraints, SIAM J. Numer. Anal., 46, 577-613 (2008) · Zbl 1211.65066 · doi:10.1137/0606668909 |
| [37] | Fornasier, M.; Schnass, K.; Vybíral, J., Learning functions of few arbitrary linear parameters in high dimensions, Found. Comput. Math., 12, 229-262 (2012) · Zbl 1252.65036 · doi:10.1007/s10208-012-9115-y |
| [38] | Foucart, S., A note on guaranteed sparse recovery via 1-minimization, Appl. Comput. Harmon. Anal., 29, 97-103 (2010) · Zbl 1198.41011 · doi:10.1016/j.acha.2009.10.004 |
| [39] | Foucart, S., Lai M.: Sparsest solutions of underdetermined linear systems via l_q-minimization for 0 < q ≤ 1. Appl. Comput. Harmon. Anal. 26, 395-407 (2009) · Zbl 1171.90014 |
| [40] | Foucart, S.; Rauhut, H., A Mathematical Introduction to Compressive Sensing (2013), New York: Birkhäuser/Springer, New York · Zbl 1315.94002 · doi:10.1007/978-0-8176-4948-7 |
| [41] | Friedman, J.; Hastie, T.; Tibshirani, R., Regularization paths for generalized linear models via coordinate descent, J. Stat. Softw., 33, 1-22 (2010) |
| [42] | Gärtner, B.; Matoušek, J., Understanding and Using Linear Programming (2006), Berlin: Springer, Berlin |
| [43] | Gilbert, A.; Li, Y.; Porat, E.; Strauss, M., Approximate sparse recovery: optimizaing time and measurements (2010), Proc. ACM Symp. Theory of Comput., Cambridge: In, Proc. ACM Symp. Theory of Comput., Cambridge · Zbl 1293.94022 · doi:10.1145/1806689.1806755 |
| [44] | Gilbert, A.; Strauss, M.; Tropp, J.; Vershynin, R., One sketch for all: fast algorithms for compressed sensing (2007), Proc. ACM Symp. Theory of Comput., San Diego: In, Proc. ACM Symp. Theory of Comput., San Diego · Zbl 1232.94008 · doi:10.1145/1250790.1250824 |
| [45] | Jasper, J.; Mixon, D. G.; Fickus, M., Kirkman equiangular tight frames and codes, IEEE Trans. Inf. Theory, 60, 170-181 (2014) · Zbl 1364.42036 · doi:10.1109/TIT.2013.2285565 |
| [46] | Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. In: Conf. in Modern Analysis and Probability, pp. 189-206 (1984) · Zbl 0539.46017 |
| [47] | Krahmer, F.; Ward, R., New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property, SIAM J. Math. Anal., 43, 1269-1281 (2011) · Zbl 1247.15019 · doi:10.1137/100810447 |
| [48] | La, C., Do, M.N.: Tree-based orthogonal matching pursuit algorithm for signal reconstruction. In: IEEE Int. Conf. Image Processing (ICIP), Atlanta (2006) |
| [49] | Ledoux, M., The Concentration of Measure Phenomenon (2001), Providence: American Mathematical Society, Providence · Zbl 0995.60002 |
| [50] | Ledoux, M.; Talagrand, M., Probability in Banach Spaces (1991), Springer, Berlin: Isoperimetry and Processes, Springer, Berlin · Zbl 0748.60004 · doi:10.1007/978-3-642-20212-4 |
| [51] | Loris, I., On the performance of algorithms for the minimization of ℓ_1-penalized functions, Inverse Prob., 25, 035008 (2009) · Zbl 1162.65333 · doi:10.1088/0266-5611/25/3/035008 |
| [52] | Lustig, M.; Donoho, D.; Pauly, J. M., Sparse MRI: the application of compressed sensing for rapid MR imaging, Magn. Reson. Med., 58, 1182-1195 (2007) · doi:10.1002/mrm.21391 |
| [53] | Mallat, S.; Zhang, Z., Matching pursuits with time-frequency dictionaries, IEEE Trans. Signal Process., 41, 3397-3415 (1993) · Zbl 0842.94004 · doi:10.1109/78.258082 |
| [54] | Matoušek, J., On variants of the Johnson-Lindenstrauss lemma, Rand. Struct. Algorithm., 33, 142-156 (2008) · Zbl 1154.51002 · doi:10.1002/rsa.20218 |
| [55] | Milman, V. D.; Schechtman, G., Asymptotic theory of finite-dimensional normed spaces (1986), Berlin: Springer, Berlin · Zbl 0606.46013 |
| [56] | Mishali, M.; Eldar, Y., From theory to practice: Sub-nyquist sampling of sparse wideband analog signals, IEEE J. Sel. Top. Signal Process., 4, 375-391 (2010) · doi:10.1109/JSTSP.2010.2042414 |
| [57] | Needell, D.; Tropp, J., CoSaMP: Iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal., 26, 301-321 (2009) · Zbl 1163.94003 · doi:10.1016/j.acha.2008.07.002 |
| [58] | Pietsch, A., Operator Ideals (1980), Amsterdam: North-Holland, Amsterdam · Zbl 0434.47030 |
| [59] | Rauhut, H., Random sampling of sparse trigonometric polynomials, Appl. Comput. Harmon. Anal., 22, 16-42 (2007) · Zbl 1123.94004 · doi:10.1016/j.acha.2006.05.002 |
| [60] | Rauhut, H.; Schnass, K.; Vandergheynst, P., Compressed sensing and redundant dictionaries, IEEE Trans. Inf. Theor., 54, 2210-2219 (2008) · Zbl 1332.94022 · doi:10.1109/TIT.2008.920190 |
| [61] | Rauhut, H.; Ward, R., Sparse Legendre expansions via ℓ_1-minimization, J. Approx. Theory, 164, 517-533 (2012) · Zbl 1239.65018 · doi:10.1016/j.jat.2012.01.008 |
| [62] | Schnass, K., Vybíral, J.: Compressed learning of high-dimensional sparse functions. In: IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP), pp. 3924-3927 (2011) |
| [63] | Stojnic, M.; Parvaresh, F.; Hassibi, B., On the reconstruction of block-sparse signals with an optimal number of measurements, IEEE Trans. Signal Process., 57, 3075-3085 (2009) · Zbl 1391.94402 · doi:10.1109/TSP.2009.2020754 |
| [64] | Tibshirani, R., Regression shrinkage and selection via the Lasso, J. R. Stat. Soc. B, 58, 267-288 (1996) · Zbl 0850.62538 |
| [65] | Tropp, J., Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inf. Theor., 50, 2231-2242 (2004) · Zbl 1288.94019 · doi:10.1109/TIT.2004.834793 |
| [66] | Tropp, J., Algorithms for simultaneous sparse approximation, Part II: Convex relaxation. Signal Process., 86, 589-602 (2006) · Zbl 1163.94395 |
| [67] | Tropp, J.; Gilbert, A., Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Inf. Theory, 53, 4655-4666 (2007) · Zbl 1288.94022 · doi:10.1109/TIT.2007.909108 |
| [68] | Tropp, J.; Gilbert, A.; Strauss, M., Algorithms for simultaneous sparse approximation, Part I: Greedy pursuit. Signal Process., 86, 572-588 (2006) · Zbl 1163.94396 |
| [69] | Tropp, J.; Laska, J.; Duarte, M.; Romberg, J.; Baraniuk, R., Beyond Nyquist: efficient sampling of sparse bandlimited signals, IEEE Trans. Inf. Theor., 56, 520-544 (2010) · Zbl 1366.94222 · doi:10.1109/TIT.2009.2034811 |
| [70] | Wakin, M.B., Sarvotham, S., Duarte, M.F., Baron, D., Baraniuk, R.: Recovery of jointly sparse signals from few random projections. In: Proc. Workshop on Neural Info. Proc. Sys. (NIPS), Vancouver (2005) |
| [71] | Welch, L., Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inf. Theory, 20, 397-399 (1974) · Zbl 0298.94006 · doi:10.1109/TIT.1974.1055219 |
| [72] | Wojtaszczyk, P., Complexity of approximation of functions of few variables in high dimensions, J. Complex., 27, 141-150 (2011) · Zbl 1343.65015 · doi:10.1016/j.jco.2011.01.004 |
| [73] | Yin, W.; Osher, S.; Goldfarb, D.; Darbon, J., Bregman iterative algorithms for ℓ_1-minimization with applications to compressed sensing, SIAM J. Imag. Sci., 1, 143-168 (2008) · Zbl 1203.90153 · doi:10.1137/070703983 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
