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/

[1] M. A. Davenport, M. F. Duarte, Y. C. Eldar, G. Kutyniok, “Introduction to compressed sensing”, Compressed Sensing, Cambridge Univ. Press, Cambridge, 2012, 1–64 | MR

[2] M. Fornasier, H. Rauhut, “Compressive sensing”, Handbook of Mathematical Methods in Imaging, Springer-Verlag, Berlin, 2011, 187–228 | Zbl

[3] S. S. Chen, D. L. Donoho, M. A. Saunders, “Atomic decomposition by basis pursuit”, SIAM Rev., 43:1 (2001), 129–159 | DOI | MR | Zbl

[4] E. J. Candés, J. K. Romberg, T. Tao, “Stable signal recovery from incomplete and inaccurate measurements”, Comm. Pure Appl. Math., 59:8 (2006), 1207–1223 | DOI | MR | Zbl

[5] E. J. Candes, T. Tao, “Decoding by linear programming”, IEEE Trans. Inform. Theory, 51:12 (2005), 4203–4215 | DOI | MR

[6] R. Baraniuk, M. Davenport, R. DeVore, M. Wakin, “A simple proof of the restricted isometry property for random matrices”, Constr. Approx., 28:3 (2008), 253–263 | DOI | MR | Zbl

[7] J. Bourgain, S. Dilworth, K. Ford, S. Konyagin, D. Kutzarova, “Explicit constructions of RIP matrices and related problems”, Duke Math. J., 159:1 (2011), 145–185 | DOI | MR | Zbl

[8] D. L. Donoho, “Compressed sensing”, IEEE Trans. Inform. Theory, 52:4 (2006), 1289–1306 | DOI | MR

[9] A. Cohen, W. Dahmen, R. DeVore, “Compressed sensing and $k$-term approximation”, J. Amer. Math. Soc., 22:1 (2009), 211–231 | DOI | MR | Zbl

[10] B. S. Kashin, V. N. Temlyakov, “Zamechanie o zadache szhatogo izmereniya”, Matem. zametki, 82:6 (2007), 829–837 | DOI | MR

[11] K. D. Ba, P. Indyk, E. Price, D. P. Woodruff, “Lower bounds for sparse recovery”, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2010, 1190–1197 | MR

[12] Y. Benyamini, A. Kroó, A. Pinkus, “$L^1$-Approximation and finding solutions with small support”, Constr. Approx., 36:3 (2012), 399–431 | DOI | MR | Zbl

[13] S. M. Nikolskii, “Priblizhenie funktsii trigonometricheskimi polinomami v srednem”, Izv. AN SSSR. Ser. matem., 10:3 (1946), 207–256 | MR | Zbl

[14] A. B. Khodulev, “Nekotorye tochnye znacheniya kolmogorovskikh poperechnikov v konechnomernykh prostranstvakh”, Preprinty IPM, 1988, 185 | MR

[15] B. S. Kashin, “Poperechniki nekotorykh konechnomernykh mnozhestv i klassov gladkikh funktsii”, Izv. AN SSSR. Ser. matem., 41:2 (1977), 334–351 | MR | Zbl

[16] A. Yu. Garnaev, E. D. Gluskin, “O poperechnikakh evklidova shara”, DAN SSSR, 277:5 (1984), 1048–1052 | MR | Zbl