On exact recovery of sparse vectors from linear measurements

Let 1 ≤ k ≤ n < N. We say that a vector x ∈ ? ^N is k-sparse if it has at most k nonzero coordinates. Let Φ be an n × N matrix. We consider the problem of recovery of a k-sparse vector x ∈ ? ^N from the vector y = Φx ∈ ? ⁿ . We obtain almost-sharp necessary conditions for k, n, N for this problem to be reduced to that of minimization of the ?₁-norm of vectors z satisfying the condition y = Φz.