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 and is used to prove many theorems in the field of compressed sensing. There are no known large matrices with bounded restricted isometry constants (computing these constants is strongly NP-hard, and is hard to approximate as well), 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. The current smallest upper bounds for any large rectangular matrices are for those of Gaussian matrices. Web forms to evaluate bounds for the Gaussian ensemble are available at the Edinburgh Compressed Sensing RIC page.
Definition Let A be an m × p matrix and let 1 ≤ s ≤ p be an integer. Suppose that there exists a constant δ s ∈ ( 0 , 1 ) {\displaystyle \delta _{s}\in (0,1)} such that, for every m × s submatrix As of A and for every s-dimensional vector y,
( 1 − δ s ) ‖ y ‖ 2 2 ≤ ‖ A s y ‖ 2 2 ≤ ( 1 + δ s ) ‖ y ‖ 2 2 . {\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 δ s {\displaystyle \delta _{s}} . This condition is equivalent to the statement that for every m × s submatrix As of A we have
‖ A s ∗ A s − I s × s ‖ 2 → 2 ≤ δ s , {\displaystyle \|A_{s}^{*}A_{s}-I_{s\times s}\|_{2\to 2}\leq \delta _{s},}
where I s × s {\displaystyle I_{s\times s}} is the s × s {\displaystyle s\times s} identity matrix and ‖ X ‖ 2 → 2 {\displaystyle \|X\|_{2\to 2}} is the operator norm. See for example for a proof. Finally this is equivalent to stating that all eigenvalues of A s ∗ A s {\displaystyle A_{s}^{*}A_{s}} are in the interval [ 1 − δ s , 1 + δ s ] {\displaystyle [1-\delta _{s},1+\delta _{s}]} .
Restricted Isometric Constant (RIC) The RIC Constant is defined as the infimum of all possible δ {\displaystyle \delta } for a given A ∈ R n × m {\displaystyle A\in \mathbb {R} ^{n\times m}} .
δ K = inf [ δ : ( 1 − δ ) ‖ y ‖ 2 2 ≤ ‖ A s y ‖ 2 2 ≤ ( 1 + δ ) ‖ y ‖ 2 2 ] , ∀ | s | ≤ K , ∀ y ∈ R | s | {\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 δ K {\displaystyle \delta _{K}} .
Eigenvalues For any matrix that satisfies the RIP property with a RIC of δ K {\displaystyle \delta _{K}} , the following condition holds:
… excerpt ends here. Continue reading the full article.
