On the Recovery of an Integer Vector from Linear Measurements

S. V. Konyagin

Matematičeskie zametki, Tome 104 (2018) no. 6, pp. 863-871

Résumé

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$.

Détail

Keywords: nonsingular matrix, lattices, successive minima.