О восстановлении разреженных векторов по линейным измерениям

Пусть $1\le 2l\le m<d$. Мы говорим, что вектор $x\in\mathbb Z^d$ является $l$-разреженным, если он имеет не более $l$ ненулевых координат. Пусть задана $m\times d$ матрица $A$. Рассматривается задача восстановления $l$-разреженного вектора $x\in\mathbb R^d$ по вектору $y=A x\in\mathbb R^m$. Задача эфективного восстановления $x$ по $y$ привлекает большое внимание ведущих специалистов. Будет упомянута связь этой задачи с оценкой числа решения уравнений с обратными величинами в целых числах. Основная часть доклада посвящена рассмотрению возможности восстановления целочисленного вектора $x$. В случае $m=2l$ мы находим необходимые условия и достаточные условия на числа $m,d,k$ для того, чтобы существовала целочисленная матрица $A$, все элементы которой по модулю не превосходят $k$, позволяющая восстановить $l$-разреженные векторы в $\mathbb Z^d$. При фиксированном $m$ эти условия на $d$ отличаются лишь логарифмическим множителем по $k$.