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


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.