Skip to Main Content

Bulletin of the American Mathematical Society

The Bulletin publishes expository articles on contemporary mathematical research, written in a way that gives insight to mathematicians who may not be experts in the particular topic. The Bulletin also publishes reviews of selected books in mathematics and short articles in the Mathematical Perspectives section, both by invitation only.

ISSN 1088-9485 (online) ISSN 0273-0979 (print)

The 2020 MCQ for Bulletin of the American Mathematical Society is 0.84.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Book Review

The AMS does not provide abstracts of book reviews. You may download the entire review from the links below.


MathSciNet review: 3686326
Full text of review: PDF   This review is available free of charge.
Book Information:

Authors: S. Foucart and H. Rauhut
Title: A mathematical introduction to compressive sensing
Additional book information: Applied and Numeric Harmonic Analysis, Birkh{\"a}user/Springer, New York, 2013, xviii+625 pp., ISBN 978-0-8176-4948-7

References [Enhancements On Off] (What's this?)

  • 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. MR 3311453, DOI 10.1093/imaiai/iau005
  • 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.
  • 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. MR 3493967, DOI 10.1007/s00365-015-9310-6
  • 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.
  • Andrew R. Barron, Universal approximation bounds for superpositions of a sigmoidal function, IEEE Trans. Inform. Theory 39 (1993), no. 3, 930–945. MR 1237720, DOI 10.1109/18.256500
  • 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. MR 3313755, DOI 10.1214/14-AAP1010
  • 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. MR 2833262, DOI 10.1007/s12532-011-0029-5
  • 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. MR 2817651, DOI 10.1215/00127094-1384809
  • 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.
  • 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. MR 2236170, DOI 10.1109/TIT.2005.862083
  • 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. MR 2989474, DOI 10.1007/s10208-012-9135-7
  • 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. MR 1639094, DOI 10.1137/S1064827596304010
  • 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.
  • 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.
  • 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. MR 2960550, DOI 10.1109/TSP.2012.2201149
  • 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. MR 1321432, DOI 10.1016/B978-0-08-052084-1.50018-1
  • R. A. DeVore and V. N. Temlyakov, Some remarks on greedy algorithms, Adv. Comput. Math. 5 (1996), no. 2-3, 173–187. MR 1399379, DOI 10.1007/BF02124742
  • D. L. Donoho and B. F. Logan, Signal recovery and the large sieve, SIAM J. Appl. Math. 52 (1992), no. 2, 577–591. MR 1154788, DOI 10.1137/0152031
  • 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. MR 2546388, DOI 10.1098/rsta.2009.0152
  • David L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289–1306. MR 2241189, DOI 10.1109/TIT.2006.871582
  • David L. Donoho and Michael Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via $l^1$ minimization, Proc. Natl. Acad. Sci. USA 100 (2003), no. 5, 2197–2202. MR 1963681, DOI 10.1073/pnas.0437847100
  • 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. MR 2237332, DOI 10.1109/TIT.2005.860430
  • David L. Donoho and Xiaoming Huo, Uncertainty principles and ideal atomic decomposition, IEEE Trans. Inform. Theory 47 (2001), no. 7, 2845–2862. MR 1872845, DOI 10.1109/18.959265
  • David L. Donoho and Iain M. Johnstone, Minimax risk over $l_p$-balls for $l_q$-error, Probab. Theory Related Fields 99 (1994), no. 2, 277–303. MR 1278886, DOI 10.1007/BF01199026
  • David L. Donoho and Philip B. Stark, Uncertainty principles and signal recovery, SIAM J. Appl. Math. 49 (1989), no. 3, 906–931. MR 997928, DOI 10.1137/0149053
  • 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. MR 2449053, DOI 10.1090/S0894-0347-08-00600-0
  • 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. MR 1658775, DOI 10.1109/18.720544
  • Yonina C. Eldar and Gitta Kutyniok (eds.), Compressed sensing, Cambridge University Press, Cambridge, 2012. Theory and applications. MR 2961961, DOI 10.1017/CBO9780511794308
  • 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.
  • M. Fazel, Matrix rank minimization with applications, Ph.D. Thesis, Palo Alto, 2002.
  • J. R. Fienup, Phase retrieval algorithms: a comparison, Appl. Opt. 21 (1982Aug), no. 15, 2758–2769.
  • Simon Foucart, Alain Pajor, Holger Rauhut, and Tino Ullrich, The Gelfand widths of $\ell _p$-balls for $0<p\leq 1$, J. Complexity 26 (2010), no. 6, 629–640. MR 2735423, DOI 10.1016/j.jco.2010.04.004
  • Simon Foucart and Holger Rauhut, A mathematical introduction to compressive sensing, Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, New York, 2013. MR 3100033, DOI 10.1007/978-0-8176-4948-7
  • Jean Jacques Fuchs, Recovery of exact sparse representations in the presence of bounded noise, IEEE Trans. Inform. Theory 51 (2005), no. 10, 3601–3608. MR 2237526, DOI 10.1109/TIT.2005.855614
  • A. Yu. Garnaev and E. D. Gluskin, The widths of a Euclidean ball, Dokl. Akad. Nauk SSSR 277 (1984), no. 5, 1048–1052 (Russian). MR 759962
  • 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.
  • A. Gilbert and P. Indyk, Sparse recovery using sparse matrices, Proceedings of the IEEE 98 (2010June), no. 6, 937–947.
  • 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. MR 2121138, DOI 10.1145/509907.509933
  • 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. MR 2121164, DOI 10.1145/509907.509966
  • 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.
  • M. Harwit and N. J. A. Sloane, Hadamard transform optics, Academic Press, 1979.
  • 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). MR 0481792
  • 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. MR 3263672, DOI 10.1002/cpa.21504
  • Eyal Kushilevitz and Yishay Mansour, Learning decision trees using the Fourier spectrum, SIAM J. Comput. 22 (1993), no. 6, 1331–1348. MR 1247193, DOI 10.1137/0222080
  • 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.
  • B. F. Logan, Properties of high-pass signals, Ph.D. Thesis, New York, 1965.
  • 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.
  • Stéphane Mallat, A wavelet tour of signal processing, 3rd ed., Elsevier/Academic Press, Amsterdam, 2009. The sparse way; With contributions from Gabriel Peyré. MR 2479996
  • Yishay Mansour, Randomized interpolation and approximation of sparse polynomials, SIAM J. Comput. 24 (1995), no. 2, 357–368. MR 1320215, DOI 10.1137/S0097539792239291
  • M. McCoy and J. A. Tropp, The achievable performance of convex demixing, 2013. Available at http://arXiv.org/abs/1309.7478.
  • 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. MR 3216671, DOI 10.1007/s00454-014-9595-4
  • Alan Miller, Subset selection in regression, 2nd ed., Monographs on Statistics and Applied Probability, vol. 95, Chapman & Hall/CRC, Boca Raton, FL, 2002. MR 2001193, DOI 10.1201/9781420035933
  • B. K. Natarajan, Sparse approximate solutions to linear systems, SIAM J. Comput. 24 (1995), no. 2, 227–234. MR 1320206, DOI 10.1137/S0097539792240406
  • 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 http://dx.doi.org/10.1190/1.1441413.
  • S. Oymak and J. A. Tropp, Universality laws for randomized dimension reduction, with applications, 2015. Available at http://arXiv.org/abs/1511.09433.
  • 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. MR 2680543, DOI 10.1137/070697835
  • Mark Rudelson and Roman Vershynin, The Littlewood-Offord problem and invertibility of random matrices, Adv. Math. 218 (2008), no. 2, 600–633. MR 2407948, DOI 10.1016/j.aim.2008.01.010
  • 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). MR 3363401, DOI 10.1016/0167-2789(92)90242-F
  • Fadil Santosa and William W. Symes, Linear inversion of band-limited reflection seismograms, SIAM J. Sci. Statist. Comput. 7 (1986), no. 4, 1307–1330. MR 857796, DOI 10.1137/0907087
  • M. Stojnic, Regularly random duality, 2013. Available at http://arXiv.org/abs/1303.7295.
  • Terence Tao, An uncertainty principle for cyclic groups of prime order, Math. Res. Lett. 12 (2005), no. 1, 121–127. MR 2122735, DOI 10.4310/MRL.2005.v12.n1.a11
  • 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.
  • 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.
  • Christos Thrampoulidis, Recovering structured signals in high dimensions via non-smooth convex optimization: Precise performance analysis., Ph.D. Thesis, Pasadena, 2016.
  • 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. MR 3382104
  • Robert Tibshirani, Regression shrinkage and selection via the lasso, J. Roy. Statist. Soc. Ser. B 58 (1996), no. 1, 267–288. MR 1379242
  • 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.
  • Joel A. Tropp, Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inform. Theory 50 (2004), no. 10, 2231–2242. MR 2097044, DOI 10.1109/TIT.2004.834793
  • Joel A. Tropp, Just relax: convex programming methods for identifying sparse signals in noise, IEEE Trans. Inform. Theory 52 (2006), no. 3, 1030–1051. MR 2238069, DOI 10.1109/TIT.2005.864420
  • Joel A. Tropp, User-friendly tail bounds for sums of random matrices, Found. Comput. Math. 12 (2012), no. 4, 389–434. MR 2946459, DOI 10.1007/s10208-011-9099-z
  • 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. MR 2589462, DOI 10.1109/TIT.2009.2034811
  • 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.
    •
    Review Information:

    Reviewer: Joel A. Tropp
    Affiliation: California Institute of Technology, Pasadena, California 91125-5000
    Email: jtropp@cms.caltech.edu
    Journal: Bull. Amer. Math. Soc. 54 (2017), 151-165
    DOI: https://doi.org/10.1090/bull/1546
    Keywords: Image processing, information theory, mathematical programming, probability in Banach spaces, random matrix theory, sampling theory, signal processing
    Published electronically: August 25, 2016
    Review copyright: © Copyright 2016 American Mathematical Society