Timezone: »

Orthogonal Matching Pursuit From Noisy Random Measurements: A New Analysis
Alyson Fletcher · Sundeep Rangan

Wed Dec 09 07:00 PM -- 11:59 PM (PST) @

Orthogonal matching pursuit (OMP) is a widely used greedy algorithm for recovering sparse vectors from linear measurements. A well-known analysis of Tropp and Gilbert shows that OMP can recover a k-sparse n-dimensional real vector from m = 4k log(n) noise-free random linear measurements with a probability that goes to one as n goes to infinity. This work shows strengthens this result by showing that a lower number of measurements, m = 2k log(n-k), is in fact sufficient for asymptotic recovery. Moreover, this number of measurements is also sufficient for detection of the sparsity pattern (support) of the vector with measurement errors provided the signal-to-noise ratio (SNR) scales to infinity. The scaling m = 2k log(n-k) exactly matches the number of measurements required by the more complex lasso for signal recovery.

Author Information

Alyson Fletcher (UCLA)
Sundeep Rangan (Qualcomm)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors