  


In pursuit of a root
Ewout van den Berg(ewout78cs.ubc.ca) Abstract: The basis pursuit technique is used to find a minimum onenorm solution of an underdetermined leastsquares problem. Basis pursuit denoise fits the leastsquares problem only approximately, and a single parameter determines a curve that traces the tradeoff between the leastsquares fit and the onenorm 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 leastsquares problem with an explicit onenorm constraint gives function and derivative information needed for a rootfinding method. As a result, we can compute arbitrary points on this curve. Numerical experiments demonstrate that our method, which relies on only matrixvector 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 TR200716, June 2007. Download: [PDF] Entry Submitted: 06/28/2007 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  