restricted isometry property

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

:$(1-\backslash delta\_s)\backslash |y\backslash |\_\{2\}^2\; \backslash le\; \backslash |A\_s\; y\backslash |\_\{2\}^2\; \backslash le\; (1+\backslash delta\_s)\backslash |y\backslash |\_\{2\}^2.\; \backslash ,$

Then, the matrix A is said to satisfy the s-restricted isometry property with restricted isometry constant $\backslash delta\_s$.

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

:$\backslash |A^*\_sA\_s\; -\; I\_\{s\; \backslash times\; s\}\backslash |\_\{2\backslash to2\}\; \backslash le\; \backslash delta\_s,$

where $I\_\{s\; \backslash times\; s\}$ is the $s\; \backslash times\; s$ identity matrix and $\backslash |X\backslash |\_\{2\backslash to2\}$ is the operator norm. See for example {{cite web|url=http://www.cis.pku.edu.cn/faculty/vision/zlin/A%20Mathematical%20Introduction%20to%20Compressive%20Sensing.pdf|title=A Mathematical Introduction to Compressive Sensing|website=Cis.pku.edu.cn|accessdate=15 May 2018}} for a proof.

Finally this is equivalent to stating that all eigenvalues of $A^*\_sA\_s$ are in the interval $[1-\backslash delta\_s,\; 1+\backslash delta\_s]$.

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

:$\backslash delta\_K\; =\; \backslash inf\; \backslash left[\; \backslash delta\; :\; (1-\backslash delta)\backslash |y\backslash |\_2^2\; \backslash le\; \backslash |A\_s\; y\backslash |\_2^2\; \backslash le\; (1+\backslash delta)\backslash |y\backslash |\_2^2\; \backslash right],\backslash \; \backslash forall\; |s|\; \backslash le\; K,\; \backslash forall\; y\; \backslash in\; R^$

s

It is denoted as $\backslash delta\_K$.

For any matrix that satisfies the RIP property with a RIC of $\backslash delta\_K$, the following condition holds:

:$1\; -\; \backslash delta\_K\; \backslash le\; \backslash lambda\_\{min\}\; (A\_\backslash tau^*A\_\backslash tau)\; \backslash le\; \backslash lambda\_\{max\}(A\_\backslash tau^*A\_\backslash tau)\; \backslash le\; 1+\backslash 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){{cite web|url=https://www.math.ucla.edu/~tao/preprints/sparse.html|title=Compressed sensing|website=Math.ucla.edu|accessdate=15 May 2018}}
• Nullspace property, another sufficient condition for sparse recovery
• Generalized restricted isometry property,{{cite journal

|arxiv = 1408.6890|title = On Linear Convergence of Adaptively Iterative Thresholding Algorithms for Compressed Sensing

|journal = IEEE Transactions on Signal Processing

|volume = 63

|issue = 11

|pages = 2957–2971

|author = Yu Wang, Jinshan Zeng, Zhimin Peng, Xiangyu Chang and Zongben Xu

|doi = 10.1109/TSP.2015.2412915

|year = 2015

|bibcode = 2015ITSP...63.2957W

|s2cid = 10734058

}} a generalized sufficient condition for sparse recovery, where mutual coherence and restricted isometry property are both its special forms.

• Johnson-Lindenstrauss lemma

{{Reflist}}

Category:Signal processing

Category:Linear algebra