Computer Science – Information Theory
Scientific paper
2011-03-16
Computer Science
Information Theory
41 Pages, 3 Figures. Submitted to IEEE Transactions on Information Theory
Scientific paper
Compressed Sensing (CS) is an emerging field that enables reconstruction of a sparse signal $x \in {\mathbb R} ^n$ that has only $k \ll n$ non-zero coefficients from a small number $m \ll n$ of linear projections. The projections are obtained by multiplying $x$ by a matrix $\Phi \in {\mathbb R}^{m \times n}$ --- called a CS matrix --- where $k < m \ll 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 R}^{m \times 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 R}^{m \times 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 $\Phi$ 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).
Baraniuk Richard G.
Sarvotham Shriram
No associations
LandOfFree
Deterministic Bounds for Restricted Isometry of Compressed Sensing Matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Deterministic Bounds for Restricted Isometry of Compressed Sensing Matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic Bounds for Restricted Isometry of Compressed Sensing Matrices will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-247349