Optimization Online


Sparse optimization with least-squares constraints

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

Abstract: The use of convex optimization for the recovery of sparse signals from incomplete or compressed data is now common practice. Motivated by the success of basis pursuit in recovering sparse vectors, new formulations have been proposed that take advantage of different types of sparsity. In this paper we propose an efficient algorithm for solving a general class of sparsifying formulations. For several common types of sparsity we provide applications, along with details on how to apply the algorithm, and experimental results.

Keywords: basis pursuit, compressed sensing, convex program, duality, group sparsity, matrix completion, Newton’s method, root-finding, sparse solutions

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Applications -- Science and Engineering

Citation: UBC Department of Computer Science Tech. Rep. TR-2010-02, January 2010

Download: [PDF]

Entry Submitted: 02/09/2010
Entry Accepted: 02/09/2010
Entry Last Modified: 02/09/2010

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