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.
Introduction
In fields like hyperspectral imaging and atmospheric spectroscopy (DOAS), researchers face the challenge of "demixing"—identifying the constituent components of a complex mixture from a spectral signature. This typically involves finding a sparse, non-negative linear combination of elements from a reference dictionary. However, real-world applications introduce significant hurdles: dictionary uncertainty (e.g., wavelength shifts or environmental variations) and high coherence among dictionary elements. When multiple similar versions of a signature are added to a dictionary to account for uncertainty, standard convex methods like Non-negative Least Squares (NNLS) or $l_1$ minimization often fail, producing a "smear" of similar elements rather than a physically meaningful sparse solution.
Structured Sparsity and Non-convex Penalties
To address these challenges, we propose a dictionary expansion strategy where each material is represented by a group of columns corresponding to different possible deformations. We then enforce structured sparsity: intra-group sparsity (picking at most one version of a material) and inter-group sparsity (using few materials overall).
The core of our approach lies in the use of non-convex penalties that promote sparsity more aggressively than the $l_1$ norm. Specifically, we utilize the Hoyer measure ($l_1/l_2$ ratio) and the difference of norms ($l_1 - l_2$). Unlike the $l_1$ norm, which penalizes magnitude and can lead to underestimation of concentrations, the $l_1/l_2$ ratio is scale-invariant. It measures the "peakiness" of a solution, creating a "forced choice" mechanism that rewards 1-sparsity in highly coherent dictionaries.
Optimization via Scaled Gradient Projection
The resulting optimization problems are non-convex. We propose a Scaled Gradient Projection algorithm that decomposes the difficult problem into a sequence of strongly convex quadratic programs. These sub-problems are solved efficiently using the Alternating Direction Method of Multipliers (ADMM). To handle the numerical instability of the $l_1/l_2$ ratio near zero, we employ a smoothing technique using the Huber function and a dummy variable strategy, ensuring the objective remains differentiable and stable.
Experimental Results
The method was validated on synthetic DOAS data and real-world hyperspectral datasets (Urban and Salinas Valley).
- DOAS Analysis: In high-noise scenarios ($\sigma = 0.05$), the proposed method correctly identified gas concentrations and wavelength shifts where standard NNLS failed.
- Hyperspectral Demixing: On the Urban dataset, the $l_1/l_2$ and $l_1 - l_2$ models significantly outperformed $l_1$ minimization, reducing the Sum of Squares Error (SSE) from ~19,107 to ~1,335–1,395. Furthermore, the solution density was reduced from 0.47 to 0.26, aligning closely with ground truth.
Conclusion
By moving beyond convex $l_1$ penalties to non-convex ratios and differences of norms, we provide a robust framework for demixing with uncertain dictionaries. This approach preserves the physical magnitude of signals while enforcing the necessary structured sparsity to resolve highly coherent dictionary elements.
Summary updated