Source-linked AI summary
Alternating Direction Algorithms for Constrained Sparse Regression: Application to Hyperspectral Unmixing
José M. Bioucas-Dias, Mário A. T. Figueiredo
TL;DR
Hyperspectral unmixing requires solving constrained regression problems for abundance estimation and sparse spectral mixtures, including cases with dependent sources and high-dimensional data. The paper introduces ADMM-based SUnSAL and C-SUnSAL algorithms, which decompose difficult problems into simpler ones and outperform an off-the-shelf optimization tool in limited experiments.
Problem
Hyperspectral unmixing involves constrained least-squares and sparse regression problems, while dependent sources and high-dimensional data challenge standard source-separation algorithms.
Method
The paper introduces SUnSAL and C-SUnSAL, alternating direction algorithms based on ADMM for solving CLS, FCLS, CSR, CBP, and CBPDN problems.
Results
The proposed algorithms clearly outperform an off-the-shelf optimization tool, achieving higher accuracy in about two orders of magnitude shorter time in the reported experiments.
Takeaways & Limitations
ADMM-based variable splitting provides convergent algorithms for several constrained sparse regression problems arising in spectral unmixing.
Takeaways & Limitations
The approach assumes the spectral matrix A is known, either as a library or as the output of an endmember extraction algorithm.
Abstract
from arXiv · showhide
Convex optimization problems are common in hyperspectral unmixing. Examples include: the constrained least squares (CLS) and the fully constrained least squares (FCLS) problems, which are used to compute the fractional abundances in linear mixtures of known spectra; the constrained basis pursuit (CBP) problem, which is used to find sparse (i.e., with a small number of non-zero terms) linear mixtures of spectra from large libraries; the constrained basis pursuit denoising (CBPDN) problem, which is a generalization of BP that admits modeling errors. In this paper, we introduce two new algorithms to efficiently solve these optimization problems, based on the alternating direction method of multipliers, a method from the augmented Lagrangian family. The algorithms are termed SUnSAL (sparse unmixing by variable splitting and augmented Lagrangian) and C-SUnSAL (constrained SUnSAL). C-SUnSAL solves the CBP and CBPDN problems, while SUnSAL solves CLS and FCLS, as well as a more general version thereof, called constrained sparse regression (CSR). C-SUnSAL and SUnSAL are shown to outperform off-the-shelf methods in terms of speed and accuracy.
1. INTRODUCTION
Hyperspectral unmixing estimates endmembers and abundances from mixed observations, but dependent sources and high dimensionality make standard source-separation methods inadequate. Sparse regression reframes unmixing over known spectral dictionaries, motivating ADMM-based algorithms for several constrained formulations.
- Hyperspectral unmixing estimates endmembers, spectral signatures, and fractional abundances from observed mixed hyperspectral vectors under a usually linear mixing assumption.
- Dependent sources and high-dimensional data place hyperspectral unmixing beyond most standard source-separation algorithms.
- Sparse regression fits mixed hyperspectral vectors with sparse linear combinations of signatures from a large, known dictionary, avoiding endmember estimation.
- CLS minimizes squared error under the ANC, FCLS adds the ASC, CBP adds ℓ1-based sparsity under the ANC, and CBPDN admits modeling errors.
- The paper introduces ADMM-based SUnSAL and C-SUnSAL algorithms to solve several constrained sparse-regression problems.
2. PROBLEM FORMULATION: CLS, FCLS, CRS, CBP, CBPDN
The paper formulates hyperspectral unmixing with a known spectral matrix and unknown abundance vector, then relates CLS, FCLS, CBP, and CBPDN through constrained sparse-regression formulations. The constraints encode abundance nonnegativity and, where applicable, sum-to-one structure, while CBPDN accommodates modeling error.
- CSR assumes a known spectral matrix A and estimates an unknown abundance vector x from an observed mixed spectral vector y.A may be a large library or the output of endmember extraction.
- The CSR approach avoids estimating endmembers, which is often a difficult problem.
- CBP is a constrained ℓ1 formulation, CBPDN generalizes it to admit modeling errors, and PCSR is equivalent to PCBPDN for suitable λ and δ choices.
3. THE ADMM
ADMM decomposes constrained optimization into simpler sequential subproblems and provides convergence guarantees under convexity and rank assumptions. The paper uses this framework as the key algorithmic tool for its unmixing methods.
- ADMM applies to problems with two functions and a linear coupling constraint, decomposing a difficult optimization problem into a sequence of simpler ones.
- The paper identifies ADMM as the key tool for its alternating-direction algorithms.
- Under full column rank of G and closed, proper, convex functions f1 and f2, ADMM converges when the problem has a solution.
- If the problem has no solution, at least one of the ADMM sequences {uk} or {dk} diverges.
4. APPLICATION OF ADMM
The paper specializes ADMM to derive SUnSAL for CSR, CLS, and FCLS, and C-SUnSAL for CBP and CBPDN. These algorithms replace ADMM substeps with problem-specific operations and satisfy convergence conditions under the stated assumptions.
- 4.1. ADMM CSR: the SUnSAL Algorithm: SUnSAL updates include solving a quadratic problem, applying soft thresholding, and projecting onto the nonnegative orthant.The nonnegativity constraint is handled through the indicator function of the first orthant.
- 4.1. ADMM CSR: the SUnSAL Algorithm: SUnSAL is obtained by replacing ADMM lines 3 and 4 with problem-specific updates for the CSR problem.The algorithm is presented in Fig. 2.
- 4.3. ADMM for CBP and CBPDN: the C-SUnSAL Algorithm: SUnSAL and C-SUnSAL converge under the paper’s convexity and rank assumptions; C-SUnSAL has complexity O(n^2) per iteration.For SUnSAL, the relevant matrix inverse can be precomputed in hyperspectral applications.
- 4.2. ADMM CLS and FCLS: For CLS, SUnSAL is run with λ = 0, while FCLS modifies step 4 to enforce the abundance sum constraint.The FCLS version is shown in Fig. 3, and its constrained quadratic update differs from the CLS version.
- 4.3. ADMM for CBP and CBPDN: the C-SUnSAL Algorithm: C-SUnSAL solves CBPDN by replacing ADMM line 3 with a quadratic update and line 4 with projections associated with the split variables.CBP is obtained as the special case δ = 0.
5. EXPERIMENTS
Experiments evaluate the proposed algorithms on simulated noisy mixtures using Gaussian and USGS spectral libraries. The algorithms achieve higher accuracy in about two orders of magnitude shorter time, while correlated USGS signatures produce lower accuracy.
- Experimental setup: Experiments use simulated mixtures y = Ax + n with additive perturbations generated by low-pass filtering Gaussian noise.The perturbations model low-pass-dominated model errors in hyperspectral applications.
- Experimental setup: The evaluation uses a 200 × 400 Gaussian library and a 224 × 498 USGS library containing selected mineral spectra.Fractional abundance vectors are generated with a specified number of nonzero components and averaged over 10 runs.
- Evaluation measures: Tables 1 and 2 report reconstruction SNR and execution times for the Gaussian and USGS libraries, respectively.Both tables report averages over 10 runs.
- Experimental setup: CLS is compared against SUnSAL using MATLAB’s lsqnonneg function as the off-the-shelf baseline.The baseline uses default options, while SUnSAL and C-SUnSAL run 200 iterations, sufficient for convergence.
- Results: The proposed algorithms achieve higher accuracy in about two orders of magnitude shorter time than the comparison methods.The paper identifies this speed advantage as critical when solving one problem instance per image pixel.
- Results: Lower accuracy with the USGS library is attributed to highly correlated spectral signatures, which make the problem harder than with the Gaussian library.
6. CONCLUDING REMARKS
The paper introduces ADMM-based algorithms for convex optimization problems in spectral unmixing and reports convergence conditions and experimental advantages over an off-the-shelf tool.
- The proposed algorithms solve a class of optimization problems arising in spectral unmixing using the alternating direction method of multipliers.ADMM decomposes a difficult problem into a sequence of simpler ones.
- Sufficient conditions for convergence are shown to be satisfied.
- Limited experiments show that the proposed algorithms clearly outperform an off-the-shelf optimization tool.The paper states that a comprehensive experimental evaluation remains ongoing work.