Abstract:
The paper shows that if a matrix $\Phi$ has the restricted isometry property (RIP) of order $[CK^{1.2}]$ with isometry constant $\delta=cK^{-0.2}$ and if its coherence is less than $1/(20K^{0.8})$, then the Orthogonal Matching Pursuit (the Orthogonal Greedy Algorithm) is capable to exactly recover an arbitrary $K$-sparse signal from the compressed sensing $y=\Phi x$ in at most $[CK^{1.2}]$ iterations. As a result, an arbitrary
$K$-sparse signal can be recovered by the Orthogonal Matching Pursuit from $M=O(K^{1.6}\log N)$ measurements.
Bibliography: 23 titles.
Fulltext:
PDF file (499 kB)
