A Method for Finding Structured Sparse Solutions to Nonnegative Least Squares Problems with Applications

Ernie Esser, Yifei Lou, Jack Xin

TL;DR

This paper introduces a novel method for solving structured sparse non-negative least squares (NNLS) problems, particularly useful when dealing with uncertain or redundant dictionaries. The approach uses a difference-of-convex (DC) programming framework with sparsity penalties based on the $\ell_1/\ell_2$ and $\ell_1 - \ell_2$ norms, enabling more robust solutions in applications like hyperspectral imaging and atmospheric spectroscopy.

What Problem Does This Paper Address?

Many real-world problems, such as analyzing hyperspectral images or atmospheric gas concentrations (DOAS), involve decomposing observed data into a linear combination of known reference signals (a dictionary). Often, these combinations are expected to be sparse (only a few components are present) and non-negative (concentrations can't be negative). However, a significant challenge arises when the dictionary itself is uncertain or contains highly similar, redundant "reference" signals. Standard methods like NNLS or $\ell_1$ minimization struggle with such "coherent" dictionaries, leading to inaccurate or overly dense solutions. This paper tackles this by proposing a way to model structured sparsity within groups of dictionary elements, accounting for potential variability in references.

Methods

The core of the paper lies in a novel optimization framework. Instead of directly solving the $\ell_0$ (true sparsity) problem, which is NP-hard, the authors propose using non-convex sparsity penalties based on the $\ell_1/\ell_2$ and $\ell_1 - \ell_2$ norms. These penalties are added to the standard NNLS objective function. The key innovation is that these non-convex problems are reformulated as difference-of-convex (DC) programming problems. This allows them to be solved efficiently using a scaled gradient projection algorithm that iteratively solves strongly convex quadratic programs. The method also incorporates structured sparsity assumptions, meaning that within groups of similar dictionary elements, only one or a few should be active.

Datasets

The paper evaluates its method on several synthetic and real-world datasets:

  • Synthetic DOAS data: Generated to simulate atmospheric gas measurements with varying levels of noise and wavelength misalignment.
  • Urban hyperspectral image dataset: A standard dataset used for hyperspectral unmixing.
  • Romaine lettuce hyperspectral data: A dataset from Salinas Valley, California, used to demonstrate demixing with expanded dictionaries representing material variability.

Key Insights and Ideas

  • Coherent dictionaries are problematic: Standard sparse recovery methods fail when dictionary elements are too similar.
  • Structured sparsity is key: Grouping similar dictionary elements and enforcing sparsity within these groups is crucial for handling reference variability.
  • $\ell_1/\ell_2$ and $\ell_1 - \ell_2$ as effective penalties: These non-convex norms, when used in a DC programming framework, can effectively promote structured sparsity and lead to better solutions than traditional $\ell_1$ penalties.
  • DC programming for tractability: Reformulating the problem as a difference of convex functions makes it solvable with existing optimization techniques.

Key Results

The proposed method, particularly using the $\ell_1/\ell_2$ and regularized $\ell_1 - \ell_2$ penalties, demonstrated superior performance compared to NNLS and $\ell_1$ minimization in the tested applications.

  • DOAS with wavelength misalignment: The method accurately estimated gas concentrations and their spectral displacements, outperforming other methods, especially in noisy conditions.
  • Hyperspectral Demixing: The approach achieved better sparsity and lower sum of squares errors, indicating more accurate abundance estimation, particularly when dealing with expanded dictionaries that capture endmember variability. The $\ell_1/\ell_2$ and $\ell_1 - \ell_2$ penalties were better at preserving abundance magnitudes while enforcing sparsity.

Limitations and Future Work

  • Parameter tuning: While the method is robust, optimal selection of sparsity penalty parameters ($\gamma_j, \gamma_0$) can still be empirical. The authors suggest that gradually increasing these parameters might help avoid bad local minima.
  • Combinatorial optimization: The paper suggests exploring how their variational approach compares to combinatorial optimization strategies for similar problems.
  • Alternative sparsity penalties: Investigating other sparsity-inducing penalties that can be adapted to specific datasets is a future direction.
  • Incorporating prior knowledge: If prior information about the likelihood of different dictionary elements is available, incorporating it into the model is a promising avenue.

Summary updated

Abstract

Demixing problems in many areas such as hyperspectral imaging and differential optical absorption spectroscopy (DOAS) often require finding sparse nonnegative linear combinations of dictionary elements that match observed data. We show how aspects of these problems, such as misalignment of DOAS references and uncertainty in hyperspectral endmembers, can be modeled by expanding the dictionary with grouped elements and imposing a structured sparsity assumption that the combinations within each group should be sparse or even 1-sparse. If the dictionary is highly coherent, it is difficult to obtain good solutions using convex or greedy methods, such as non-negative least squares (NNLS) or orthogonal matching pursuit. We use penalties related to the Hoyer measure, which is the ratio of the $l_1$ and $l_2$ norms, as sparsity penalties to be added to the objective in NNLS-type models. For solving the resulting nonconvex models, we propose a scaled gradient projection algorithm that requires solving a sequence of strongly convex quadratic programs. We discuss its close connections to convex splitting methods and difference of convex programming. We also present promising numerical results for example DOAS analysis and hyperspectral demixing problems.
BibTeX
@article{esser2013method,
  author = {Ernie Esser and Yifei Lou and Jack Xin},
  title = {{A Method for Finding Structured Sparse Solutions to Nonnegative Least Squares Problems with Applications}},
  journal = {SIAM J. Imaging sci},
  year = {2013},
  doi = {10.1137/13090540x},
}
Figure