Restricted isometry property

Let A be an m × p matrix and let 1 ≤ s ≤ p be an integer. Suppose that there exists a constant ${\displaystyle \delta _{s}\in (0,1)}$ such that, for every m × s submatrix A_s of A and for every s-dimensional vector y,

${\displaystyle (1-\delta _{s})\|y\|_{2}^{2}\leq \|A_{s}y\|_{2}^{2}\leq (1+\delta _{s})\|y\|_{2}^{2}.\,}$

Then, the matrix A is said to satisfy the s-restricted isometry property with restricted isometry constant ${\displaystyle \delta _{s}}$.

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

${\displaystyle \|A_{s}^{*}A_{s}-I_{s\times s}\|_{2\to 2}\leq \delta _{s},}$

where ${\displaystyle I_{s\times s}}$ is the ${\displaystyle s\times s}$ identity matrix and ${\displaystyle \|X\|_{2\to 2}}$ is the operator norm. See for example ^[8] for a proof.

Finally this is equivalent to stating that all eigenvalues of ${\displaystyle A_{s}^{*}A_{s}}$ are in the interval ${\displaystyle [1-\delta _{s},1+\delta _{s}]}$.

The RIC Constant is defined as the infimum of all possible ${\displaystyle \delta }$ for a given ${\displaystyle A\in \mathbb {R} ^{n\times m}}$.

${\displaystyle \delta _{K}=\inf \left[\delta :(1-\delta )\|y\|_{2}^{2}\leq \|A_{s}y\|_{2}^{2}\leq (1+\delta )\|y\|_{2}^{2}\right],\ \forall |s|\leq K,\forall y\in R^{|s|}}$

It is denoted as ${\displaystyle \delta _{K}}$.

For any matrix that satisfies the RIP property with a RIC of ${\displaystyle \delta _{K}}$, the following condition holds:^[1]

${\displaystyle 1-\delta _{K}\leq \lambda _{min}(A_{\tau }^{*}A_{\tau })\leq \lambda _{max}(A_{\tau }^{*}A_{\tau })\leq 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.

• 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