×

Book review of: S. Foucart and H. Rauhut, A mathematical introduction to compressive sensing. (English) Zbl 1352.00019

Review of [Zbl 1315.94002].

MSC:

00A17 External book reviews
94-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
94A12 Signal theory (characterization, reconstruction, filtering, etc.)

Citations:

Zbl 1315.94002

Software:

PDCO; TFOCS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dennis Amelunxen, Martin Lotz, Michael B. McCoy, and Joel A. Tropp, Living on the edge: phase transitions in convex programs with random data, Inf. Inference 3 (2014), no. 3, 224 – 294. · Zbl 1339.90251 · doi:10.1093/imaiai/iau005
[2] M. Salman Asif, Ali Ayremlou, Aswin C. Sankaranarayanan, Ashok Veeraraghavan, and Richard G. Baraniuk, Flatcam: Thin, bare-sensor cameras using coded aperture and computation, 2015. Available at http://arXiv.org/abs/1509.00116.
[3] Afonso S. Bandeira, Matthew Fickus, Dustin G. Mixon, and Joel Moreira, Derandomizing restricted isometries via the Legendre symbol, Constr. Approx. 43 (2016), no. 3, 409 – 424. · Zbl 1367.94143 · doi:10.1007/s00365-015-9310-6
[4] R. G. Baraniuk, E. Candès, M. Elad, and Y. Ma, Applications of sparse representation and compressive sensing, Proceedings of the IEEE 98 (2010June), no. 6. Special issue.
[5] Andrew R. Barron, Universal approximation bounds for superpositions of a sigmoidal function, IEEE Trans. Inform. Theory 39 (1993), no. 3, 930 – 945. · Zbl 0818.68126 · doi:10.1109/18.256500
[6] Mohsen Bayati, Marc Lelarge, and Andrea Montanari, Universality in polytope phase transitions and message passing algorithms, Ann. Appl. Probab. 25 (2015), no. 2, 753 – 822. · Zbl 1322.60207 · doi:10.1214/14-AAP1010
[7] Stephen R. Becker, Emmanuel J. Candès, and Michael C. Grant, Templates for convex cone problems with applications to sparse signal recovery, Math. Program. Comput. 3 (2011), no. 3, 165 – 218. · Zbl 1257.90042 · doi:10.1007/s12532-011-0029-5
[8] Jean Bourgain, Stephen Dilworth, Kevin Ford, Sergei Konyagin, and Denka Kutzarova, Explicit constructions of RIP matrices and related problems, Duke Math. J. 159 (2011), no. 1, 145 – 185. · Zbl 1236.94027 · doi:10.1215/00127094-1384809
[9] E. J. Candès and M. A. Davenport, How well can we estimate a sparse vector?, Appl. Comput. Harmonic Anal. 34 (2013Mar.), no. 2, 317-323. · Zbl 1315.94019
[10] Emmanuel J. Candès, Justin Romberg, and Terence Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory 52 (2006), no. 2, 489 – 509. · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083
[11] Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo, and Alan S. Willsky, The convex geometry of linear inverse problems, Found. Comput. Math. 12 (2012), no. 6, 805 – 849. · Zbl 1280.52008 · doi:10.1007/s10208-012-9135-7
[12] Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput. 20 (1998), no. 1, 33 – 61. · Zbl 0919.94002 · doi:10.1137/S1064827596304010
[13] Jon F. Claerbout and Francis Muir, Robust modeling with erratic data, Geophysics 38 (1973), no. 5, 826-844, available at http://geophysics.geoscienceworld.org/content/38/5/826.full.pdf.
[14] R. R. Coifman and M. V. Wickerhauser, Entropy-based algorithms for best basis selection, IEEE Transactions on Information Theory 38 (1992March), no. 2, 713-718. · Zbl 0849.94005
[15] Mark A. Davenport, Jason N. Laska, John R. Treichler, and Richard G. Baraniuk, The pros and cons of compressive sensing for wideband signal acquisition: noise folding versus dynamic range, IEEE Trans. Signal Process. 60 (2012), no. 9, 4628 – 4642. · Zbl 1393.94678 · doi:10.1109/TSP.2012.2201149
[16] Geoffrey Davis, Stephane Mallat, and Zhifeng Zhang, Adaptive time-frequency approximations with matching pursuits, Wavelets: theory, algorithms, and applications (Taormina, 1993) Wavelet Anal. Appl., vol. 5, Academic Press, San Diego, CA, 1994, pp. 271 – 293. · Zbl 0854.94005 · doi:10.1016/B978-0-08-052084-1.50018-1
[17] R. A. DeVore and V. N. Temlyakov, Some remarks on greedy algorithms, Adv. Comput. Math. 5 (1996), no. 2-3, 173 – 187. · Zbl 0857.65016 · doi:10.1007/BF02124742
[18] D. L. Donoho and B. F. Logan, Signal recovery and the large sieve, SIAM J. Appl. Math. 52 (1992), no. 2, 577 – 591. · Zbl 0768.42001 · doi:10.1137/0152031
[19] David Donoho and Jared Tanner, Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 367 (2009), no. 1906, 4273 – 4293. With electronic supplementary materials available online. · Zbl 1185.94029 · doi:10.1098/rsta.2009.0152
[20] David L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289 – 1306. · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[21] David L. Donoho and Michael Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via \?\textonesuperior minimization, Proc. Natl. Acad. Sci. USA 100 (2003), no. 5, 2197 – 2202. · Zbl 1064.94011 · doi:10.1073/pnas.0437847100
[22] David L. Donoho, Michael Elad, and Vladimir N. Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Trans. Inform. Theory 52 (2006), no. 1, 6 – 18. · Zbl 1288.94017 · doi:10.1109/TIT.2005.860430
[23] David L. Donoho and Xiaoming Huo, Uncertainty principles and ideal atomic decomposition, IEEE Trans. Inform. Theory 47 (2001), no. 7, 2845 – 2862. · Zbl 1019.94503 · doi:10.1109/18.959265
[24] David L. Donoho and Iain M. Johnstone, Minimax risk over \?_{\?}-balls for \?_{\?}-error, Probab. Theory Related Fields 99 (1994), no. 2, 277 – 303. · Zbl 0802.62006 · doi:10.1007/BF01199026
[25] David L. Donoho and Philip B. Stark, Uncertainty principles and signal recovery, SIAM J. Appl. Math. 49 (1989), no. 3, 906 – 931. · Zbl 0689.42001 · doi:10.1137/0149053
[26] David L. Donoho and Jared Tanner, Counting faces of randomly projected polytopes when the projection radically lowers dimension, J. Amer. Math. Soc. 22 (2009), no. 1, 1 – 53. · Zbl 1206.52010
[27] David L. Donoho, Martin Vetterli, R. A. DeVore, and Ingrid Daubechies, Data compression and harmonic analysis, IEEE Trans. Inform. Theory 44 (1998), no. 6, 2435 – 2476. Information theory: 1948 – 1998. · Zbl 1125.94311 · doi:10.1109/18.720544
[28] Yonina C. Eldar and Gitta Kutyniok , Compressed sensing, Cambridge University Press, Cambridge, 2012. Theory and applications. · Zbl 1336.94022
[29] Y. Erlich, A. Gilbert, H. Ngo, A. Rudra, N. Thierry-Mieg, M. Wootters, D. Zielinski, and O. Zuk, Biological screens from linear codes: theory and tools, 2015. Unpublished.
[30] M. Fazel, Matrix rank minimization with applications, Ph.D. Thesis, Palo Alto, 2002.
[31] J. R. Fienup, Phase retrieval algorithms: a comparison, Appl. Opt. 21 (1982Aug), no. 15, 2758-2769.
[32] Simon Foucart, Alain Pajor, Holger Rauhut, and Tino Ullrich, The Gelfand widths of \ell _{\?}-balls for 0<\?\le 1, J. Complexity 26 (2010), no. 6, 629 – 640. · Zbl 1204.41019 · doi:10.1016/j.jco.2010.04.004
[33] Simon Foucart and Holger Rauhut, A mathematical introduction to compressive sensing, Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, New York, 2013. · Zbl 1315.94002
[34] Jean Jacques Fuchs, Recovery of exact sparse representations in the presence of bounded noise, IEEE Trans. Inform. Theory 51 (2005), no. 10, 3601 – 3608. · Zbl 1286.94031 · doi:10.1109/TIT.2005.855614
[35] A. Yu. Garnaev and E. D. Gluskin, The widths of a Euclidean ball, Dokl. Akad. Nauk SSSR 277 (1984), no. 5, 1048 – 1052 (Russian). · Zbl 0588.41022
[36] R. W. Gerchberg and W. O. Saxton, A practical algorithm for the determination of the phase from image and diffraction plane pictures, Optik 35 (1972), no. 2, 237-246.
[37] A. Gilbert and P. Indyk, Sparse recovery using sparse matrices, Proceedings of the IEEE 98 (2010June), no. 6, 937-947.
[38] A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, and M. Strauss, Near-optimal sparse Fourier representations via sampling, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 152 – 161. · Zbl 1192.94078 · doi:10.1145/509907.509933
[39] Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, and Martin J. Strauss, Fast, small-space algorithms for approximate histogram maintenance, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 389 – 398. · Zbl 1192.68962 · doi:10.1145/509907.509966
[40] Anna C. Gilbert, S. Muthukrishnan, and Martin J. Strauss, Approximation of functions over redundant dictionaries using coherence, Proceedings of the fourteenth annual acm-siam symposium on discrete algorithms, 2003, pp. 243-252. · Zbl 1094.41500
[41] M. Harwit and N. J. A. Sloane, Hadamard transform optics, Academic Press, 1979. · Zbl 0477.94001
[42] B. S. Kašin, The widths of certain finite-dimensional sets and classes of smooth functions, Izv. Akad. Nauk SSSR Ser. Mat. 41 (1977), no. 2, 334 – 351, 478 (Russian).
[43] Felix Krahmer, Shahar Mendelson, and Holger Rauhut, Suprema of chaos processes and the restricted isometry property, Comm. Pure Appl. Math. 67 (2014), no. 11, 1877 – 1904. · Zbl 1310.94024 · doi:10.1002/cpa.21504
[44] Eyal Kushilevitz and Yishay Mansour, Learning decision trees using the Fourier spectrum, SIAM J. Comput. 22 (1993), no. 6, 1331 – 1348. · Zbl 0799.68159 · doi:10.1137/0222080
[45] Shlomo Levy and Peter K. Fullagar, Reconstruction of a sparse spike train from a portion of its spectrum and application to high-resolution deconvolution, Geophysics 46 (1981), no. 9, 1235-1243, available at http://geophysics.geoscienceworld.org/content/46/9/1235.full.pdf.
[46] B. F. Logan, Properties of high-pass signals, Ph.D. Thesis, New York, 1965.
[47] Michael Lustig, David Donoho, and John M. Pauly, Sparse mri: The application of compressed sensing for rapid mr imaging, Magnetic Resonance in Medicine 58 (2007), no. 6, 1182-1195.
[48] Stéphane Mallat, A wavelet tour of signal processing, 3rd ed., Elsevier/Academic Press, Amsterdam, 2009. The sparse way; With contributions from Gabriel Peyré. · Zbl 1170.94003
[49] Yishay Mansour, Randomized interpolation and approximation of sparse polynomials, SIAM J. Comput. 24 (1995), no. 2, 357 – 368. · Zbl 0826.65005 · doi:10.1137/S0097539792239291
[50] M. McCoy and J. A. Tropp, The achievable performance of convex demixing, 2013. Available at http://arXiv.org/abs/1309.7478.
[51] Michael B. McCoy and Joel A. Tropp, From Steiner formulas for cones to concentration of intrinsic volumes, Discrete Comput. Geom. 51 (2014), no. 4, 926 – 963. · Zbl 1317.52010 · doi:10.1007/s00454-014-9595-4
[52] Alan Miller, Subset selection in regression, 2nd ed., Monographs on Statistics and Applied Probability, vol. 95, Chapman & Hall/CRC, Boca Raton, FL, 2002. · Zbl 1051.62060
[53] B. K. Natarajan, Sparse approximate solutions to linear systems, SIAM J. Comput. 24 (1995), no. 2, 227 – 234. · Zbl 0827.68054 · doi:10.1137/S0097539792240406
[54] D. W. Oldenburg, T. Scheuer, and S. Levy, Recovery of the acoustic impedance from reflection seismograms, GEOPHYSICS 48 (1983), no. 10, 1318-1337, available at https://doi.org/10.1190/1.1441413.
[55] S. Oymak and J. A. Tropp, Universality laws for randomized dimension reduction, with applications, 2015. Available at http://arXiv.org/abs/1511.09433.
[56] Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev. 52 (2010), no. 3, 471 – 501. · Zbl 1198.90321 · doi:10.1137/070697835
[57] Mark Rudelson and Roman Vershynin, The Littlewood-Offord problem and invertibility of random matrices, Adv. Math. 218 (2008), no. 2, 600 – 633. · Zbl 1139.15015 · doi:10.1016/j.aim.2008.01.010
[58] Leonid I. Rudin, Stanley Osher, and Emad Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D 60 (1992), no. 1-4, 259 – 268. Experimental mathematics: computational issues in nonlinear science (Los Alamos, NM, 1991). · Zbl 0780.49028
[59] Fadil Santosa and William W. Symes, Linear inversion of band-limited reflection seismograms, SIAM J. Sci. Statist. Comput. 7 (1986), no. 4, 1307 – 1330. · Zbl 0602.73113 · doi:10.1137/0907087
[60] M. Stojnic, Regularly random duality, 2013. Available at http://arXiv.org/abs/1303.7295.
[61] Terence Tao, An uncertainty principle for cyclic groups of prime order, Math. Res. Lett. 12 (2005), no. 1, 121 – 127. · Zbl 1080.42002 · doi:10.4310/MRL.2005.v12.n1.a11
[62] H. L. Taylor, S. C. Banks, and J. F. McCoy, Deconvolution with the l 1 norm, Geophysics 44 (1979), no. 1, 39-52, available at http://geophysics.geoscienceworld.org/content/44/1/39.full.pdf.
[63] C. Thrampoulidis, S. Oymak, and B. Hassibi, The Gaussian min-max theorem in the presence of convexity, 2014. Available at http://arXiv.org/abs/1408.4837. · Zbl 1333.94024
[64] Christos Thrampoulidis, Recovering structured signals in high dimensions via non-smooth convex optimization: Precise performance analysis., Ph.D. Thesis, Pasadena, 2016.
[65] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi, Recovering structured signals in noise: least-squares meets compressed sensing, Compressed sensing and its applications, Appl. Numer. Harmon. Anal., Birkhäuser/Springer, Cham, 2015, pp. 97 – 141. · Zbl 1333.94024
[66] Robert Tibshirani, Regression shrinkage and selection via the lasso, J. Roy. Statist. Soc. Ser. B 58 (1996), no. 1, 267 – 288. · Zbl 0850.62538
[67] J. A. Tropp and S. J. Wright, Computational methods for sparse solution of linear inverse problems, Proceedings of the IEEE 98 (2010June), no. 6, 948-958.
[68] Joel A. Tropp, Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inform. Theory 50 (2004), no. 10, 2231 – 2242. · Zbl 1288.94019 · doi:10.1109/TIT.2004.834793
[69] Joel A. Tropp, Just relax: convex programming methods for identifying sparse signals in noise, IEEE Trans. Inform. Theory 52 (2006), no. 3, 1030 – 1051. · Zbl 1288.94025 · doi:10.1109/TIT.2005.864420
[70] Joel A. Tropp, User-friendly tail bounds for sums of random matrices, Found. Comput. Math. 12 (2012), no. 4, 389 – 434. · Zbl 1259.60008 · doi:10.1007/s10208-011-9099-z
[71] Joel A. Tropp, Jason N. Laska, Marco F. Duarte, Justin K. Romberg, and Richard G. Baraniuk, Beyond Nyquist: efficient sampling of sparse bandlimited signals, IEEE Trans. Inform. Theory 56 (2010), no. 1, 520 – 544. · Zbl 1366.94222 · doi:10.1109/TIT.2009.2034811
[72] S. Vasanawala, M. Murphy, M. Alley, P. Lai, K. Keutzer, J. Pauly, and M. Lustig, Practical parallel imaging compressed sensing MRI: Summary of two years of experience in accelerating body MRI of pediatric patients, 2011 ieee international symposium on biomedical imaging: From nano to macro, 2011March, pp. 1039-1043.
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.