What is the meaning of Restricted Isometry Property (RIP) condition in Compressive Sensing for Sparse Signal Analysis? How can we define Restricted Isometry Constant (RIC) for the RIP condition?
Thanks in Advance!
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Please see the recent article for properties, generalization and usefulness of the RIP in Compressed Sensing... arxiv.org/abs/1410.1956 $\endgroup$– OliverJul 17, 2015 at 12:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
The restricted isometry property states that: $$\begin{equation} (1-\delta_S)||x||_2^2 \le ||A x||_2^2 \le (1+\delta_S)||x||_2^2 \end{equation}$$ for any $S$-sparse vector $x$. The restricted isometry constant is $\delta_S$, $0 < \delta_S < 1$.
This means that the matrix $A$ is guaranteed to only change the length of any vector $x$ "very little" as long as the vector $x$ is at least $S$-sparse (has at most $S$ non-zero coefficients).
Suppose we have arbitrary $\frac{S}{2}$-sparse vectors $x$. In order to be able to reconstruct such vectors in general, from measurements taken as $y = A x$, we need to be sure that it is possible to distinguish between measurements $y_1 = A x_1$ and $y_2 = A x_2$ of any two such vectors. If $y_1 = y_2$ for any two such vectors $x_1$ and $x_2$, we would not be able to distinguish them and reconstruct them unambigously. Therefore we need to make sure that measurements of any two $\frac{S}{2}$-sparse vectors are "sufficiently different".
If we calculate the difference between any two $\frac{S}{2}$-sparse vectors, their difference can be at most $S$-sparse. So for reconstructing any $\frac{S}{2}$-sparse vector correctly from measurements taken with $A$, the restricted isometry property quantifies how well $A$ lets us do that (the smaller $\delta_S$, the better).
For an early introduction to compressed sensing and the restricted isometry property (and other concepts), see Candès & Wakin, 2008.
-
1$\begingroup$ Let us also note that the constant $\delta_{S}$ need not be the same on both sides, e.g. Gaussian sensing matrix. Please see the recent article. arxiv.org/abs/1410.1956 $\endgroup$– OliverJul 17, 2015 at 12:49
-
$\begingroup$ Should the given property hold for any sub-matrix of $A$ ? $\endgroup$– DilawarAug 30, 2017 at 6:19
-
$\begingroup$ can one check the RIP property for a concrete matrix in practice with an algorithm? $\endgroup$ Mar 31, 2018 at 18:41
-
1$\begingroup$ @CharlieParker no unfortunately not. It involves calculating the SVD of all possible $S$-column sub-matrices of $A$. This quickly becomes an unrealistic number of combinations to calculate even for modest-sized $A$. And, remember that compressive sensing works better the larger the sizes of $A$ and $x$. $\endgroup$ Mar 31, 2018 at 20:12