6
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Please see the recent article for properties, generalization and usefulness of the RIP in Compressed Sensing... arxiv.org/abs/1410.1956 $\endgroup$ – Oliver Jul 17 '15 at 12:47
7
$\begingroup$

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.

$\endgroup$
  • 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$ – Oliver Jul 17 '15 at 12:49
  • $\begingroup$ Should the given property hold for any sub-matrix of $A$ ? $\endgroup$ – Dilawar Aug 30 '17 at 6:19
  • $\begingroup$ can one check the RIP property for a concrete matrix in practice with an algorithm? $\endgroup$ – Charlie Parker Mar 31 '18 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$ – Thomas Arildsen Mar 31 '18 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.