On Exact Recovery of Sparse Vectors from Linear Measurements

Let $1\le k\le n<N$. We say that a vector $x\in\mathbb R^N$ is $k$-sparse if it has at most $k$ nonzero coordinates. Let $\Phi$ be an $n\times N$ matrix. We consider the problem of recovery of a $k$-sparse vector $x\in\mathbb R^N$ from the vector $y=\Phi x\in\mathbb R^n$. We obtain almost-sharp necessary conditions for $k,n,N$ for this problem to be reduced to that of minimization of the $\ell_1$-norm of vectors $z$ satisfying the condition $y=\Phi z$.