In pursuit of a root

Ewout van den Berg(ewout78cs.ubc.ca)
Michael P Friedlander(mpfcs.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