Optimization Online


On partially sparse recovery

A. S. Bandeira(ajsb***at***math.princeton.edu)
K. Scheinberg(katyas***at***lehigh.edu)
L. N. Vicente(lnv***at***mat.uc.pt)

Abstract: In this paper we consider the problem of recovering a partially sparse solution of an underdetermined system of linear equations by minimizing the l1-norm of the part of the solution vector which is known to be sparse. Such a problem is closely related to the classical problem in Compressed Sensing where the l1-norm of the whole solution vector is minimized. We introduce analogues of restricted isometry and null space properties for the recovery of partially sparse vectors and show that these new properties are implied by their original counterparts. We show also how to extend recovery under noisy measurements to the partially sparse case.

Keywords: Sparse recovery, partially sparse recovery, compressed sensing, l1-minimization, applications in sparse quadratic polynomial interpolation.

Category 1: Convex and Nonsmooth Optimization

Citation: preprint 11-13, Dept. Mathematics, Univ. Coimbra

Download: [PDF]

Entry Submitted: 04/15/2011
Entry Accepted: 04/15/2011
Entry Last Modified: 04/15/2011

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