On recovery of sparse vectors from linear measurements

Let $1\le 2l\le m<d$. We say that a vector $x\in\mathbb{R}^d$ is $l$-sparse if it has at most $l$ nonzero coordinates. Let $A$ be a given $m\times d$ matrix. We consider the problem of recovery of an $l$-sparse vector $x\in\mathbb{R}^d$ from the vector $y=A x\in\mathbb{R}^m$. The problem of an effective recovery of $x$ from $y$ attracts a big interest of leading specialists. We will mention a connection of this problem with estimation of the number of solutions of equations with reciprocals. The main part of the talk will be devoted to possibility of recovery of integer vectors. In the case $m=2l$ we find necessary conditions and sufficient conditions on numbers $m,d,k$ for the existence of an integer matrix $A$ with the absolute values of all elements not exceeding $k$ that allows to reconstruct $l$-sparse vectors in $\mathbb{Z}^d$. For fixed $m$ these conditions on $d$ differ only by a logarithmic factor depending on $k$.