Skip to main content
Journal cover image

Iteratively reweighted least squares minimization for sparse recovery

Publication ,  Journal Article
Daubechies, I; Devore, R; Fornasier, M; Güntürk, CS
Published in: Communications on Pure and Applied Mathematics
January 1, 2010

Under certain conditions (known as the restricted isometry property, or RIP) on the m × N matrix Φ (wherem < N), vectors x ∈ R{double-struck}N that are sparse (i.e., have most of their entries equal to 0) can be recovered exactly from y:= Φx even though Φ-1(y). is typically an (N-m)-dimensional hyperplane; in addition, x is then equal to the element in Φ-1(y) of minimal l1-norm. This minimal element can be identified via linear programming algorithms. We study an alternative method of determining x, as the limit of an iteratively reweighted least squares (IRLS) algorithm. The main step of this IRLS finds, for a given weight vector w, the element in Φ-1(y) with smallest l2.(w)-norm. If x(n) is the solution at iteration step n, then the new weight w(n)i/ is defined by for a decreasing sequence of adaptively defined εn; this updated weight is then used to obtain x(n+1)/ and the process is repeated. We prove that when ̂ satisfies the RIP conditions, the sequence x(n) converges for all y, regardless of whether Φ-1(y), contains a sparse vector. If there is a sparse vector in Φ-1(y), then the limit is this sparse vector, and when x.(n) is sufficiently close to the limit, the remaining steps of the algorithm converge exponentially fast (linear convergence in the terminology of numerical optimization). The same algorithm with the "heavier" weight, can recover sparse solutions as well; more importantly, we show its local convergence is superlinear and approaches a quadratic rate for approaching 0. © 2009 Wiley Periodicals, Inc.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Communications on Pure and Applied Mathematics

DOI

EISSN

0010-3640

ISSN

0010-3640

Publication Date

January 1, 2010

Volume

63

Issue

1

Start / End Page

1 / 38

Related Subject Headings

  • General Mathematics
  • 4904 Pure mathematics
  • 4901 Applied mathematics
  • 0102 Applied Mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Daubechies, I., Devore, R., Fornasier, M., & Güntürk, C. S. (2010). Iteratively reweighted least squares minimization for sparse recovery. Communications on Pure and Applied Mathematics, 63(1), 1–38. https://doi.org/10.1002/cpa.20303
Daubechies, I., R. Devore, M. Fornasier, and C. S. Güntürk. “Iteratively reweighted least squares minimization for sparse recovery.” Communications on Pure and Applied Mathematics 63, no. 1 (January 1, 2010): 1–38. https://doi.org/10.1002/cpa.20303.
Daubechies I, Devore R, Fornasier M, Güntürk CS. Iteratively reweighted least squares minimization for sparse recovery. Communications on Pure and Applied Mathematics. 2010 Jan 1;63(1):1–38.
Daubechies, I., et al. “Iteratively reweighted least squares minimization for sparse recovery.” Communications on Pure and Applied Mathematics, vol. 63, no. 1, Jan. 2010, pp. 1–38. Scopus, doi:10.1002/cpa.20303.
Daubechies I, Devore R, Fornasier M, Güntürk CS. Iteratively reweighted least squares minimization for sparse recovery. Communications on Pure and Applied Mathematics. 2010 Jan 1;63(1):1–38.
Journal cover image

Published In

Communications on Pure and Applied Mathematics

DOI

EISSN

0010-3640

ISSN

0010-3640

Publication Date

January 1, 2010

Volume

63

Issue

1

Start / End Page

1 / 38

Related Subject Headings

  • General Mathematics
  • 4904 Pure mathematics
  • 4901 Applied mathematics
  • 0102 Applied Mathematics
  • 0101 Pure Mathematics