A Fast Gradient Method for Nonnegative Sparse Regression With Self-Dictionary

Nicolas Gillis, Robert Luce

Abstract

Nonnegative Matrix Factorization (NMF) can be computed efficiently under the separability assumption, which posits that all columns of an input data matrix reside within the cone generated by a small subset of those columns. While methods based on nonnegative sparse regression and self-dictionaries are the most robust for identifying these conic basis columns, they typically require solving large-scale, computationally intensive convex optimization problems. This paper introduces a specific nonnegative sparse regression model that reformulates the task into a smooth optimization problem by enforcing sparsity through linear constraints rather than non-smooth penalties. We demonstrate that the Euclidean projection onto the resulting polyhedron can be computed efficiently and propose a fast gradient method (FGNSR) to solve the model. Experimental results on synthetic datasets and real-world hyperspectral images show that our approach maintains the robustness of convex models while significantly improving scalability compared to state-of-the-art solvers.

Introduction

Nonnegative Matrix Factorization (NMF) is a fundamental tool in data science, used to decompose complex datasets into interpretable components. In applications such as hyperspectral unmixing or document clustering, a common simplifying premise is the separability assumption. This assumption suggests that the "pure" source signals (the basis) are already present as actual columns within the dataset.

Identifying these columns in the presence of noise, however, remains a significant challenge. Current algorithmic solutions generally fall into two categories:

  1. Greedy/Sequential Methods: Algorithms like the Successive Projection Algorithm (SPA) or Vertex Component Analysis (VCA) are computationally efficient but highly sensitive to noise. Even minor perturbations can lead these methods to select incorrect columns.
  2. Convex Optimization Models: These models are theoretically robust to noise but computationally expensive. They often rely on Second-Order Cone Programming (SOCP) solvers, which struggle to scale as the number of data points ($n$) increases, often involving $O(n^2)$ variables.

This paper bridges the gap between these two extremes by providing a method that offers the robustness of convex optimization with the efficiency required for large-scale applications.

The FGNSR Model

The core innovation of this work is a shift in how sparsity is handled within the optimization framework. Traditional robust models use non-smooth penalties (such as the $L_1$ norm) in the objective function to promote sparsity, which necessitates slower optimization techniques. In contrast, we propose a smooth objective function and move the sparsity requirement into the linear constraints.

Mathematical Formulation

We propose a model where the diagonal of a reconstruction matrix $X$ is minimized to promote row-sparsity. This is subject to constraints that prevent off-diagonal entries from exceeding the magnitude of the corresponding diagonal entries ($X_{ij} \le X_{ii}$). This specific constraint structure allows the objective function to remain quadratic and smooth.

Fast Gradient Method and Efficient Projection

To solve this smooth convex problem, we employ Nesterov’s accelerated gradient method, which achieves an optimal $O(1/k^2)$ convergence rate. The primary challenge in applying first-order methods to constrained problems is the complexity of the projection step. We derive an $O(n^2 \log n)$ algorithm to perform the Euclidean projection onto the polyhedron defined by our constraints. This efficiency ensures that the fast gradient method remains computationally viable even as the dataset grows.

Theoretical Equivalence

We prove that this smooth model is mathematically equivalent to existing $L_{1,q}$ models. Consequently, our algorithm inherits the theoretical robustness guarantees of established convex models while benefiting from a much faster numerical implementation. Furthermore, the model incorporates column weights ($w_j$), allowing it to handle unnormalized physical data more effectively than models that require columns to sum to one.

Experimental Evaluation

Synthetic "Middle Point" Datasets

We tested the algorithm against synthetic datasets designed to deceive NMF algorithms by placing noisy data points just outside the convex hull of the true basis. In these controlled environments, FGNSR successfully recovered the true basis at noise levels where greedy methods like SPA and XRAY failed entirely.

Real-World Hyperspectral Imaging (HSI)

The method was evaluated on several standard HSI datasets:

  • Urban (HYDICE): 162 spectral bands representing materials like road, grass, and metal.
  • San Diego Airport: 158 bands featuring complex man-made structures.
  • Terrain: 166 bands consisting of soil and various vegetation types.

On the "Urban" dataset, FGNSR achieved a relative reconstruction error of 5.07%, significantly outperforming VCA, which resulted in an 18.05% error.

Scalability

While FGNSR is naturally slower than the simplest greedy heuristics, it is orders of magnitude faster than commercial SOCP solvers like Gurobi. In a small-scale test case, FGNSR completed the task in 0.09s, compared to 2.78s for Gurobi—a performance gap that expands significantly as the number of data points increases. To handle images with millions of pixels, we utilize a hierarchical clustering preprocessing step to reduce the data to a representative set of centroids before applying the main algorithm.

Conclusion

The Fast Gradient Method for Nonnegative Sparse Regression (FGNSR) provides a scalable, robust solution for the near-separable NMF problem. By leveraging a smooth reformulation and an efficient projection algorithm, it achieves high accuracy on complex real-world data without the prohibitive computational costs of standard convex solvers. Future work will explore the use of random projections to further reduce dimensionality and investigate the model's performance under non-additive noise conditions.

Summary updated

Abstract

A nonnegative matrix factorization (NMF) can be computed efficiently under the <i>separability assumption</i>, which asserts that all the columns of the given input data matrix belong to the cone generated by a (small) subset of them. The provably most robust methods to identify these <i>conic basis columns</i> are based on nonnegative sparse regression and self-dictionaries, and require the solution of large-scale convex optimization problems. In this paper, we study a particular nonnegative sparse regression model with self-dictionary. As opposed to previously proposed models, this model yields a smooth optimization problem, where the sparsity is enforced through linear constraints. We show that the Euclidean projection on the polyhedron defined by these constraints can be computed efficiently, and propose a fast gradient method to solve our model. We compare our algorithm with several state-of-the-art methods on synthetic data sets and real-world hyperspectral images.A nonnegative matrix factorization (NMF) can be computed efficiently under the <i>separability assumption</i>, which asserts that all the columns of the given input data matrix belong to the cone generated by a (small) subset of them. The provably most robust methods to identify these <i>conic basis columns</i> are based on nonnegative sparse regression and self-dictionaries, and require the solution of large-scale convex optimization problems. In this paper, we study a particular nonnegative sparse regression model with self-dictionary. As opposed to previously proposed models, this model yields a smooth optimization problem, where the sparsity is enforced through linear constraints. We show that the Euclidean projection on the polyhedron defined by these constraints can be computed efficiently, and propose a fast gradient method to solve our model. We compare our algorithm with several state-of-the-art methods on synthetic data sets and real-world hyperspectral images.
BibTeX
@article{gillis2017fast,
  author = {Nicolas Gillis and Robert Luce},
  title = {{A Fast Gradient Method for Nonnegative Sparse Regression With Self-Dictionary}},
  journal = {IEEE Transactions on Image Processing},
  year = {2017},
  doi = {10.1109/tip.2017.2753400},
}

Loading related content...

Figure