  


Probing the Pareto frontier for basis pursuit solutions
Ewout van den Berg (ewout78cs.ubc.ca) Abstract: The basis pursuit problem seeks a minimum onenorm solution of an underdetermined leastsquares problem. Basis pursuit denoise (BPDN) fits the leastsquares problem only approximately, and a single parameter determines a curve that traces the optimal tradeoff between the leastsquares fit and the onenorm 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 rootfinding 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 gradientprojection method approximately minimizes a leastsquares problem with an explicit onenorm constraint. Only matrixvector operations are required. The primaldual solution of this problem gives function and derivative information needed for the rootfinding 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 TR200801, January 2008 Download: [PDF] Entry Submitted: 01/27/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  