PaperlayerView exact revision on arXiv

Source-linked AI summary

Iteratively re-weighted least squares minimization for sparse recovery

Ingrid Daubechies, Ronald DeVore, Massimo Fornasier, C. Sinan Gunturk

arXiv:0807.0575v1math.NA

TL;DR

Sparse recovery seeks preferred solutions of underdetermined systems when the desired vector is sparse or compressible. The paper develops an IRLS algorithm with carefully constructed weights, proves convergence and local rates, and extends it to ℓτ-minimization. The extension supports superlinear convergence, approaching a quadratic rate as τ tends to zero, while nonconvexity weakens the recovery guarantee.

  • Problem

    Underdetermined systems have infinitely many solutions, so recovery requires a method that selects sparse or compressible vectors; standard IRLS analyses face difficulties when coordinates vanish.

  • Method

    The paper constructs an IRLS algorithm using positive weights derived from successive weighted least-squares solutions, then extends the scheme to promote ℓτ-minimization for 0 < τ < 1.

  • Results

    Under stated RIP conditions, Algorithm 1 converges to a sparse solution and, when applicable, the unique ℓ1-minimizer; its local convergence is exponential, while the ℓτ modification is superlinear and approaches quadratic as τ approaches zero.

  • Takeaways & Limitations

    IRLS provides a theoretically analyzed alternative to direct ℓ1-minimization for sparse recovery, with a nonconvex extension offering faster local convergence.

  • Takeaways & Limitations

    Because ℓτ-minimization is non-convex, the extended theorem does not ensure convergence to the sparsest or minimal ℓτ-solution.

Abstract

from arXiv · show

We analyze an Iteratively Re-weighted Least Squares (IRLS) algorithm for promoting l1-minimization in sparse and compressible vector recovery. We prove its convergence and we estimate its local rate. We show how the algorithm can be modified in order to promote lt-minimization for t<1, and how this modification produces superlinear rates of convergence.

1 Introduction

The paper develops and analyzes an IRLS method for sparse recovery, addressing failures caused by vanishing coordinates and infinite re-weighting components. It proves convergence under null-space or RIP conditions, establishes exponential local convergence, and extends the analysis to nonconvex ℓτ-minimization with superlinear rates.

  • Method: IRLS iteratively solves weighted least-squares problems and updates weights from the current solution to approximate ℓ1-minimization.The method uses positive weights and an alternating minimizer-weight construction; sparsity is characterized through the decreasing rearrangement of vector magnitudes.
  • Motivation: Infinite weights at vanishing coordinates can cause problems, while practical weight modifications may no longer converge to the desired ℓ1 solution.The paper notes that Osborne’s local analysis applies only under assumptions that become vacuous when uniqueness forces vanishing components.
  • Convergence and recovery: Under the RIP and related null-space conditions, Algorithm 1 converges to a limit and recovers a sufficiently sparse solution, which is the unique ℓ1-minimizer when the limiting regularization vanishes.The sparsity threshold depends on the RIP constant, with κ approaching 1 as δ becomes small.
  • Convergence and recovery: Once sufficiently close to a sparse limit, the algorithm converges exponentially fast, although the analysis does not specify how long the iterates take to enter that local region.The local contraction factor µ is fixed below 1 and depends on δ.
  • Nonconvex extension: A modified IRLS scheme also promotes ℓτ-minimization for 0 < τ < 1, with local convergence that is superlinear and approaches quadratic as τ approaches zero.Because the objective is non-convex, the corresponding theorem does not ensure convergence to the sparsest or minimal ℓτ solution.

2 Characterization of ℓ1- and weighted ℓ2-minimizers

This section characterizes ℓ1-minimizers in the feasible affine space and establishes uniqueness criteria, then describes unique weighted ℓ2-minimizers through weighted orthogonality.

  • ℓ1-minimizers: ℓ1-minimization over F(y) is framed as approximation from the null space N.Minimizers are feasible points that cannot be improved by adding null-space directions.
  • ℓ1-minimizers: An element x∈F(y) is an ℓ1-minimizer exactly when its null-space directional inequalities hold for every η∈N.The same characterization is necessary and sufficient.
  • Uniqueness: Strict inequality for every nonzero η∈N is equivalent to uniqueness of the ℓ1-minimizer.Conversely, equality in the relevant condition permits another minimizer.
  • Uniqueness: Unique ℓ1-minimizers must be k-sparse for some k<N.A minimizer with no vanishing entries can be perturbed along a nonzero null-space direction without changing its ℓ1 norm.
  • Weighted ℓ2-minimizers: Strictly positive weighted ℓ2(w)-norms are strictly convex, so their minimizer is unique and characterized by weighted orthogonality to N.The minimizer satisfies ⟨z,η⟩_w=0 for every η∈N.

3 The Restricted Isometry and the Null Space Properties

The section introduces RIP and NSP as structural conditions on Φ for analyzing IRLS convergence. It explains their relationship and how NSP guarantees recovery and uniqueness of sparse ℓ1-minimizers.

  • RIP: RIP of order L bounds ||Φz||_ℓ2 above and below for every L-sparse vector z.The bounds use the distortion parameter δ∈(0,1).
  • RIP: Random Gaussian or Bernoulli matrix families satisfy RIP with high probability for L≤c0(δ)n/log n.The stated asymptotic range applies to the random families discussed.
  • NSP: The NSP controls null-space vectors by comparing their coordinates on any set T of size at most L with those on its complement.The paper uses a variant parameterized by order L and constant γ.
  • RIP–NSP relationship: RIP implies NSP at related orders, and requiring γ<1 may slightly reduce the usable order range.The paper states that an NSP with arbitrary γ0 can be reduced to a smaller order with γ<1.
  • Sparse recovery: If Φ has NSP of order L with γ<1 and F(y) contains an L-sparse vector, that vector is the unique ℓ1-minimizer.Thus NSP supplies a sufficient recovery condition for sparse solutions.

4 Preliminary results

The preliminary results develop rearrangement and approximation tools, a null-space geometric inequality, and monotonicity properties of the IRLS functional. These ingredients support sparse recovery and convergence analysis.

  • Approximation tools: The decreasing rearrangement r(z) orders the absolute entries of z, and a vector is k-sparse exactly when r(v)k+1=0.The j-term error σj(z)_ℓ1 measures the tail beyond the largest j entries.
  • Approximation tools: The map z↦r(z) is Lipschitz continuous in ℓ∞, with corresponding bounds for rearrangement and j-term approximation errors.These continuity properties are used to pass sparsity-related bounds to limits.
  • Null-space geometry: Under NSP with γ<1, feasible points with close ℓ1 norms are close when one is near a k-sparse vector.This approximate reverse triangle inequality is a geometric property of the null space.
  • Sparse recovery: If F(y) contains an L-sparse vector, NSP makes it the unique ℓ1-minimizer and bounds the ℓ1 error of arbitrary feasible vectors relative to it.The proof derives minimality and uniqueness from the geometric inequality.
  • IRLS functional: The IRLS functional is monotone across weight, smoothing, and minimization updates.Specifically, J(xn+1,wn+1,εn+1)≤J(xn,wn,εn).
  • IRLS functional: Each new x is determined by the previous weights, and uniform initial weights make x1 the classical minimum ℓ2-norm feasible point.The monotonicity inequality therefore also holds for arbitrary x0∈F(y).

5 Convergence of the algorithm

The convergence theorem shows that IRLS converges under an NSP condition, reaching the unique ℓ1-minimizer when the smoothing limit is zero and a smoothed minimizer when it is positive. It also gives sparse-approximation bounds and identifies a recovery gap relative to ℓ1-minimization.

  • Convergence proof: The iteration differences satisfy xn−xn+1→0, providing the starting point for convergence.The proof uses the decreasing IRLS functional and weighted norm control.
  • Main convergence theorem: Under NSP of order K with γ<1, Algorithm 1 converges for every y to a vector x̄ whose (K+1)-st rearranged entry equals N limn→∞εn.The theorem distinguishes the cases of zero and positive smoothing limits.
  • Main convergence theorem: When ε=limn→∞εn=0, x̄ is K-sparse and equals the unique ℓ1-minimizer x* whenever a K-sparse feasible solution exists.The proof uses NSP-based uniqueness and continuity of rearrangements.
  • Main convergence theorem: When ε=limn→∞εn>0, the iterates converge to the unique minimizer xε of the smoothed functional fε.The characterization uses weighted orthogonality, and uniqueness of the accumulation point yields convergence.
  • Error estimates: For positive ε, a stricter NSP bound yields an ℓ1 error estimate relative to any feasible z, including its k-term approximation error.The theorem applies when k<K−2γ/(1−γ).
  • Scope and comparison: IRLS guarantees sparse recovery for a slightly smaller sparsity range than ℓ1-minimization, with the gap vanishing as γ becomes small.The paper cannot exclude non-recovery in the gap K−2γ/(1−γ)≤k≤K, although for γ<1/3 it can occur only when k=K.

6 Rate of Convergence

The analysis establishes exponential convergence of IRLS to sparse solutions and extends rate guarantees to approximately sparse targets, where convergence is toward a controlled error ball.

  • 6.1 Case of k-sparse vectors: Under the stated NSP conditions, IRLS converges to a k-sparse solution x∗ and therefore to the unique ℓ1-minimizer.The limit coincides with the sparse vector when the sparsity and NSP bounds hold.
  • 6.1 Case of k-sparse vectors: Once the iterates are sufficiently close to x∗, the error contracts geometrically, yielding exponential (linear) convergence.The contraction has the form E_n+1 ≤ μE_n with μ < 1.
  • 6.1 Case of k-sparse vectors: The precise update rule for ϵ_n is needed to ensure eventual entry into the locally controlled region, but other decreasing update rules may also work.The rate additionally depends on the contraction factor and the decay rate of ϵ_n.
  • 6.2 Case of noisy k-sparse vectors: For approximately k-sparse targets, the iterates converge exponentially to a ball centered at z whose radius scales with σ_k(z)_ℓ1.This extends the sparse-target rate estimate to a neighborhood of k-sparse vectors.
  • 6.2 Case of noisy k-sparse vectors: The noisy-target guarantee applies while the iterate remains sufficiently far from its limit and requires an approximately sparse target with an adequate gap ratio.The authors note that exponential convergence can persist for a meaningful number of iterations when the gap ratio is sufficiently larger than C1.

7 Beyond the convex case: ℓτ-minimization for τ < 1

The paper extends IRLS from convex ℓ1-minimization to non-convex ℓτ-minimization for τ < 1. Under a τ-NSP, the modified algorithm can recover sparse minimizers and achieves superlinear local convergence, while global guarantees are weaker.

  • Motivation: ℓτ-minimization is studied as a non-convex alternative to ℓ1-minimization, with potential recovery benefits for smaller τ.Prior results indicate that the recoverable sparsity range can be larger for smaller τ.
  • Convergence: Under a τ-NSP and suitable sparsity conditions, the algorithm converges to an ℓτ-minimizer that coincides with an existing sparse solution.For τ < 1, the convergence theorem distinguishes the cases ϵ = 0 and ϵ > 0.
  • Local rate: The local error convergence is superlinear, with the rate approaching quadratic as τ approaches zero.The local estimate is valid in a sufficiently small neighborhood of the sparse solution.
  • Algorithm: The modified IRLS algorithm replaces J with Jτ while retaining the same ϵ-update rule, and its objective values decrease monotonically.The iterates remain bounded, the weights stay bounded below, and the iterations are asymptotically regular.
  • Limitations: Unlike the convex case, the τ < 1 theorem does not ensure convergence to the sparsest or globally minimal ℓτ solution because the objective is non-convex.The authors instead provide a posteriori conditions supporting such convergence and establish a local rate result.

8 Numerical results

The experiments confirm linear convergence and robust sparse recovery for the ℓ1-inspired IRLS algorithm, while ℓτ-inspired variants accelerate locally and can benefit from a staged initialization.

  • The experiments confirm the expected linear convergence rate and robust recovery of sparse vectors for ℓ1-minimization IRLS.Gaussian matrices were used because they are known to possess the RIP with high probability.
  • The comparison examines linear convergence for ℓ1-minimization against superlinear convergence for IRLS promoting ℓτ-minimization.
  • For τ = 1, convergence is linear, whereas τ = 0.8, 0.6, and 0.56 accelerate after the iterates approach the sparse solution.For smaller τ, the experiments do not always reach the neighborhood where convergence is ensured.
  • The main sparse-recovery example uses a 45-sparse vector in dimension 1500 and reports approximation error and convergence-rate quantities across iterations.
  • Combining initial ℓ1-inspired IRLS iterations with later ℓτ-inspired iterations enables very fast convergence to the sparsest solution for τ = 0.5.
Loading 0807.0575v1…