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

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.