0
$\begingroup$

I have been looking for the origin of the restricted isometry property (RIP). Many papers cite the origin of the RIP in the following paper

but I cannot understand where the definition came from. Some others papers say that the RIP is very similar to the Johnson-Lindenstrauss lemma (JL), and in fact it is, but I am not sure that that it is the origin of the RIP. However, I haven't been able to find this origin, mathematically.

On the other hand, how can the RIP be proved with certain matrices? Let's say for example Gaussian matrices or a Fourier matrix?

|improve this question
$\endgroup$
  • $\begingroup$ To address your 2nd question. Proving that a matrix satisfies the RIP is an NP hard problem. You would have to enumerate the possibilities and test them. For a Gaussian matrix, it can be shown that it satisfies the RIP with a high probability, $\endgroup$ – David Feb 19 at 13:06
  • $\begingroup$ @David can you explain me how it can be shown that a Gaussian Matrix satisfies the RIP with high probability. You can send me the paper if you are able and want to. $\endgroup$ – Lord Feb 19 at 13:26
  • 1
    $\begingroup$ The reference I have is: R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, “A simpleproof of the restricted isometry property for random matrices,” Constructive Approximation, vol. 28, no. 3, pp. 253–263, 2008.Link here $\endgroup$ – David Feb 19 at 16:35

Your Answer

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

Browse other questions tagged or ask your own question.