On efficiency of Orthogonal Matching Pursuit
arXiv:1004.394615 citationsh-index: 7
Originality Incremental advance
AI Analysis
For researchers in compressed sensing, this provides a tighter theoretical guarantee on the number of measurements required for OMP to recover sparse signals.
The paper proves that Orthogonal Matching Pursuit (OMP) can recover K-sparse signals using M=O(K^{1.6} log N) measurements, improving the known bound from O(K^2 log N) to O(K^{1.6} log N).
We show that if a matrix $Φ$ satisfies the RIP of order $[CK^{1.2}]$ with isometry constant $\dt = c K^{-0.2}$ and has coherence less than $1/(20 K^{0.8})$, then Orthogonal Matching Pursuit (OMP) will recover $K$-sparse signal $x$ from $y=Φx$ in at most $[CK^{1.2}]$ iterations. This result implies that $K$-sparse signal can be recovered via OMP by $M=O(K^{1.6}\log N)$ measurements.