Systems Seminar
Random Subdictionaries of General Dictionaries
Joel A. Tropp
NSF Postdoctoral Fellow
Hildebrandt Research Assistant Professor
Department of Mathematics
The University of Michigan at Ann Arbor
Abstract
A central problem in electrical engineering, statistics, and applied
mathematics is to solve ill-conditioned systems of linear equations.
Basic linear algebra forbids this possibility in the general case. But
a recent strand of research has established that certain
ill-conditioned systems can be solved robustly with efficient
algorithms, provided that the solution is sparse (i.e., has many zero
entries). This talk describes a popular method, called l1 minimization
or Basis Pursuit, for finding sparse solutions to linear systems. It
details situations where the algorithm is guaranteed to succeed. In
particular, it describes some new work on the case where the matrix is
deterministic and the sparsity pattern is random. These results are
currently the strongest available for general linear systems.
Time and Place: Tue., Aug. 29, at 2 pm in 4610 Engr. Hall.
*** NOTE SPECIAL DAY & TIME ***
SYSTEMS SEMINAR WEB PAGE:
http://homepages.cae.wisc.edu/~gubner/seminar/schedule.html