Geodesic
On the Recovery of an Integer Vector from Linear Measurements
Matematičeskie zametki, Tome 104 (2018) no. 6, pp. 863-871.

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

Let $1\le 2l\le m$. A vector $x\in\mathbb Z^d$ is said to be $l$-sparse if it has at most $l$ nonzero coordinates. Let an $m\times d$ matrix $A$ be given. The problem of the recovery of an $l$-sparse vector $x\in\mathbb Z^d$ from the vector $y=A x\in\mathbb R^m$ is considered. In the case $m=2l$, we obtain necessary and sufficient conditions on the numbers $m$, $d$, and $k$ ensuring the existence of an integer matrix $A$ all of whose elements do not exceed $k$ in absolute value which makes it possible to reconstruct $l$-sparse vectors in $\mathbb Z^d$. For a fixed $m$, these conditions on $d$ differ only by a logarithmic factor depending on $k$.
Keywords: nonsingular matrix, lattices, successive minima. 
@article{MZM_2018_104_6_a5,
     author = {S. V. Konyagin},
     title = {On the {Recovery} of an {Integer} {Vector} from {Linear} {Measurements}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {863--871},
     publisher = {mathdoc},
     volume = {104},
     number = {6},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2018_104_6_a5/}
}
TY  - JOUR
AU  - S. V. Konyagin
TI  - On the Recovery of an Integer Vector from Linear Measurements
JO  - Matematičeskie zametki
PY  - 2018
SP  - 863
EP  - 871
VL  - 104
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2018_104_6_a5/
LA  - ru
ID  - MZM_2018_104_6_a5
ER  - 
%0 Journal Article
%A S. V. Konyagin
%T On the Recovery of an Integer Vector from Linear Measurements
%J Matematičeskie zametki
%D 2018
%P 863-871
%V 104
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2018_104_6_a5/
%G ru
%F MZM_2018_104_6_a5
S. V. Konyagin. On the Recovery of an Integer Vector from Linear Measurements. Matematičeskie zametki, Tome 104 (2018) no. 6, pp. 863-871. http://geodesic.mathdoc.fr/item/MZM_2018_104_6_a5/

[1] M. Davenport, M. 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] L. Fukshansky, D. Needell, B. Sudakov, An Algebraic Perspective on Integer Sparse Recovery, 2018, arXiv: 1801.01526

[4] J. Bourgain, V. H. Vu, Ph. M. Wood, “On the singularity probability of discrete random matrices”, J. Funct. Anal., 258:2 (2010), 559–603 | DOI | MR | Zbl

[5] I. M. Vinogradov, Osnovy teorii chisel, Nauka, M., 1981 | MR

[6] M. Henk, “Successive minima and lattice points”, Rend. Circ. Mat. Palermo (2) Suppl., 70 (2002), 377–384 | MR | Zbl