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
$\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$
  • $\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$ – Digital Gal Jun 25 '13 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 '13 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 Jul 28 '16 at 21:41

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.