Geodesic
On Exact Recovery of Sparse Vectors from Linear Measurements
Matematičeskie zametki, Tome 94 (2013) no. 1, pp. 122-129

Voir la notice de l'article provenant de la source Math-Net.Ru

Let $1\le k\le 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$.
Keywords: compressed sensing, exact recovery of a $k$-sparse vector, restricted isometry property, element of best approximation, estimates of Kolmogorov widths. 
@article{MZM_2013_94_1_a9,
     author = {S. V. Konyagin and Yu. V. Malykhin and C. S. Rjutin},
     title = {On {Exact} {Recovery} of {Sparse} {Vectors} from {Linear} {Measurements}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {122--129},
     publisher = {mathdoc},
     volume = {94},
     number = {1},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2013_94_1_a9/}
}
TY  - JOUR
AU  - S. V. Konyagin
AU  - Yu. V. Malykhin
AU  - C. S. Rjutin
TI  - On Exact Recovery of Sparse Vectors from Linear Measurements
JO  - Matematičeskie zametki
PY  - 2013
SP  - 122
EP  - 129
VL  - 94
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2013_94_1_a9/
LA  - ru
ID  - MZM_2013_94_1_a9
ER  - 
%0 Journal Article
%A S. V. Konyagin
%A Yu. V. Malykhin
%A C. S. Rjutin
%T On Exact Recovery of Sparse Vectors from Linear Measurements
%J Matematičeskie zametki
%D 2013
%P 122-129
%V 94
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2013_94_1_a9/
%G ru
%F MZM_2013_94_1_a9
S. V. Konyagin; Yu. V. Malykhin; C. S. Rjutin. On Exact Recovery of Sparse Vectors from Linear Measurements. Matematičeskie zametki, Tome 94 (2013) no. 1, pp. 122-129. http://geodesic.mathdoc.fr/item/MZM_2013_94_1_a9/