Probing the Pareto frontier for basis pursuit solutions

Ewout van den Berg (ewout78cs.ubc.ca)
Michael P. Friedlander (mpfcs.ubc.ca)

Abstract: The basis pursuit problem seeks a minimum one-norm solution of an underdetermined least-squares problem. Basis pursuit denoise (BPDN) fits the least-squares problem only approximately, and a single parameter determines a curve that traces the optimal trade-off between the least-squares fit and the one-norm of the solution. We prove that this curve is convex and continuously differentiable over all points of interest, and show that it gives an explicit relationship to two other optimization problems closely related to BPDN. We describe a root-finding algorithm for finding arbitrary points on this curve; the algorithm is suitable for problems that are large scale and for those that are in the complex domain. At each iteration, a spectral gradient-projection method approximately minimizes a least-squares problem with an explicit one-norm constraint. Only matrix-vector operations are required. The primal-dual solution of this problem gives function and derivative information needed for the root-finding method. Numerical experiments on a comprehensive set of test problems demonstrate that the method scales well to large problems.

Keywords: basis pursuit, convex program, duality, Lagrange multiplier, projected gradient, regularization, sparse solutions, least squares

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Applications -- Science and Engineering (Basic Sciences Applications )

Citation: Department of Computer Science, University of British Columbia, Technical Report TR-2008-01, January 2008

Download: [PDF]

Entry Submitted: 01/27/2008
Entry Accepted: 01/28/2008
Entry Last Modified: 06/06/2008

Modify/Update this entry