Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Linear Inverse Problems Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Compressive Sensing

Authors : Massimo Fornasier, Holger Rauhut

Published in: Handbook of Mathematical Methods in Imaging

Publisher: Springer New York

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Compressive sensing is a recent type of sampling theory, which predicts that sparse signals and images can be reconstructed from what was previously believed to be incomplete information. As a main feature, efficient algorithms such as ℓ 1-minimization can be used for recovery. The theory has many potential applications in signal processing and imaging. This chapter gives an introduction and overview on both theoretical and numerical aspects of compressive sensing.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Energy Minimization Methods
next chapter Duality and Convex Programming
Literature
1.
Achlioptas, D.: Database-friendly random projections. In: Proceedings of the 20th Annual ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Santa Barbara, pp. 274–281 (2001)
2.
Affentranger, F., Schneider, R.: Random projections of regular simplices. Discret. Comput. Geom. 7(3), 219–226 (1992)MATHMathSciNet
3.
Ailon, N., Liberty, E.: Almost optimal unrestricted fast Johnson-Lindenstrauss transform. In: Symposium on Discrete Algorithms (SODA), San Francisco, (2011)
4.
Alexeev, B., Bandeira, A.S., Fickus, M., Mixon, D.G.: Phase retrieval with polarization (2012). arXiv:1210.7752
5.
Balan, R., Casazza, P., Edidin, D.: On signal reconstruction without phase. Appl. Comput. Harmon. Anal. 20(3), 345–356 (2006)MATHMathSciNet
6.
Baraniuk, R.: Compressive sensing. IEEE Signal Process. Mag. 24(4), 118–121 (2007)
7.
Baraniuk, R.G., Davenport, M., DeVore, R.A., Wakin, M.: A simple proof of the restricted isometry property for random matrices. Constr. Approx. 28(3), 253–263 (2008)MATHMathSciNet
8.
Bauschke, H.H., Combettes, P.-L., Luke, D.R.: Hybrid projection-reflection method for phase retrieval. J. Opt. Soc. Am. A 20(6), 1025–1034 (2003)
9.
Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183–202 (2009)MATHMathSciNet
10.
Beck, A., Teboulle, M.: Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems. IEEE Trans. Image Process. 18(11), 2419–2434 (2009)MathSciNet
11.
Berinde, R., Gilbert, A.C., Indyk, P., Karloff, H., Strauss, M.: Combining geometry and combinatorics: a unified approach to sparse signal recovery. In: Proceedings of the 46th Annual Allerton Conference on Comunication, Control, and Computing 2008, Urbana, pp. 798–805. IEEE (2008)
12.
Blanchard, J.D., Cartis, C., Tanner, J., Thompson, A.: Phase transitions for greedy sparse approximation algorithms. Appl. Comput. Harmon. Anal. 30(2), 188–203 (2011)MATHMathSciNet
13.
Blumensath, T., Davies, M.: Iterative hard thresholding for compressed sensing. Appl. Comput. Harmon. Anal. 27(3), 265–274 (2009)MATHMathSciNet
14.
Bobin, J., Starck, J.-L., Ottensamer, R.: Compressed sensing in astronomy. IEEE J. Sel. Top. Signal Process. 2(5), 718–726 (2008)
15.
Bourgain, J., Dilworth, S., Ford, K., Konyagin, S., Kutzarova, D.: Breaking the k 2-barrier for explicit RIP matrices. In: STOC’11, San Jose, pp. 637–644 (2011)
16.
Bourgain, J., Dilworth, S., Ford, K., Konyagin, S., Kutzarova, D.: Explicit constructions of RIP matrices and related problems. Duke Math. J. 159(1), 145–185 (2011)MATHMathSciNet
17.
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge/New York (2004)MATH
18.
19.
Cai, T., Zhang, A.: Sparse representation of a polytope and recovery of sparse signals and low-rank matrices. IEEE Trans. Inf. Theory 60(1), 122–132 (2014)MathSciNet
20.
Cai, J.-F., Candès, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20(4), 1956–1982 (2010)MATHMathSciNet
21.
Candès, E.J.: Compressive sampling. In: Proceedings of the International Congress of Mathematicians, Madrid (2006)
22.
Candès, E.J.: The restricted isometry property and its implications for compressed sensing. C. R. Acad. Sci. Paris Ser. I Math. 346, 589–592 (2008)MATH
23.
Candès, E.J., Li, X.: Solving quadratic equations via PhaseLift when there are about as many equations as unknowns. Found. Comput. Math. 14(5), 1017–1026 (2014)MATHMathSciNet
24.
Candès, E.J., Plan, Y.: Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements. IEEE Trans. Inf. Theory 57(4), 2342–2359 (2011)
25.
Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9, 717–772 (2009)MATHMathSciNet
26.
Candès, E.J., Tao, T.: Near optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inf. Theory 52(12), 5406–5425 (2006)MATH
27.
Candès, E.J., Tao, T.: The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inf. Theory 56(5), 2053–2080 (2010)
28.
Candès, E., Wakin, M.: An introduction to compressive sampling. IEEE Signal Process. Mag. 25(2), 21–30 (2008)
29.
Candès, E.J., Tao, T., Romberg, J.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489–509 (2006)MATH
30.
Candès, E.J., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207–1223 (2006)MATH
31.
Candès, E., Li, X., Soltanolkotabi, M.: Phase retrieval from masked Fourier transforms (2013, preprint)
32.
Candès, E.J., Strohmer, T., Voroninski, V.: PhaseLift: exact and stable signal recovery from magnitude measurements via convex programming. Commun. Pure Appl. Math. 66(8), 1241–1274 (2013)MATH
33.
Capalbo, M., Reingold, O., Vadhan, S., Wigderson, A.: Randomness conductors and constant-degree lossless expanders. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, Montréal, pp. 659–668 (electronic). ACM (2002)
34.
Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40, 120–145 (2011)MATHMathSciNet
35.
Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33–61 (1999)MATHMathSciNet
36.
Christensen, O.: An Introduction to Frames and Riesz Bases. Applied and Numerical Harmonic Analysis. Birkhäuser, Boston (2003)MATH
37.
38.
Cohen, A., Dahmen, W., DeVore, R.A.: Compressed sensing and best k-term approximation. J. Am. Math. Soc. 22(1), 211–231 (2009)MATHMathSciNet
39.
Combettes, P., Pesquet, J.-C.: A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery. IEEE J. Sel. Top. Signal Process. 1(4), 564–574 (2007)
40.
Combettes, P., Pesquet, J.-C.: Proximal splitting methods in signal processing. In: Bauschke, H., Burachik, R., Combettes, P., Elser, V., Luke, D., Wolkowicz, H. (eds.) Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pp. 185–212. Springer, New York (2011)
41.
Combettes, P., Wajs, V.: Signal recovery by proximal forward-backward splitting. Multisc. Model. Simul. 4(4), 1168–1200 (electronic) (2005)
42.
Cormode, G., Muthukrishnan, S.: Combinatorial algorithms for compressed sensing. In: CISS, Princeton (2006)
43.
Daubechies, I., Defrise, M., De Mol, C.: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Commun. Pure Appl. Math. 57(11), 1413–1457 (2004)MATH
44.
Daubechies, I., DeVore, R., Fornasier, M., Güntürk, C.: Iteratively re-weighted least squares minimization for sparse recovery. Commun. Pure Appl. Math. 63(1), 1–38 (2010)MATH
45.
Davies, M., Gribonval, R.: Restricted isometry constants where ℓ p sparse recovery can fail for 0 < p ≤ 1. IEEE Trans. Inf. Theory 55(5), 2203–2214 (2009)MathSciNet
46.
Do, B., Indyk, P., Price, E., Woodruff, D.: Lower bounds for sparse recovery. In: Proceedings of the SODA, Austin (2010)
47.
48.
Donoho, D.L.: For most large underdetermined systems of linear equations the minimal l 1 solution is also the sparsest solution. Commun. Pure Appl. Anal. 59(6), 797–829 (2006)MATHMathSciNet
49.
Donoho, D.L.: High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension. Discret. Comput. Geom. 35(4), 617–652 (2006)MATHMathSciNet
50.
Donoho, D.L., Elad, M.: Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization. Proc. Natl. Acad. Sci. USA 100(5), 2197–2202 (2003)MATHMathSciNet
51.
Donoho, D.L., Huo, X.: Uncertainty principles and ideal atomic decompositions. IEEE Trans. Inf. Theory 47(7), 2845–2862 (2001)MATHMathSciNet
52.
Donoho, D., Logan, B.: Signal recovery and the large sieve. SIAM J. Appl. Math. 52(2), 577–591 (1992)MATHMathSciNet
53.
Donoho, D.L., Tanner, J.: Neighborliness of randomly projected simplices in high dimensions. Proc. Natl. Acad. Sci. USA 102(27), 9452–9457 (2005)MATHMathSciNet
54.
Donoho, D.L., Tanner, J.: Counting faces of randomly-projected polytopes when the projection radically lowers dimension. J. Am. Math. Soc. 22(1), 1–53 (2009)MATHMathSciNet
55.
Donoho, D.L., Tsaig, Y.: Fast solution of l1-norm minimization problems when the solution may be sparse. IEEE Trans. Inf. Theory 54(11), 4789–4812 (2008)MATHMathSciNet
56.
Dorfman, R.: The detection of defective members of large populations. Ann. Stat. 14, 436–440 (1943)
57.
Douglas, J., Rachford, H.: On the numerical solution of heat conduction problems in two or three space variables. Trans. Am. Math. Soc. 82, 421–439 (1956)MATHMathSciNet
58.
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(2), 83–91 (2008)
59.
Efron, B., Hastie, T., Johnstone, I., Tibshirani, R.: Least angle regression. Ann. Stat. 32(2), 407–499 (2004)MATHMathSciNet
60.
Ehler, M., Fornasier, M., Sigl, J.: Quasi-linear compressed sensing. Multiscale Model. Simul. 12(2), 725–754 (2014)MathSciNet
61.
Elad, M.: Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing. Springer, New York (2010)
62.
Elad, M., Bruckstein, A.M.: A generalized uncertainty principle and sparse representation in pairs of bases. IEEE Trans. Inf. Theory 48(9), 2558–2567 (2002)MATHMathSciNet
63.
Eldar, Y., Kutyniok, G. (eds.): Compressed Sensing – Theory and Applications. Cambridge University Press, Cambridge/New York (2012)
64.
Eldar, Y., Mendelson, S.: Phase retrieval: stability and recovery guarantees. Appl. Comput. Harmon. Anal. (to appear). doi:10.1016/j.acha.2013.08.003
65.
Ender, J.: On compressive sensing applied to radar. Signal Process. 90(5), 1402–1414 (2010)MATH
66.
Fannjiang, A., Yan, P., Strohmer, T.: Compressed remote sensing of sparse objects. SIAM J. Imaging Sci. 3(3), 595–618 (2010)MATHMathSciNet
67.
Fazel, M.: Matrix rank minimization with applications. PhD thesis, Stanford University (2002)
68.
Fienup, J.R.: Phase retrieval algorithms: a comparison. Appl. Opt. 21(15), 2758–2769 (1982)
69.
Fornasier, M.: Numerical methods for sparse recovery. In: Fornasier, M. (ed.) Theoretical Foundations and Numerical Methods for Sparse Recovery. Radon Series on Computational and Applied Mathematics, vol. 9, pp. 93–200. deGruyter, Berlin (2010). Papers based on the presentations of the summer school “Theoretical Foundations and Numerical Methods for Sparse Recovery”, Vienna, Austria, 31 Aug-4 Sept 2009
70.
Fornasier, M., March, R.: Restoration of color images by vector valued BV functions and variational calculus. SIAM J. Appl. Math. 68(2), 437–460 (2007)MATHMathSciNet
71.
Fornasier, M., Ramlau, R., Teschke, G.: The application of joint sparsity and total variation minimization algorithms to a real-life art restoration problem. Adv. Comput. Math. 31(1–3), 157–184 (2009)MATHMathSciNet
72.
Fornasier, M., Langer, A., Schönlieb, C.: A convergent overlapping domain decomposition method for total variation minimization. Numer. Math. 116(4), 645–685 (2010)MATHMathSciNet
73.
Fornasier, M., Rauhut, H., Ward, R.: Low-rank matrix recovery via iteratively reweighted least squares minimization. SIAM J. Optim. 21(4), 1614–1640 (2011)MATHMathSciNet
74.
Foucart, S.: A note on guaranteed sparse recovery via ℓ 1-minimization. Appl. Comput. Harmon. Anal. 29(1), 97–103 (2010)MATHMathSciNet
75.
Foucart, S., Lai, M.: Sparsest solutions of underdetermined linear systems via ℓ q -minimization for 0 < q ≤ 1. Appl. Comput. Harmon. Anal. 26(3), 395–407 (2009)MATHMathSciNet
76.
Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis. Birkhäuser, Boston (2013)MATH
77.
Foucart, S., Pajor, A., Rauhut, H., Ullrich, T.: The Gelfand widths of ℓ p -balls for 0 < p ≤ 1. J. Complex. 26(6), 629–640 (2010)MATHMathSciNet
78.
Fuchs, J.J.: On sparse representations in arbitrary redundant bases. IEEE Trans. Inf. Theory 50(6), 1341–1344 (2004)MATH
79.
Garnaev, A., Gluskin, E.: On widths of the Euclidean ball. Sov. Math. Dokl. 30, 200–204 (1984)MATH
80.
Gilbert, A.C., Muthukrishnan, S., Guha, S., Indyk, P., Strauss, M.: Near-optimal sparse Fourier representations via sampling. In: Proceedings of the STOC’02, Montréal, pp. 152–161. Association for Computing Machinery (2002)
81.
Gilbert, A.C., Muthukrishnan, S., Strauss, M.J.: Approximation of functions over redundant dictionaries using coherence. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, 12–14 Jan 2003, pp. 243–252. SIAM and Association for Computing Machinery (2003)
82.
Gilbert, A.C., Strauss, M., Tropp, J.A., Vershynin, R.: One sketch for all: fast algorithms for compressed sensing. In: Proceedings of the 39th ACM Symposium Theory of Computing (STOC), San Diego (2007)
83.
Glowinski, R., Le, T.: Augmented Lagrangian and Operator-Splitting Methods. SIAM, Philadelphia (1989)MATH
84.
Gluskin, E.: Norms of random matrices and widths of finite-dimensional sets. Math. USSR-Sb. 48, 173–182 (1984)MATH
85.
Goldfarb, D., Ma, S.: Convergence of fixed point continuation algorithms for matrix rank minimization. Found. Comput. Math. 11(2), 183–210 (2011)MATHMathSciNet
86.
Gorodnitsky, I., Rao, B.: Sparse signal reconstruction from limited data using FOCUSS: a re-weighted minimum norm algorithm. IEEE Trans. Signal Process. 45(3), 600–616 (1997)
87.
Gribonval, R., Nielsen, M.: Sparse representations in unions of bases. IEEE Trans. Inf. Theory 49(12), 3320–3325 (2003)MATHMathSciNet
88.
Gross, D.: Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inf. Theory 57(3), 1548–1566 (2011)
89.
Gross, D., Liu, Y.-K., Flammia, S.T., Becker, S., Eisert, J.: Quantum state tomography via compressed sensing. Phys. Rev. Lett. 105, 150401 (2010)
90.
Gross, D., Krahmer, F., Kueng, R.: Improved recovery guarantees for phase retrieval from coded diffraction patterns (2014, preprint)
91.
Gross, D., Krahmer, F., Kueng, R.: A partial derandomization of PhaseLift using spherical designs. J. Fourier Anal. Appl. (to appear)
92.
He, B., Yuan, X.: Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective. SIAM J. Imaging Sci. 5(1), 119–149 (2012)MATHMathSciNet
93.
Horn, R., Johnson, C.: Matrix Analysis. Cambridge University Press, Cambridge/New York (1990)MATH
94.
Hügel, M., Rauhut, H., Strohmer, T.: Remote sensing via l1-minimization. Found. Comput. Math. 14, 115–150 (2014)MATHMathSciNet
95.
Johnson, W.B., Lindenstrauss, J. (eds.): Handbook of the Geometry of Banach Spaces, vol. I. North-Holland, Amsterdam (2001)MATH
96.
Kashin, B.: Diameters of some finite-dimensional sets and classes of smooth functions. Math. USSR Izv. 11, 317–333 (1977)MATH
97.
Keshavan, R.H., Montanari, A., Oh, S.: Matrix completion from a few entries. IEEE Trans. Inf. Theory 56, 2980–2998 (2010)MathSciNet
98.
Keshavan, R.H., Montanari, A., Oh, S.: Matrix completion from noisy entries. J. Mach. Learn. Res. 11, 2057–2078 (2010)MATHMathSciNet
99.
Krahmer, F., Rauhut, H.: Structured random measurements in signal processing. GAMM Mitteilungen. (to appear)
100.
Krahmer, F., Ward, R.: New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property. SIAM J. Math. Anal. 43(3), 1269–1281 (2011)MATHMathSciNet
101.
Krahmer, F., Mendelson, S., Rauhut, H.: Suprema of chaos processes and the restricted isometry property. Commun. Pure Appl. Math. (to appear). doi:10.1002/cpa.21504
102.
Lawson, C.: Contributions to the theory of linear least maximum approximation. PhD thesis, University of California, Los Angeles (1961)
103.
Ledoux, M., Talagrand, M.: Probability in Banach Spaces. Springer, Berlin/New York (1991)MATH
104.
Lee, K., Bresler, Y.: ADMiRA: atomic decomposition for minimum rank approximation. IEEE Trans. Inf. Theory 56(9), 4402–4416 (2010)MathSciNet
105.
Li, X., Voroninski, V.: Sparse signal recovery from quadratic measurements via convex programming (2013). arXiv:1209.4785
106.
Logan, B.: Properties of high-pass signals. PhD thesis, Columbia University (1965)
107.
Lorentz, G.G., von Golitschek, M., Makovoz, Y.: Constructive Approximation: Advanced Problems. Springer, Berlin (1996)MATH
108.
Mallat, S.G., Zhang, Z.: Matching pursuits with time-frequency dictionaries. IEEE Trans. Signal Process. 41(12), 3397–3415 (1993)MATH
109.
Marple, S.: Digital Spectral Analysis with Applications. Prentice-Hall, Englewood Cliffs (1987)
110.
Mendelson, S., Pajor, A., Tomczak Jaegermann, N.: Uniform uncertainty principle for Bernoulli and subgaussian ensembles. Constr. Approx. 28(3), 277–289 (2009)MathSciNet
111.
Millane, R.: Phase retrieval in crystallography and optics. J. Opt. Soc. Am. A 7(3), 394–411 (1990)
112.
Mixon, D.: Short, fat matrices. Blog (2013)
113.
Mohan, K., Fazel, M.: Reweighted nuclear norm minimization with application to system identification. In: Proceedings of the American Control Conference, Baltimore, pp. 2953–2959 (2010)
114.
Natarajan, B.K.: Sparse approximate solutions to linear systems. SIAM J. Comput. 24, 227–234 (1995)MATHMathSciNet
115.
Nesterov, Y., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming. Volume 13 of SIAM Studies in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1994)
116.
Netrapalli, P., Jain, P., Sanghavi, S.: Phase retrieval using alternating minimization (2013). arXiv:1306.0160
117.
Novak, E.: Optimal recovery and n-widths for convex classes of functions. J. Approx. Theory 80(3), 390–408 (1995)MATHMathSciNet
118.
Ohlsson, H., Yang, A.Y., Dong, R., Sastry, S.S.: Nonlinear basis pursuit. In: 47th Asilomar Conference on Signals, Systems and Computers, Pacific Grove (2013)
119.
Osborne, M., Presnell, B., Turlach, B.: A new approach to variable selection in least squares problems. IMA J. Numer. Anal. 20(3), 389–403 (2000)MATHMathSciNet
120.
Osborne, M., Presnell, B., Turlach, B.: On the LASSO and its dual. J. Comput. Graph. Stat. 9(2), 319–337 (2000)MathSciNet
121.
Oymak, S., Mohan, K., Fazel, M., Hassibi, B.: A simplified approach to recovery conditions for low-rank matrices. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT), St. Petersburg (2011)
122.
Pfander, G.E., Rauhut, H.: Sparsity in time-frequency representations. J. Fourier Anal. Appl. 16(2), 233–260 (2010)MATHMathSciNet
123.
Pfander, G.E., Rauhut, H., Tanner, J.: Identification of matrices having a sparse representation. IEEE Trans. Signal Process. 56(11), 5376–5388 (2008)MathSciNet
124.
Pfander, G.E., Rauhut, H., Tropp, J.A.: The restricted isometry property for time-frequency structured random matrices. Probab. Theory Relat. Fields 156, 707–737 (2013)MATHMathSciNet
125.
Pock, T., Chambolle, A.: Diagonal preconditioning for first order primal-dual algorithms in convex optimization. In: IEEE International Conference Computer Vision (ICCV), Barcelona, pp. 1762–1769 (2011)
126.
Pock, T., Cremers, D., Bischof, H., Chambolle, A.: An algorithm for minimizing the Mumford-Shah functional. In: ICCV Proceedings, Kyoto. Springer (2009)
127.
Prony, R.: Essai expérimental et analytique sur les lois de la Dilatabilité des uides élastique et sur celles de la Force expansive de la vapeur de loeau et de la vapeur de l’alkool, à différentes températures. J. École Polytechnique 1, 24–76 (1795)
128.
Rauhut, H.: Random sampling of sparse trigonometric polynomials. Appl. Comput. Harmon. Anal. 22(1), 16–42 (2007)MATHMathSciNet
129.
Rauhut, H.: Stability results for random sampling of sparse trigonometric polynomials. IEEE Trans. Inf Theory 54(12), 5661–5670 (2008)MATHMathSciNet
130.
Rauhut, H.: Circulant and Toeplitz matrices in compressed sensing. In: Proceedings of the SPARS’09 (2009)
131.
Rauhut, H.: Compressive sensing and structured random matrices. In: Fornasier, M. (ed.) Theoretical Foundations and Numerical Methods for Sparse Recovery. Radon Series on Computational and Applied Mathematics, vol. 9, pp. 1–92. deGruyter, Berlin (2010). Papers based on the presentations of the summer school “Theoretical Foundations and Numerical Methods for Sparse Recovery”, Vienna, Austria, 31 Aug-4 Sept 2009
132.
Rauhut, H., Ward, R.: Interpolation via weighted l1 minimization (2013). ArXiv:1308.0759
133.
Rauhut, H., Romberg, J.K., Tropp, J.A.: Restricted isometries for partial random circulant matrices. Appl. Comput. Harmon. Anal. 32(2), 242–254 (2012)MATHMathSciNet
134.
Recht, B.: A simpler approach to matrix completion. J. Mach. Learn. Res. 12, 3413–3430 (2012)MathSciNet
135.
Recht, B., Fazel, M., Parrilo, P.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471–501 (2010)MATHMathSciNet
136.
Romberg, J.: Imaging via compressive sampling. IEEE Signal Process. Mag. 25(2), 14–20 (2008)
137.
Romberg, J.K.: Compressive sensing by random convolution. SIAM J. Imaging Sci. 2(4), 1098–1128 (2009)MATHMathSciNet
138.
Rudelson, M., Vershynin, R.: On sparse reconstruction from Fourier and Gaussian measurements. Commun. Pure Appl. Math. 61, 1025–1045 (2008)MATHMathSciNet
139.
Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60(1–4), 259–268 (1992)MATH
140.
Santosa, F., Symes, W.: Linear inversion of band-limited reflection seismograms. SIAM J. Sci. Stat. Comput. 7(4), 1307–1330 (1986)MATHMathSciNet
141.
Schnass, K., Vandergheynst, P.: Dictionary preconditioning for greedy algorithms. IEEE Trans. Signal Process. 56(5), 1994–2002 (2008)MathSciNet
142.
Starck, J.-L., Murtagh, F., Fadili, J.: Sparse Image and Signal Processing Wavelets, Curvelets, Morphological Diversity, xvii, p. 316. Cambridge University Press, Cambridge (2010)
143.
Strohmer, T., Heath, R.W., Jr.: Grassmannian frames with applications to coding and communication. Appl. Comput. Harmon. Anal. 14(3), 257–275 (2003)MATHMathSciNet
144.
Strohmer, T., Hermann, M.: Compressed sensing radar. In: IEEE Proceedings of the International Conference on Acoustic, Speech, and Signal Processing, Las Vegas, pp. 1509–1512 (2008)
145.
Tadmor, E.: Numerical methods for nonlinear partial differential equations. In: Meyers, R.A. (ed.) Encyclopedia of Complexity and Systems Science. Springer, New York/London (2009)
146.
147.
Tauböck, G., Hlawatsch, F., Eiwen, D., Rauhut, H.: Compressive estimation of doubly selective channels in multicarrier systems: leakage effects and sparsity-enhancing processing. IEEE J. Sel. Top. Signal Process. 4(2), 255–271 (2010)
148.
Taylor, H., Banks, S., McCoy, J.: Deconvolution with the ℓ 1-norm. Geophys. J. Int. 44(1), 39–52 (1979)
149.
Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B 58(1), 267–288 (1996)MATHMathSciNet
150.
Traub, J., Wasilkowski, G., Wo’zniakowski, H.: Information-Based Complexity. Computer Science and Scientific Computing. Academic, Boston (1988)MATH
151.
Tropp, J.A.: Greed is good: algorithmic results for sparse approximation. IEEE Trans. Inf. Theory 50(10), 2231–2242 (2004)MATHMathSciNet
152.
Tropp, J.A.: Just relax: convex programming methods for identifying sparse signals in noise. IEEE Trans. Inf. Theory 51(3), 1030–1051 (2006)MathSciNet
153.
Tropp, J., Needell, D.: CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harmon. Anal. 26(3), 301–321 (2009)MATHMathSciNet
154.
Tropp, J.A., Laska, J.N., Duarte, M.F., Romberg, J.K., Baraniuk, R.G.: Beyond nyquist: efficient sampling of sparse bandlimited signals. IEEE Trans. Inf. Theory 56(1), 520–544 (2010)MathSciNet
155.
Unser, M.: Sampling—50 years after Shannon. Proc. IEEE 88(4), 569–587 (2000)
156.
van den Berg, E., Friedlander, M.: Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31(2), 890–912 (2008)MATHMathSciNet
157.
158.
Wagner, G., Schmieder, P., Stern, A., Hoch, J.: Application of non-linear sampling schemes to cosy-type spectra. J. Biomol. NMR 3(5), 569 (1993)
159.
Willett, R., Marcia, R., Nichols, J.: Compressed sensing for practical optical imaging systems: a tutorial. Opt. Eng. 50(7), 072601–072601–13 (2011)
160.
Willett, R., Duarte, M., Davenport, M., Baraniuk, R.: Sparsity and structure in hyperspectral imaging: sensing, reconstruction, and target detection. IEEE Signal Proc. Mag. 31(1), 116–126 (2014)
Metadata
Title
Compressive Sensing
Authors
Massimo Fornasier
Holger Rauhut
Copyright Year
2015
Publisher
Springer New York
Book
Handbook of Mathematical Methods in Imaging

Print ISBN: 978-1-4939-0789-2

Electronic ISBN: 978-1-4939-0790-8

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-1-4939-0790-8_6

Premium Partner

    Image Credits