Branch-and-bound algorithm for exact ℓ0-norm sparse spectral unmixing

Résumé

We propose an algorithm that exactly solves the cardinality-constrained sparse spectral unmixing problem. Based on recent works on ℓ0-norm exact optimization, a branch-and-bound architecture is specifically developed for sparse unmixing, under nonnegativity and sum-to-one constraints. The procedure boils down to solving a finite number of sum-to-one constrained nonnegative least-squares problems for upper-and lower-bounding the global optimal value, which are solved efficiently. Numerical simulations show that our method outperforms competing ones in terms of support identification and estimation, and that it remains computationally tractable as long as the problem size is limited or the signal-to-noise ratio is high enough. A free C++ implementation is made available.