Restricted isometry property explained

In linear algebra, the restricted isometry property (RIP) characterizes matrices which are nearly orthonormal, at least when operating on sparse vectors. The concept was introduced by Emmanuel Candès and Terence Tao^[1] and is used to prove many theorems in the field of compressed sensing.^[2] There are no known large matrices with bounded restricted isometry constants (computing these constants is strongly NP-hard,^[3] and is hard to approximate as well^[4]), but many random matrices have been shown to remain bounded. In particular, it has been shown that with exponentially high probability, random Gaussian, Bernoulli, and partial Fourier matrices satisfy the RIP with number of measurements nearly linear in the sparsity level.^[5] The current smallest upper bounds for any large rectangular matrices are for those of Gaussian matrices.^[6] Web forms to evaluate bounds for the Gaussian ensemble are available at the Edinburgh Compressed Sensing RIC page.^[7]

Definition

Let A be an m × p matrix and let 1 ≤ s ≤ p be an integer. Suppose that there exists a constant

\delta _{s} \in ( 0 , 1 ) such that, for every m × s submatrix A_s of A and for every s-dimensional vector y,( 1- \delta _{s)\|y\|} ^{2} ^{2} \le \|A _{s} y\| ^{2} _{2} \le ( 1+ \delta _{s)\|y\|} ^{2 .} ^{2}

Then, the matrix A is said to satisfy the s-restricted isometry property with restricted isometry constant

\delta _{s} .

This condition is equivalent to the statement that for every m × s submatrix A_s of A we have

\|A ^{*} _{sA} _{s} - I _{s} \| _{2\to2} \le \delta _{s,}

where

I _{s} is the s x s identity matrix and \|X\| _{2\to2} is the operator norm. See for example ^[8] for a proof.

Finally this is equivalent to stating that all eigenvalues of

A ^{*} _{sA} _{s} are in the interval [ 1- \delta _{s,} 1+ \delta _{s]} .

Restricted Isometric Constant (RIC)

The RIC Constant is defined as the infimum of all possible

\delta for a given A \in R ^{n} .\delta _{K} = inf \left[ \delta : ( 1- \delta)\|y\| ^{2} _{2} \le \|A _{s} y\| ^{2} _{2} \le ( 1+ \delta)\|y\| ^{2} _{2} \right], \forall |s| \le K, \forall y \in R ^{|s|} It is denoted as \delta _{K} .

Eigenvalues

For any matrix that satisfies the RIP property with a RIC of

\delta _{K} , the following condition holds:^[1] 1 - \delta _{K} \le λ _{min} (A ^{*A} _{\tau)} \le λ _{max} (A ^{*A} _{\tau)} \le 1+ \delta _{K} .

The tightest upper bound on the RIC can be computed for Gaussian matrices. This can be achieved by computing the exact probability that all the eigenvalues of Wishart matrices lie within an interval.

See also

• Compressed sensing
• Mutual coherence (linear algebra)
• Terence Tao's website on compressed sensing lists several related conditions, such as the 'Exact reconstruction principle' (ERP) and 'Uniform uncertainty principle' (UUP)^[9]
• Nullspace property, another sufficient condition for sparse recovery
• Generalized restricted isometry property,^[10] a generalized sufficient condition for sparse recovery, where mutual coherence and restricted isometry property are both its special forms.
• Johnson-Lindenstrauss lemma

Notes and References

1. E. J. Candes and T. Tao, "Decoding by Linear Programming," IEEE Trans. Inf. Th., 51(12): 4203 - 4215 (2005).
2. E. J. Candes, J. K. Romberg, and T. Tao, "Stable Signal Recovery from Incomplete and Inaccurate Measurements," Communications on Pure and Applied Mathematics, Vol. LIX, 1207–1223 (2006).
3. A. M. Tillmann and M. E. Pfetsch, "The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing," IEEE Trans. Inf. Th., 60(2): 1248 - 1259 (2014)
4. Abhiram Natarajan and Yi Wu, "Computational Complexity of Certifying Restricted Isometry Property," Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) (2014)
5. F. Yang, S. Wang, and C. Deng, "Compressive sensing of image reconstruction using multi-wavelet transform", IEEE 2010
6. B. Bah and J. Tanner "Improved Bounds on Restricted Isometry Constants for Gaussian Matrices"
7. Web site: Edinburgh University - School of Mathematics - Compressed Sensing Group - Restricted Isometry Constants . 2010-03-31 . https://web.archive.org/web/20100427085437/http://ecos.maths.ed.ac.uk/ric_bounds.shtml . 2010-04-27 . dead .
8. Web site: A Mathematical Introduction to Compressive Sensing. Cis.pku.edu.cn. 15 May 2018.
9. Web site: Compressed sensing. Math.ucla.edu. 15 May 2018.
10. 1408.6890. On Linear Convergence of Adaptively Iterative Thresholding Algorithms for Compressed Sensing. IEEE Transactions on Signal Processing. 63. 11. 2957–2971. Yu Wang, Jinshan Zeng, Zhimin Peng, Xiangyu Chang and Zongben Xu. 10.1109/TSP.2015.2412915. 2015. 2015ITSP...63.2957W. 10734058.