Exact Sparse Nonnegative Least Squares

Nicolas Nadisic, Arnaud Vandaele, Nicolas Gillis, Jeremy E. CohenICASSP 2020 · OpenReview

Abstract

We propose a novel approach to solve exactly the sparse nonnegative least squares problem, under hard ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub> sparsity constraints. This approach is based on a dedicated branch-and-bound algorithm. This simple strategy is able to compute the optimal solution even in complicated cases such as noisy or ill-conditioned data, where traditional approaches fail. We also show that our algorithm scales well, despite the combinatorial nature of the problem. We illustrate the advantages of the proposed technique on synthetic data sets, as well as a real-world hyperspectral image.
BibTeX
@inproceedings{nadisic2020exact,
  author = {Nicolas Nadisic and Arnaud Vandaele and Nicolas Gillis and Jeremy E. Cohen},
  title = {{Exact Sparse Nonnegative Least Squares}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=pqSJb_kf-HR9},
}
Figure