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

Пусть $1\le k\le n<N$. Мы говорим, что вектор $x\in\mathbb R^N$ является $k$-разреженным, если он имеет не более $k$ ненулевых координат. Пусть задана $n\times N$ матрица $\Phi$. Рассматривается задача восстановления $k$-разреженного вектора $x\in\mathbb R^N$ по вектору $y=\Phi x\in\mathbb R^n$. Мы находим близкие к окончательным необходимые условия на $k,n,N$ для того, чтобы эта задача могла быть сведена к задаче минимизации $\ell_1$-нормы векторов $z$, удовлетворяющих условию $y=\Phi z$.
Библиография: 16 названий.