1
$\begingroup$

Let $x$ be a $N \times 1$ vector in $\mathbb{R}^{N}$ where $M$ components are zero and the remaining $N-M$ components are standard normal random variables. $x$ may not be sparse e.g. $M$ may be small.

I am interested in bounding $||Ax||_{l_{2}}$ where $A$ is a $K \times N$ matrix $(K<N)$.

This made me think to look for a restricted isometry like property. So my question is are there a class of $K \times N$ matrices $(K<N)$ such that $(1-\delta) ||x||_{l_{2}} \le ||Ax||_{l_{2}} \le (1+\delta) ||x||_{l_{2}}$ with probability $\ge p$ for some prescribed $\delta>0$ and $0<p<1$ ?

$\endgroup$

1 Answer 1

1
$\begingroup$

The $\delta$ constants in the RIP-2 property depend on the number of non-zero entries of $x$, so if the support of $x$ is of fixed size $N-M$, you loose the liberty of prescribing a $\delta$. In this sense, the answer would be: no.

Now, as the RIP-2 property is a statement over all $N-M$-sparse vectors, so if $M$ is small, the $\delta$ constants are likely to grow with $N$, and would provide extremely low-quality bounds.

$\endgroup$
3
  • $\begingroup$ I only require that RIP be satisfied with a high probability and not for every $x$. So the $\delta$ may not be too large. Are there any formal results too show this? $\endgroup$
    – Mykie
    Jun 25, 2013 at 17:53
  • $\begingroup$ To the best of my knowledge, no. The probabilistic guarantees in the RIP property concern the distribution of the sensing matrix $A$, and not of the vector $x$. However, Fourier, Gaussian, and Bernoulli matrices are known to satisfy RIP with high probability, but again, if the support $x$ is large, $\delta$ will be too. $\endgroup$
    – rodms
    Jun 26, 2013 at 12:48
  • $\begingroup$ Is it the $\delta$ dependent on sparsity, or the probability $p$, as far as I know, it should be the probability $p$ that depends on sparsity as well as $\delta$, though that does not prevent the matrix to satisfy the RIP property, just the no. of rows of the matrix has to satisfy some bound of that depends on the sparsity of the unknown vector. So, in that sense I think the answer is yes, most of the random linear mappings with i.i.d. entries will satisfy the RIP property, of course with conditions on $N-M$ and $K$ $\endgroup$ Jul 28, 2016 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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