Optimization Online


In pursuit of a root

Ewout van den Berg(ewout78***at***cs.ubc.ca)
Michael P Friedlander(mpf***at***cs.ubc.ca)

Abstract: The basis pursuit technique is used to find a minimum one-norm solution of an underdetermined least-squares problem. Basis pursuit denoise fits the least-squares problem only approximately, and a single parameter determines a curve that traces the trade-off between the least-squares fit and the one-norm of the solution. We show that the function that describes this curve is convex and continuously differentiable over all points of interest. The dual solution of a least-squares problem with an explicit one-norm constraint gives function and derivative information needed for a root-finding method. As a result, we can compute arbitrary points on this curve. Numerical experiments demonstrate that our method, which relies on only matrix-vector operations, scales well to large problems.

Keywords: Basis pursuit, gradient projection, Lagrange duality

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: UBC Computer Science Technical Report TR-2007-16, June 2007.

Download: [PDF]

Entry Submitted: 06/28/2007
Entry Accepted: 06/29/2007
Entry Last Modified: 06/28/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society