Об эффективности ортогонального жадного алгоритма в задаче о сжатых измерениях

В работе показано, что если матрица $\Phi$ обладает свойством ограниченной изометрии (СОИ) порядка $[CK^{1.2}]$ с изометрической константой $\delta=cK^{-0.2}$ и имеет когерентность меньшую, чем $1/(20K^{0.8})$, то произвольный $K$-разреженный сигнал может быть точно восстановлен по сжатым измерениям $y=\Phi x$ с помощью ортогонального жадного алгоритма (Orthogonal Matching Pursuit) за не более чем $[CK^{1.2}]$ итераций. Из этого результата вытекает, что произвольный $K$-разреженный сигнал может быть восстановлен с помощью жадного алгоритма по $M=O(K^{1.6}\log N)$ измерениям.
Библиография: 23 названия.