Source-linked AI summary
A Method for Finding Structured Sparse Solutions to Non-negative Least Squares Problems with Applications
Ernie Esser, Yifei Lou, Jack Xin
TL;DR
The paper tackles sparse nonnegative demixing when dictionary uncertainty creates grouped, highly coherent expansions that challenge standard methods. It introduces Hoyer-related structured sparsity penalties and a scaled gradient projection method based on strongly convex quadratic subproblems. The approach yields stationary-point guarantees and promising DOAS and hyperspectral demixing results, while parameter choices can affect local-minimum behavior and group sparsity.
Problem
Dictionary uncertainty can require grouped expansions with intra-group and inter-group sparsity, but high coherence makes standard NNLS and greedy approaches inadequate.
Method
The paper adds Hoyer-related l1/l2 or l1-l2 penalties to NNLS-type models and solves them using scaled gradient projection with strongly convex quadratic subproblems.
Results
Any limit point of the proposed iterates is a stationary point, and numerical examples cover DOAS and hyperspectral demixing.
Takeaways & Limitations
The framework supports structured sparse demixing for grouped dictionary uncertainty in the paper's DOAS and hyperspectral examples.
Takeaways & Limitations
Penalty parameters affect behavior: large γ_j can cause bad local minima, while small γ_j may fail to enforce group 1-sparsity.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses sparse nonnegative demixing when dictionary elements are uncertain and expanded dictionaries become highly coherent. It models structured sparsity with nonconvex Hoyer-related penalties and solves the resulting models using a scaled gradient projection approach.
- Demixing estimates component quantities or concentrations by matching observed mixtures with sparse, nonnegative combinations of dictionary references.
- Dictionary uncertainty is modeled by expanding known references into grouped representative elements, including wavelength shifts and varying hyperspectral endmembers.
- Structured sparsity requires sparse or at most 1-sparse coefficients within groups and sparse activation across groups.
- Expanded dictionaries are often highly coherent, making NNLS, l1 minimization, and greedy methods unreliable for sufficiently sparse representations.
- The proposed models add Hoyer-measure penalties, based on the l1/l2 norm ratio, separately within groups and across all coefficients.
- The nonconvex models are solved through scaled gradient projection, with connections to convex splitting and difference of convex programming.
2 Problem
The paper formulates structured sparse NNLS over an expanded, grouped dictionary. Hoyer-ratio and l1-l2 penalties impose intra-group and inter-group sparsity, with smoothing or dummy variables addressing nondifferentiability near zero.
- The expanded dictionary contains grouped, l2-normalized columns, and the model estimates nonnegative coefficients for the resulting linear mixture.
- Intra-group penalties act on each coefficient group, while an inter-group penalty acts on the full coefficient vector.
- The model targets at most 1-sparse coefficients within each group, requiring sufficiently large penalty parameters γ_j.
- The sparsity penalties are either l1/l2 ratios or l1-l2 differences, both favoring vectors with smaller l1 norm relative to l2 scale.
- The Hoyer-ratio and l1-l2 penalties are nondifferentiable or discontinuous at zero, motivating regularization with a Huber-based smoothing construction.
- Regularized penalties behave more like l1 near the origin, while the paper prefers dummy variables for l1/l2 and regularization for l1-l2.
- Dummy variables provide an alternative differentiable formulation by constraining each group norm plus its dummy variable to exceed ε_j.
3 Algorithm
The algorithm minimizes a nonconvex structured-sparse objective through successive strongly convex quadratic subproblems. Its analysis establishes descent-related boundedness properties and stationarity of limit points.
- Both problem formulations are handled by convex-concave splitting and updates obtained by minimizing a quadratic upper bound over a convex constraint set.
- The algorithms connect to convex splitting, difference of convex methods, optimization transfer, and related projection algorithms.
- Each iteration solves a strongly convex quadratic program, with positive-definite quadratic terms ensuring the required subproblem curvature.
- The update is a scaled gradient projection step, interpretable as projection in a metric defined by the quadratic model.
- The method uses adaptive or fixed positive-definite matrices to control sufficient decrease while balancing convergence speed and numerical behavior.
- Under the stated assumptions, the objective decreases, iterates remain bounded, and successive iterate differences converge to zero.
- Any limit point of Algorithm 1 is a stationary point of the nonconvex model.
4 Applications
The applications model DOAS and hyperspectral demixing with expanded dictionaries, structured sparsity, and smooth background terms. These formulations allow the proposed sparsity-penalized models to address wavelength misalignment, background variation, and endmember variability.
- DOAS analysis: DOAS estimates gas concentrations from wavelength-dependent light attenuation using absorption spectra and a linear combination model after suitable transformations.The formulation accounts for scattering, smooth baselines, measurement sensitivity, and approximately white Gaussian log-noise.
- DOAS with wavelength misalignment: Wavelength misalignment is modeled by expanding each reference spectrum over a grid of linear deformations and assigning nonnegative coefficients to the resulting grouped dictionary.Each group corresponds to one gas, and at most one active coefficient selects its deformation and concentration.
- DOAS with background model: The DOAS model replaces the hard within-group l0 constraint with intra-group sparsity penalties, using sufficiently large γj values to encourage 1-sparsity.A smooth unknown background B is added with a quadratic penalty α||QB||2, and the background is treated as an unpenalized group when applying the algorithms.
- DOAS with background model: The background-smoothing operator Q penalizes high-frequency discrete sine transform coefficients of the background after subtracting its endpoint-interpolating line.The weights increase with frequency as diag(WB)i = i2, while α controls smoothing strength.
- Hyperspectral image analysis: Hyperspectral demixing estimates nonnegative material abundances across pixels while allowing expanded endmember dictionaries to represent spatially varying spectral signatures.The expansion accommodates effects such as nonlinear mixing from nonuniform dust, while structured sparsity can constrain the selected representatives.
5 Numerical Experiments
The experiments compare NNLS, l1-based, direct l0, and structured l1/l2 or l1−l2 methods on synthetic DOAS and hyperspectral demixing problems. The structured penalties generally improve sparsity while preserving coefficient accuracy, but parameter choices and initialization affect convergence and local minima.
- Experimental design: The experiments evaluate Problems 1 and 2 across DOAS alignment, DOAS background estimation, hyperspectral demixing, and structured sparse synthetic examples.Comparisons include NNLS, l1 minimization, direct l0 penalty decomposition, least squares, and the proposed structured penalties.
- Runtime and limitations: Algorithm 5 may require a good initialization or slowly increasing ρ, because incorrect initial within-group maxima can lead to a local minimum.The experiments therefore use both least-squares and NNLS initializations.
- DOAS experiments: Synthetic DOAS data uses three gases, 441 deformed references per gas, and noise standard deviations of 0, .005, and .05.One reference per gas is selected with random magnitude before additive Gaussian noise is added.
- DOAS results: The l0, l1/l2, and regularized l1−l2 models produced good, nearly equivalent DOAS solutions, although all overestimated O3 because its reference contained a large background component.HONO and NO2 amounts were correct, while the estimated displacements of HONO and O3 were correct but NO2 was not.
- Hyperspectral results: For hyperspectral demixing, l1/l2 and l1−l2 penalties encouraged sparse solutions while maintaining small average abundance-coefficient errors.NNLS had low average coefficient errors but poor sparsity, whereas l1 minimization produced sparsity with underestimated abundance magnitudes.
6 Conclusions and Future Work
The paper develops structured sparsity penalties and a difference-of-convex scaled gradient projection method for nonnegative least-squares demixing with multiple candidate references. Experiments support its use for DOAS and hyperspectral demixing, while future work targets broader optimization settings and improved parameter selection.
- Contributions: l2 and l1 − l2 penalties produce structured sparse solutions for non-negative least squares problems.The penalties can promote different sparsity levels on possibly overlapping subsets of fitting or abundance coefficients.
- Contributions: A scaled gradient projection method based on difference-of-convex programming solves the resulting models through strongly convex quadratic programs.The quadratic programs can be efficiently solved with the alternating direction method of multipliers.
- Results: 4 to 20 iterations were required in practice across all numerical examples, and limit points of the iterates were shown to be stationary points.These observations accompany the convergence analysis and computational results reported for the proposed method.
- Results: Numerical results show that the difference-of-convex approach promotes different sparsity levels in DOAS and hyperspectral image demixing problems.The applications involve possibly overlapping subsets of fitting or abundance coefficients.
- Future Work: Future work includes testing more general multiple choice quadratic knapsack problems and comparing the approach with combinatorial optimization strategies.The current applications focused on solutions that were at most 1-sparse within specified groups.
- Future Work: Future directions also include adaptive sparsity parameters and incorporating prior relative likelihoods of candidate references into the model.The experiments used fixed parameters for promoting 1-sparse solutions, while gradually increasing the parameter appeared empirically better at avoiding bad local minima.