Inlinear algebra, therestricted isometry property (RIP) characterizesmatrices which are nearly orthonormal, at least when operating on sparse vectors. The concept was introduced byEmmanuel Candès andTerence Tao^[1] and is used to prove many theorems in the field ofcompressed sensing.^[2] There are no known large matrices with bounded restricted isometry constants (computing these constants isstrongly 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]

LetA be anm × p matrix and let1 ≤ s ≤ p be an integer. Suppose that there exists a constant${\displaystyle {\delta }_s\in (0,1)}$ such that, for everym × s submatrixA_s ofA and for everys-dimensional vector y,

${\displaystyle (1-{\delta }_s)\Vert y{\Vert }_2^2\le \Vert A_{s}y{\Vert }_2^2\le (1+{\delta }_s)\Vert y{\Vert }_2^2.}$

Then, the matrixA is said to satisfy thes-restricted isometry property with restricted isometry constant${\displaystyle {\delta }_s}$.

This condition is equivalent to the statement that for everym × s submatrixA_s ofA we have

${\displaystyle \Vert A_s^{\ast }{A}_s-I_{s\times s}{\Vert }_{2\to 2}\le {\delta }_s,}$

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

Finally this is equivalent to stating that alleigenvalues of${\displaystyle A_s^{\ast }{A}_s}$ are in the interval${\displaystyle [1-{\delta }_s,1+{\delta }_s]}$.

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

${\displaystyle {\delta }_K=inf\left[\delta :(1-\delta )\Vert y{\Vert }_2^2\le \Vert A_{s}y{\Vert }_2^2\le (1+\delta )\Vert y{\Vert }_2^2\right],\mathrm{\forall }|s|\le K,\mathrm{\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\le {\lambda }_{min}(A_{\tau }^{\ast }{A}_{\tau })\le {\lambda }_{max}(A_{\tau }^{\ast }{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.

• 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, wheremutual coherence andrestricted isometry property are both its special forms.
• Johnson-Lindenstrauss lemma

• Signal processing
• Linear algebra

• CS1 maint: multiple names: authors list
• Articles with short description
• Short description matches Wikidata