A simple proof of the restricted isometry property for random matrices. (English) Zbl 1177.15015
Summary: We give a simple technique for verifying the restricted isometry property (as introduced by E. Candès and T. Tao [IEEE Trans. Inf. Theory 51, No. 12, 4203–4215 (2005)]) for random matrices that underlies compressed sensing. Our approach has two main ingredients: (i) concentration inequalities for random inner products that have recently provided algorithmically simple proofs of the Johnson-Lindenstrauss lemma [W. B. Johnson and J. Lindenstrauss, Contemp. Math. 26, 189–206 (1984; Zbl 0539.46017)]; and (ii) covering numbers for finite-dimensional balls in Euclidean space. This leads to an elementary proof of the restricted isometry property and brings out connections between compressed sensing and the Johnson-Lindenstrauss lemma. As a result, we obtain simple and direct proofs of Kashin’s theorems on widths of finite balls in Euclidean space [B. S. Kashin, Izv. Akad. Nauk SSSR, Ser. Mat. 41, 334–351 (1977; Zbl 0354.46021)] (and their improvements due to Gluskin [A. Garnaev and E. D. Gluskin, Sov. Math., Dokl. 30, 200–204 (1984); translation from Dokl. Akad. Nauk SSSR 277, 1048–1052 (1984; Zbl 0588.41022)]) and proofs of the existence of optimal compressed sensing measurement matrices. In the process, we also prove that these measurements have a certain universality with respect to the sparsity-inducing basis.
MSC:
| 15A22 | Matrix pencils |
| 60F10 | Large deviations |
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 94A20 | Sampling theory in information and communication theory |
References:
| [1] | Achlioptas, D.: Database-friendly random projections. In: Proc. ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, pp. 274–281, 2001 |
| [2] | Candès, E., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489–509 (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083 |
| [3] | Candès, E., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207–1223 (2005) · Zbl 1098.94009 · doi:10.1002/cpa.20124 |
| [4] | Candès, E., Tao, T.: Decoding by linear programing. IEEE Trans. Inf. Theory 51(12), 4203–4215 (2005) · Zbl 1264.94121 · doi:10.1109/TIT.2005.858979 |
| [5] | Cohen, A., Dahmen, W., DeVore, R.: Compressed sensing and best k-term approximation. Preprint (2006) · Zbl 1206.94008 |
| [6] | Cohen, A., Dahmen, W., DeVore, R.: Near optimal approximation of arbitrary signals from highly incomplete measurements. Preprint (2007) |
| [7] | Dasgupta, S., Gupta, A.: An elementary proof of the Johnson–Lindenstrauss lemma. Tech. Report Technical report 99-006, U.C. Berkeley (March, 1999) |
| [8] | Donoho, D.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289–1306 (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582 |
| [9] | Frankl, P., Maehara, H.: The Johnson–Lindenstrauss lemma and the sphericity of some graphs. J. Comb. Theory Ser. B 44(3), 355–362 (1988) · Zbl 0675.05049 · doi:10.1016/0095-8956(88)90043-3 |
| [10] | Gilbert, A., Guha, S., Indyk, P., Muthukrishnan, S., Strauss, M.: Near-optimal sparse Fourier representations via sampling, 2005. In: ACM Symp. on Theoretical Computer Science, 2002 · Zbl 1192.94078 |
| [11] | Garnaev, A., Gluskin, E.D.: The widths of Euclidean balls. Dokl. An. SSSR 277, 1048–1052 (1984) · Zbl 0588.41022 |
| [12] | Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Symp. on Theory of Computing, pp. 604–613, 1998 · Zbl 1029.68541 |
| [13] | 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 |
| [14] | Kashin, B.: The widths of certain finite dimensional sets and classes of smooth functions. Izvestia (41), 334–351 (1977) |
| [15] | Ledoux, M.: The Concentration of Measure Phenomenon. Am. Math. Soc., Providence (2001) · Zbl 0995.60002 |
| [16] | Lorentz, G.G., von Golitschek, M., Makovoz, Yu.: Constructive Approximation: Advanced Problems, vol. 304. Springer, Berlin (1996) · Zbl 0910.41001 |
| [17] | Milman, V.D., Pajor, A.: Regularization of star bodies by random hyperplane cut off. Studia Math. 159(2), 247–261 (2003) · Zbl 1076.46008 · doi:10.4064/sm159-2-6 |
| [18] | Milman, V.D., Schechtman, G.: Asymptotic Theory of Finite-Dimensional Normed Spaces. Lecture Notes in Mathematics, vol. 1200. Springer, Berlin (1986) · Zbl 0606.46013 |
| [19] | Mendelson, S., Pajor, A., Tomczack-Jaegermann, N.: Reconstruction and subgaussian operators in asymptotic geometric analysis. Preprint (2006) · Zbl 1163.46008 |
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.
