Sparse Representation in Redundant Systems

CSIC Building (#406), Seminar Room 4122.
Directions: home.cscamm.umd.edu/directions

Signal Recovery from Partial Information via Orthogonal Matching Pursuit

Dr. Joel Tropp

University of Michigan at Ann Arbor

Abstract:   This talk will demonstrate theoretically and empirically that a greedy algorithm called Orthogonal Matching Pursuit (OMP) can reliably recover a signal with m nonzero entries in dimension d given O(m ln d) random linear measurements of that signal. This is a massive improvement over previous results for OMP, which require O(m²) measurements. The new results for OMP are comparable with recent results for the Basis Pursuit (BP) algorithm. The OMP algorithm is much faster and much easier to implement, which makes it an attractive alternative to BP for signal recovery problems.

[LECTURE SLIDES]