Sparse Solutions to Underdetermined Linear Systems

GUEST LECTURER
Joel A. Tropp

AFFILIATION
The University of Michigan

ABSTRACT
A fundamental problem in applied mathematics, statistics, and electrical engineering is to solve underdetermined systems of linear equations. Basic linear algebra seems to forbid this possibility. But a recent strand of research has established that certain underdetermined systems can be solved robustly with efficient algorithms, provided that the solution is sparse (i.e., has many zero components). This talk provides an overview of these sparse representation problems, and it describes the basic algorithmic approaches. Then it details situations where the algorithms are guaranteed to succeed. In particular, the talk introduces some new work on the case where the matrix is deterministic and the sparsity pattern is random. It also covers some results for the case where the matrix is random, which is the situation in Compressed Sensing applications.