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$ ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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
    Commented 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$
    – Samrat Mukhopadhyay
    Commented Jul 28, 2016 at 21:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .