A fast approach for overcomplete sparse decomposition based on smoothed L0 norm

Hossein Mohimani; Massoud Babaie-Zadeh; Christian Jutten

Source-linked AI summary

A fast approach for overcomplete sparse decomposition based on smoothed L0 norm

Hossein Mohimani, Massoud Babaie-Zadeh, Christian Jutten

arXiv:0809.2508v2Sep 15, 2008cs.IT

TL;DR

Underdetermined linear systems require sparse solutions for applications including SCA and overcomplete decomposition, but existing LP-based approaches minimize ℓ1 rather than directly targeting ℓ0. The paper proposes SL0, which directly minimizes a smoothed ℓ0 objective. Experiments show it is about two to three orders of magnitude faster than state-of-the-art interior-point LP solvers while providing the same or better accuracy.

Problem
The paper addresses sparse solutions of underdetermined linear systems and the computational burden of existing LP-based ℓ1 approaches.
Method
SL0 directly minimizes a smoothed approximation to the ℓ0 norm instead of minimizing the ℓ1 norm with Linear Programming.
Results
About two to three orders of magnitude faster than state-of-the-art interior-point LP solvers, with the same or better accuracy.
Takeaways & Limitations
Smoothed ℓ0 minimization provides a fast approach for sparse solutions in underdetermined systems and overcomplete decomposition.

Abstract

from arXiv · show

In this paper, a fast algorithm for overcomplete sparse decomposition, called SL0, is proposed. The algorithm is essentially a method for obtaining sparse solutions of underdetermined systems of linear equations, and its applications include underdetermined Sparse Component Analysis (SCA), atomic decomposition on overcomplete dictionaries, compressed sensing, and decoding real field codes. Contrary to previous methods, which usually solve this problem by minimizing the L1 norm using Linear Programming (LP) techniques, our algorithm tries to directly minimize the L0 norm. It is experimentally shown that the proposed algorithm is about two to three orders of magnitude faster than the state-of-the-art interior-point LP solvers, while providing the same (or better) accuracy.

EDICS Category: MAL-SSEP, SPC-CODC, DSP-FAST

The paper is titled “A fast approach for overcomplete sparse” and lists affiliations in Iran and France, along with funding acknowledgments.

The work is affiliated with Sharif University of Technology’s Electrical Engineering Department in Tehran, Iran.
A second affiliation is GIPSA-Lab’s Department of Images and Signals at INPG in France.
The work acknowledges partial support from the Iran National Science Foundation under contract 86/994.

I. INTRODUCTION

The paper addresses sparse solutions of underdetermined linear systems arising in applications such as SCA and overcomplete dictionary decomposition. It proposes direct ℓ0 minimization as a faster alternative to LP-based ℓ1 methods, while retaining comparable accuracy.

In underdetermined BSS with m > n, source sparsity can make separation possible after estimating the mixing matrix and then the sources.
Overcomplete dictionaries have m > n atoms, and the objective is to represent signals using as few atoms as possible.
Sparse solutions of the underdetermined system As = x are central to sparse component analysis and overcomplete signal decomposition.
Minimum ℓ0 search is difficult because it requires combinatorial search and is sensitive to noise.
The proposed method directly minimizes ℓ0 and is typically two to three orders of magnitude faster than BP while achieving the same or better accuracy.

A. The Main Idea

The main idea is to replace discontinuous ℓ0 minimization with optimization of a continuous smoothed approximation. A decreasing smoothing parameter guides optimization from an easier problem toward a sparse solution.

The method approximates the discontinuous ℓ0 norm with a continuous function controlled by a parameter σ.
For small σ, the smoothed objective approaches the ℓ0 norm, so maximizing Fσ subject to As = x yields a minimum-ℓ0 solution.
Larger σ values make Fσ smoother and easier to maximize, whereas smaller values improve its approximation to ℓ0 but introduce more local maxima.
The algorithm decreases σ gradually, initializing each maximization from the solution found at the previous, larger σ.
This continuation strategy is intended to avoid local maxima and reach the minimum-ℓ0 solution at small σ.

B. Initialization

Initialization begins at sufficiently large σ, where maximizing the smoothed objective under As = x gives the minimum-ℓ2 solution. The constrained maximization is characterized using Lagrange multipliers and KKT equations.

For sufficiently large σ, the maximizer of Fσ subject to As = x is the minimum-ℓ2 solution given by the pseudo-inverse of A.
The constrained optimization is formulated with L(s, λ) = Fσ(s) − λT(As − x), and setting derivatives to zero produces a KKT system.
The resulting system contains m components of s and n components of λ, for m + n unknowns.
As σ approaches infinity, the stationarity systems for maximizing Fσ and minimizing the ℓ2 norm become identical.

III. THE FINAL ALGORITHM

SL0 minimizes a smoothed approximation to the ℓ0 norm through repeated steepest-ascent updates, projection onto the feasible set, and gradual decreases in σ. It starts from the minimum ℓ2-norm solution and uses scale-dependent step sizes to approach sparse solutions efficiently.

The internal loop need not reach an exact maximizer; entering the region near the global maximizer is sufficient for escaping local maximizers.
Because Fσ becomes more fluctuating as σ decreases, the steepest-ascent step sizes should also decrease, with µ_j proportional to σ^2.
The final SL0 algorithm initializes with the minimum ℓ2-norm solution obtained by the pseudo-inverse of A.
It selects a decreasing sequence of σ values and, at each value, repeatedly performs steepest ascent followed by projection onto As = x.
The algorithm uses a single constant µ by setting µ_j = µσ^2, making the ascent update s ← s + (µσ^2)∇Fσ.
For noisy sources, σ should remain around one to two times the noise standard deviation because smaller values can make the algorithm learn noisy inactive elements.

A. Convergence Analysis

The convergence analysis asks whether gradually maximizing Fσ recovers the unique sparsest solution and how σ controls the estimation error. Under URP and sparsity assumptions, exact fixed-σ maximization yields convergence as σ decreases, while the paper does not theoretically guarantee the practical σ schedule.

The analysis studies whether the smoothed objective converges to the unique ℓ0 minimizer and how far σ must decrease to achieve a desired accuracy.
The paper does not provide a theoretical σ sequence guaranteeing convergence because establishing such a sequence is considered very difficult.
Theorem 1 proves that, assuming exact maximization for each fixed σ, the maximizer sσ converges to the unique sparsest solution s0.
Under URP, if at most n components of a null-space vector exceed α in magnitude, its Euclidean norm is bounded by (M + 1)mα.
For a sparse solution with k ≤ n/2, the Gaussian smoothed objective provides bounds that force maximizers toward the sparse solution as σ → 0.
A stopping-based variant can guarantee the error bound involving σJ if it converges, but exceeding its threshold can slow the algorithm or cause an infinite loop.

B. Relation to minimum norm 2 solution

The minimum ℓ2-norm solution is the natural large-σ starting point for SL0. As σ tends to infinity, the maximizer of Fσ subject to As = x converges to that solution, while decreasing σ moves the estimate toward sparsity.

For sufficiently large σ, maximizing Fσ subject to As = x selects the minimum ℓ2-norm solution.
Theorem 2 characterizes this large-σ behavior for function families satisfying scaling, curvature, and related regularity conditions.
The maximizer sσ converges to the minimum ℓ2-norm solution as σ → ∞.
For the Gaussian family, the minimum ℓ2-norm solution is the optimal initialization for SL0.

C. The noisy case

The noisy-case analysis extends the noiseless theory to approximate systems As ≈ x and quantifies how observation noise limits recovery accuracy. For Gaussian smoothing, the error scales with the noise power and vanishes as the noise tends to zero.

The theory considers additive sensor noise but assumes inactive source elements are exactly zero.
The noisy analysis relaxes As = 0 to ∥As∥ < ε, with the noiseless case recovered as ε → 0.
Theorem 3 considers approximate feasible solutions Sε = {s | ∥As − x∥ < ε} and assumes a sparse solution s0 with k < n/2.
For Gaussian functions under k < n/2, solution accuracy is proportional to the noise power, with a bound of at least C · ε.
As ε → 0, choosing σ0 according to equation (31) makes sσ0 converge to s0.
Unlike the noiseless case, arbitrarily accurate solutions are impossible because the noise power bounds the achievable accuracy.

V. EXPERIMENTAL RESULTS

Experiments evaluate SL0's accuracy, robustness, parameter sensitivity, sparsity limits, and computational cost against LP and FOCUSS. SL0 is substantially faster, often achieves higher SNR, and performs especially well as sparsity approaches the uniqueness limit, although accuracy and cost impose trade-offs.

Computational cost: Two orders of magnitude faster than LP while producing better SNR in a typical run; some applications reach three orders of magnitude.The comparison is with ℓ1-magic, an interior-point LP implementation, and the paper notes an even larger speedup in Experiment 6.
Sparsity and recovery limits: SL0 outperforms LP as the number of active sources increases, with breakdown near k = 150 for c = 0.8 and k = 180 for c = 0.95.For LP and SL0 with c = 0.5, breakdown occurs near k = 100, while the theoretical limit is n/2 = 200.
Noise and accuracy: In noisy settings, SL0 achieves better SNR than LP, whereas LP performs better in the noiseless case; noisy accuracy remains bounded.The optimal σJ depends on the noise power, and accuracy cannot increase arbitrarily under noise.
Sparsity and recovery limits: SL0 and LP both degrade beyond a critical sparsity, but SL0 performs better once n exceeds 2k, the theoretical uniqueness limit for the sparsest solution.Both methods perform poorly when 2k > n; at k ≃ 10 they are similar, while at k ≃ 100 SL0 outperforms LP.
Computational cost: 38ms per sample lets SL0 solve a system with 400 equations and 1000 unknowns, compared with 30s for ℓ1-magic.Average computation time decreases from 266ms at T = 1 to 38ms at T = 10000.

VI. CONCLUSIONS

The paper shows that smoothed ℓ0 optimization yields a fast, robust approach to sparse solutions, supported by theoretical and experimental analysis. SL0 is highly faster than state-of-the-art ℓ1-based methods, tolerates noise, and works near the uniqueness limit, while parameter scheduling and convergence theory remain open issues.

Smoothed ℓ0 optimization addresses the intractable minimal-ℓ0 search while providing a smooth measure of sparsity.The smoothing also reduces the high sensitivity of the ℓ0 norm to noise.
Theorem 1 shows that SL0 is equivalent to the ℓ0 norm for a large family of functions fσ.
Theorem 2 supports initializing SL0 with the minimum ℓ2-norm solution, while Theorem 3 justifies the algorithm’s robustness.The minimum ℓ2-norm solution can serve as a rough estimate of the sparse solution.
SL0 is highly faster than state-of-the-art LP approaches, is not difficult to parameterize, works when the support size is near n/2, and is robust against noise.The n/2 condition is described as the theoretical limit for uniqueness of the sparse solution.
No theoretical rule currently determines how gradually σ should decrease, leaving convergence-related questions for future work.The paper reports that experiments nevertheless found it fairly easy to set parameters for suitable performance.
Future work includes incorporating noise directly into the model through a penalty term and testing SL0 on real-world applications such as compressed sensing.