EUROPT 2024
Abstract Submission

123. Matrix-wise L0-constrained Sparse Nonnegative Least Squares

Invited abstract in session TB-4: Optimization in regression, classification and learning II, stream Optimization in regression, classification and learning.

Thursday, 10:05 - 11:20
Room: M:M

Authors (first author is the speaker)

1. Nicolas Nadisic
Ghent University and Royal Institute for Cultural Heritage (KIK-IRPA)
2. Arnaud Vandaele
Mathematics and Operations Research, University of Mons
3. Jeremy Cohen
CNRS
4. Nicolas Gillis
Mathematics and Operational Research, Université de Mons

Abstract

Nonnegative least squares problems with multiple right-hand sides (MNNLS) arise in models that rely on additive linear combinations. In particular, they are at the core of most nonnegative matrix factorization algorithms and have many applications. The nonnegativity constraint is known to naturally favor sparsity, that is, solutions with few non-zero entries. However, it is often useful to further enhance this sparsity, as it improves the interpretability of the results and helps reducing noise, which leads to the sparse MNNLS problem. In this paper, as opposed to most previous works that enforce sparsity column- or row-wise, we first introduce a novel formulation for sparse MNNLS, with a matrix-wise sparsity constraint. Then, we present a two-step algorithm to tackle this problem. The first step divides sparse MNNLS in subproblems, one per column of the original problem. It then uses different algorithms to produce, either exactly or approximately, a Pareto front for each subproblem, that is, to produce a set of solutions representing different tradeoffs between reconstruction error and sparsity. The second step selects solutions among these Pareto fronts in order to build a sparsity-constrained matrix that minimizes the reconstruction error. We perform experiments on facial and hyperspectral images, and we show that our proposed two-step approach provides more accurate results than state-of-the-art sparse coding heuristics applied both column-wise and globally.

Keywords

Status: accepted

Back to the list of papers