2011/03/16 by Shriram Sarvotham, Richard G. Baraniuk, Sarvotham, Shriram +1
Computer Science · Engineering · Mathematics · #Blind Source Separation Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Mathematical Analysis and Transform Methods #Sparse and Compressive Sensing Techniques #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1103.3316
41 Pages, 3 Figures. Submitted to IEEE Transactions on Information Theory
openalex publication_date 2011/03/16 · arxiv created 2011/03/27 · arxiv updated 2011/03/29 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
Compressed Sensing (CS) is an emerging field that enables reconstruction of a sparse signal x ∈ \mathbb R n that has only k ≪ n non-zero coefficients from a small number m ≪ n of linear projections. The projections are obtained by multiplying x by a matrix Φ∈ \mathbb Rm × n --- called a CS matrix --- where k < m ≪ n. In this work, we ask the following question: given the triplet \k, m, n \ that defines the CS problem size, what are the deterministic limits on the performance of the best CS matrix in \mathbb Rm × n? We select Restricted Isometry as the performance metric. We derive two deterministic converse bounds and one deterministic achievable bound on the Restricted Isometry for matrices in \mathbb Rm × n in terms of n, m and k. The first converse bound (structural bound) is derived by exploiting the intricate relationships between the singular values of sub-matrices and the complete matrix. The second converse bound (packing bound) and the achievable bound (covering bound) are derived by recognizing the equivalence of CS matrices to codes on Grassmannian spaces. Simulations reveal that random Gaussian Φ provide far from optimal performance. The derivation of the three bounds offers several new geometric insights that relate optimal CS matrices to equi-angular tight frames, the Welch bound, codes on Grassmannian spaces, and the Generalized Pythagorean Theorem (GPT).