Theory of Compressive Sensing via ℓ 1-Minimization: a Non-RIP Analysis and Extensions
Tóm tắt
Compressive sensing (CS) is an emerging methodology in computational signal processing that has recently attracted intensive research activities. At present, the basic CS theory includes recoverability and stability: the former quantifies the central fact that a sparse signal of length n can be exactly recovered from far fewer than n measurements via ℓ
1-minimization or other recovery techniques, while the latter specifies the stability of a recovery technique in the presence of measurement errors and inexact sparsity. So far, most analyses in CS rely heavily on the Restricted Isometry Property (RIP) for matrices. In this paper, we present an alternative, non-RIP analysis for CS via ℓ
1-minimization. Our purpose is three-fold: (a) to introduce an elementary and RIP-free treatment of the basic CS theory; (b) to extend the current recoverability and stability results so that prior knowledge can be utilized to enhance recovery via ℓ
1-minimization; and (c) to substantiate a property called uniform recoverability of ℓ
1-minimization; that is, for almost all random measurement matrices recoverability is asymptotically identical. With the aid of two classic results, the non-RIP approach enables us to quickly derive from scratch all basic results for the extended theory.
Tài liệu tham khảo
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)
Barvinok, A.: Math 710: Measure Concentration. Lecture Notes, Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1109
Candès, E.: The restricted isometry property and its implications for compressed sensing. C. R. Math. 346, 589–592 (2008)
Candès, E.: Compressive sampling. In: International Congress of Mathematicians, Madrid, Spain, August 22–30, 2006, 3, 1433–1452. Eur. Math. Soc., Zurich (2006)
Candès, E., Tao, T.: Near optimal signal recovery from random projections: universal encoding strategies. IEEE Trans. Inf. Theory 52, 5406–5425 (2006)
Candès, E., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51, 4203–4215 (2005)
Candès, E., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate information. Commun. Pure Appl. Math. 2005, 1207–1233 (2005)
Candès, E., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52, 489–509 (2006)
Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20, 33–61 (1998)
Cohen, A., Dahmen, W., DeVore, R.A.: Compressed sensing and best k-term approximation. J. Am. Math. Soc. 22, 211–231 (2009)
Donoho, D.: Compressed sensing. IEEE Trans. Inf. Theory 52, 1289–1306 (2006)
Donoho, D., Elad, M.: Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization. Proc. Natl. Acad. Sci. USA 100, 2197–2202 (2003)
Donoho, D., Tanner, J.: Counting faces of randomly-projected polytopes when the projection radically lowers dimension. Manuscript arXiv:math/0607364v2 [math.MG] (2006)
Donoho, D., Tanner, J.: Sparse nonnegative solutions of underdetermined linear equations by linear programming. Proc. Natl. Acad. Sci. USA 102(27), 9446–9451 (2005)
Donoho, D., Tsaig, Y.: Extensions of compressed sensing. Signal Process. 86(3), 533–548 (2006)
Eydelzon, A.: A study on conditions for sparse solution recovery in compressive sensing. Ph.D. Thesis, Rice University, CAAM technical report TR07-12 (2007)
Garnaev, A., Gluskin, E.D.: The widths of a Euclidean ball. Dokl. Akad. Nauk SSSR 277, 1048–1052 (1984)
Girko, V.L.: A refinement of the central limit theorem for random determinants. Theory Probab. Appl. 42(1), 21–129 (1998) (translated from a Teor. Veroâtn. Ee Primen.)
Girko, V.L.: Theory of Random Determinants. Kluwer Academic, Dordrecht (1990)
Gluskin, E., Milman, V.: Note on the geometric-arithmetic mean inequality. In: Geometric Aspects of Functional Analysis Israel Seminar 2001–2002. Lecture Notes in Mathematics, 1807, 131–135. Springer, Berlin (2003)
Kashin, B.S.: Diameters of certain finite-dimensional sets in classes of smooth functions. Izv. Akad. Nauk SSSR, Ser. Mat. 41, 334–351 (1977)
Lustig, M., Donoho, D., Santos, J., Pauly, J.: Compressed sensing MRI. IEEE Signal Process. Mag. 25, 72–82 (2008)
Milman, V.D., Schechtman, G.: Asymptotic Theory of Finite Dimensional Normed Spaces, with an Appendix by M. Gromov. Lecture Notes in Mathematics, vol. 1200. Springer, Berlin (2001)
Needell, D., Tropp, J.A.: CoSaMP: Iterative signal recovery from incomplete and inaccurate samples (2008). arXiv:0803.2392v2
Needell, D., Vershynin, R.: Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit. IEEE J. Sel. Top. Signal Process. 4, 310–316 (2010)
Rudelson, M., Vershynin, R.: Geometric approach to error correcting codes and reconstruction of signals. Int. Math. Res. Not. 64, 4019–4041 (2005)
Santosa, F., Symes, W.: Linear inversion of band-limited reflection histograms. SIAM J. Sci. Stat. Comput. 7, 1307–1330 (1986)
Tropp, J.A., Gilbert, A.C.: Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans. Inf. Theory 53(12), 4655–4666 (2007)
Vavasis, S.: Derivation of compressive sensing theorems for the spherical section property. University of Waterloo, CO 769 Lecture Notes (2009)
Zhang, Y.: A simple proof for recoverability of ℓ 1-minimization: go over or under? Rice University CAAM technical report TR05-09 (2005)
Zhang, Y.: A simple proof for recoverability of ℓ 1-minimization (II): the nonnegativity case. Rice University CAAM technical report TR05-10 (2005)
Compressive Sensing Resources. http://www.dsp.ece.rice.edu/cs