Abstract
We give a simple technique for verifying the Restricted Isometry Property (as introduced by Candès and Tao) 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; 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 (and their improvements due to Gluskin) 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.
Similar content being viewed by others
References
Achlioptas, D.: Database-friendly random projections. In: Proc. ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, pp. 274–281, 2001
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)
Candès, E., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207–1223 (2005)
Candès, E., Tao, T.: Decoding by linear programing. IEEE Trans. Inf. Theory 51(12), 4203–4215 (2005)
Cohen, A., Dahmen, W., DeVore, R.: Compressed sensing and best k-term approximation. Preprint (2006)
Cohen, A., Dahmen, W., DeVore, R.: Near optimal approximation of arbitrary signals from highly incomplete measurements. Preprint (2007)
Dasgupta, S., Gupta, A.: An elementary proof of the Johnson–Lindenstrauss lemma. Tech. Report Technical report 99-006, U.C. Berkeley (March, 1999)
Donoho, D.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289–1306 (2006)
Frankl, P., Maehara, H.: The Johnson–Lindenstrauss lemma and the sphericity of some graphs. J. Comb. Theory Ser. B 44(3), 355–362 (1988)
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
Garnaev, A., Gluskin, E.D.: The widths of Euclidean balls. Dokl. An. SSSR 277, 1048–1052 (1984)
Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Symp. on Theory of Computing, pp. 604–613, 1998
Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. In: Conf. in Modern Analysis and Probability, pp. 189–206, 1984
Kashin, B.: The widths of certain finite dimensional sets and classes of smooth functions. Izvestia (41), 334–351 (1977)
Ledoux, M.: The Concentration of Measure Phenomenon. Am. Math. Soc., Providence (2001)
Lorentz, G.G., von Golitschek, M., Makovoz, Yu.: Constructive Approximation: Advanced Problems, vol. 304. Springer, Berlin (1996)
Milman, V.D., Pajor, A.: Regularization of star bodies by random hyperplane cut off. Studia Math. 159(2), 247–261 (2003)
Milman, V.D., Schechtman, G.: Asymptotic Theory of Finite-Dimensional Normed Spaces. Lecture Notes in Mathematics, vol. 1200. Springer, Berlin (1986)
Mendelson, S., Pajor, A., Tomczack-Jaegermann, N.: Reconstruction and subgaussian operators in asymptotic geometric analysis. Preprint (2006)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Emmanuel J. Candès.
Rights and permissions
About this article
Cite this article
Baraniuk, R., Davenport, M., DeVore, R. et al. A Simple Proof of the Restricted Isometry Property for Random Matrices. Constr Approx 28, 253–263 (2008). https://doi.org/10.1007/s00365-007-9003-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00365-007-9003-x