Math @ Duke

Publications [#287189] of Ingrid Daubechies
Papers Published
 Daubechies, I; Devore, R; Fornasier, M; Güntürk, CS, Iteratively reweighted least squares minimization for sparse recovery,
Communications on Pure & Applied Mathematics, vol. 63 no. 1
(2010),
pp. 138, ISSN 00103640 [doi]
(last updated on 2018/03/17)
Abstract: Under certain conditions (known as the restricted isometry property, or RIP) on the m × N matrix Φ (wherem < N), vectors x ∈ R{doublestruck}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 (Nm)dimensional hyperplane; in addition, x is then equal to the element in Φ1(y) of minimal l1norm. 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

