Stanford 50: State of the Art and Future Directions of Computational Mathematics and Numerical Computing


  • March 29, 2007
  • 4:25 pm - 4:50 pm

Finding sparse solutions of underdetermined systems: Gradient Projection approaches

Stephen Wright (University of Wisconsin-Madison)

We discuss optimization problems in which the objective consists of a linear least squares term (usually derived from an underdetermined linear system) added to a weighted $\ell$-1 norm of the variables. Such problems arise in wavelet-based deconvolution, compressed sensing, and other applications. They have been the subject of intense research in recent years from both a theoretical and an algorithmic perspective. We give an overview of the various approaches, then focus on algorithms of gradient projection type. Some computational results are presented. (Joint work with Rob Nowak and Mario Figuerido.)

Stanford University Home Page