Matrix tri-factorizations (MTFs) aim to decompose an input matrix X into the product of three factor matrices, instead of only two as in standard matrix factorization (MF). In contrast to MF, MTF is able to cluster both rows and columns of X while quantifying the relationship among these two groups of clusters. When dealing with binary input matrices, Boolean matrix factorization (BMF) is a natural extension of MF. In this work we focus on Boolean matrix tri-factorization (BMTF) that extends BMF to the tri-factorization framework. We first show an identifiability result for BMTF, namely, we show that the factors are unique under certain sparsity conditions. Then we propose an algorithm to compute the factors of BMTF, and perform numerical experiments to show how it performs on synthetic and real data.

Mixture models are traditionally represented and learned by adding several distributions as components. Allowing mixtures to subtract probability mass or density can drastically reduce the number of components needed to model complex distributions. However, learning such subtractive mixtures while ensuring they still encode a non-negative function is challenging. We investigate how to learn and perform inference on deep subtractive mixtures by squaring them. We do this in the framework of probabilistic circuits, which enable us to represent tensorized mixtures and generalize several other subtractive models. We theoretically prove that the class of squared circuits allowing subtractions can be exponentially more expressive than traditional additive mixtures; and, we empirically show this increased expressiveness on a series of real-world distribution estimation tasks.

Deep nonnegative matrix factorization (deep NMF) has recently emerged as a valuable technique for extracting multiple layers of features across different scales. However, all existing deep NMF models and algorithms have primarily centered their evaluation on the least squares error, which may not be the most appropriate metric for assessing the quality of approximations on diverse data sets. For instance, when dealing with data types such as audio signals and documents, it is widely acknowledged that ß-divergences offer a more suitable alternative. In this article, we develop new models and algorithms for deep NMF using some ß-divergences, with a focus on the Kullback-Leibler divergence. Subsequently, we apply these techniques to the extraction of facial features, the identification of topics within document collections, and the identification of materials within hyperspectral images.

Abstract. Simplex-structured matrix factorization (SSMF), closely related to nonnegative matrix factorization, is a fundamental interpretable data analysis model and has applications in hyperspectral unmixing and topic modeling. To obtain identifiable solutions, a standard approach is to find minimum-volume solutions. By taking advantage of the duality/polarity concept for polytopes, we convert minimum-volume SSMF in the primal space to a maximum-volume problem in the dual space. We first prove the identifiability of this maximum-volume dual problem. Then, we use this dual formulation to provide a novel optimization approach which bridges the gap between two existing families of algorithms for SSMF, namely volume minimization and facet identification. Numerical experiments show that the proposed approach performs favorably compared to the state-of-the-art SSMF algorithms.

The sufficiently scattered condition (SSC) is a key condition in the study of identifiability of various matrix factorization problems, including nonnegative, minimum-volume, symmetric, simplex-structured, and polytopic matrix factorizations. The SSC allows one to guarantee that the computed matrix factorization is unique/identifiable, up to trivial ambiguities. However, this condition is NP-hard to check in general. In this letter, we show that it can however be checked in a reasonable amount of time in realistic scenarios, when the factorization rank is not too large. This is achieved by formulating the problem as a non-convex quadratic optimization problem over a bounded set. We use the global non-convex optimization software Gurobi, and showcase the usefulness of this code on real-world hyperspectral images.

Semi-binary matrix factorization (semi-BMF) is a matrix decomposition model where the elements of one factor are binary. Semi-BMF can be interpreted as a generalization of k - means, and can be employed in clustering problems such as community detection. In the absence of noise, Kueng and Tropp (SIAM J. Math. Data Sc., 2021) have recently proposed a provably correct algorithm for semi-BMF that require to solve semidefinite programs (SDPs). In this paper, we extend their approach in the presence of noise. Moreover, since standard solvers for SDP rely on interior-point methods and do not scale well, we also propose a first-order method to reduce the computational costs. We test our new algorithms on synthetic data, and show that they compare favorably with the state of the art.

In this paper, we introduce TITAN, a novel inerTIal block majorizaTion minimizAtioN ramework for nonsmooth nonconvex optimization problems. To the best of our knowledge, TITAN is the first framework of block-coordinate update method that relies on the majorization-minimization framework while embedding inertial force to each step of the block updates. The inertial force is obtained via an extrapolation operator that subsumes heavy-ball and Nesterov-type accelerations for block proximal gradient methods as special cases. By choosing various surrogate functions, such as proximal, Lipschitz gradient, Bregman, quadratic, and composite surrogate functions, and by varying the extrapolation operator, TITAN produces a rich set of inertial block-coordinate update methods. We study sub-sequential convergence as well as global convergence for the generated sequence of TITAN. We illustrate the effectiveness of TITAN on two important machine learning problems, namely sparse non-negative matrix factorization and matrix completion.

Subspace clustering is an unsupervised approach for determining the union of multiple subspaces that best fits a collection of high-dimensional samples. Self-expressive representation, that is, expressing samples as linear combination of other samples, is the core of most state-of-the-art subspace clustering approaches. However, existence of sufficiently well-spread samples within each subspace is crucial for precise representation, which might not always be available in real-world scenarios. Inspired by the remarkable influence of data augmentation on the performance of neural networks, we propose a scalable approach that employs data augmentation within subspace clustering. Benefiting from the increased diversity in data, we use augmented samples as an enlarged dictionary and combine the self-expressive representations based on the assumption that augmentation does not alter the labels of the samples. Significant improvement of the clustering performance on two real-world datasets demonstrates the effectiveness of the proposed approach.

In this paper, we propose a new low-rank matrix factorization model, dubbed bounded simplex-structured matrix factorization (BSSMF). Given an input matrix X and a factorization rank r, BSSMF looks for a matrix W with r columns and a matrix H with r rows such that X ≈ W H where the entries in each column of W are bounded, that is, they belong to given intervals, and the columns of H belong to the unit simplex, that is, H is column stochastic. BSSMF generalizes nonnegative matrix factorization (NMF), and simplex-structured matrix factorization (SSMF). BSSMF is particularly well suited when the entries of the input matrix X themselves belong to a given interval; for example when the columns of X represent images. In this paper, we first provide identifiability conditions for BSSMF, that is, we provide conditions under which BSSMF admits a unique decomposition, up to trivial ambiguities. Then we propose a fast inertial algorithm for BSSMF. Finally, we illustrate the effectiveness of BSSMF to obtain interpretable features in the MNIST dataset.

Nonnegative matrix factorization (NMF) is a linear dimensionality reduction technique for analyzing nonnegative data. A key aspect of NMF is the choice of the objective function that depends on the noise model (or statistics of the noise) assumed on the data. In many applications, the noise model is unknown and difficult to estimate. In this paper, we define a multi-objective NMF (MO-NMF) problem, where several objectives are combined within the same NMF model. We propose to use Lagrange duality to judiciously optimize for a set of weights to be used within the framework of the weighted-sum approach, that is, we minimize a single objective function which is a weighted sum of the all objective functions. We design a simple algorithm based on multiplicative updates to minimize this weighted sum. We show how this can be used to find distributionally robust NMF (DR-NMF) solutions, that is, solutions that minimize the largest error among all objectives, using a dual approach solved via a heuristic inspired from the Frank-Wolfe algorithm. We illustrate the effectiveness of this approach on synthetic, document and audio data sets. The results show that DR-NMF is robust to our incognizance of the noise model of the NMF problem.

We introduce a new Nonnegative Matrix Factorization (NMF) model called Nonnegative Unimodal Matrix Factorization (NuMF), which adds on top of NMF the unimodal condition on the columns of the basis matrix. NuMF finds applications for example in analytical chemistry. We propose a simple but naive brute-force heuristics strategy based on accelerated projected gradient. It is then improved by using multi-grid for which we prove that the restriction operator preserves the unimodality. We also present two preliminary results regarding the uniqueness of the solution, that is, the identifiability, of NuMF. Empirical results on synthetic and real datasets confirm the effectiveness of the algorithm and illustrate the theoretical results on NuMF.

Nonnegative matrix factorization (NMF) is a linear dimensionality technique for nonnegative data with applications such as image analysis, text mining, audio source separation, and hyperspectral unmixing. Given a data matrix M and a factorization rank r, NMF looks for a nonnegative matrix W with r columns and a nonnegative matrix H with r rows such that M ≈ WH. NMF is NP-hard to solve in general. However, it can be computed efficiently under the separability assumption which requires that the basis vectors appear as data points, that is, that there exists an index set K such that W = M(:,K). In this article, we generalize the separability assumption. We only require that for each rank-one factor W(:,k)H(k,:) for k=1,2,…,r, either W(:,k) = M(:,j) for some j or H(k,:) = M(i,:) for some i. We refer to the corresponding problem as generalized separable NMF (GS-NMF). We discuss some properties of GS-NMF and propose a convex optimization model which we solve using a fast gradient method. We also propose a heuristic algorithm inspired by the successive projection algorithm. To verify the effectiveness of our methods, we compare them with several state-of-the-art separable NMF and standard NMF algorithms on synthetic, document and image data sets.

In this work, we consider the problem of blind source separation (BSS) by departing from the usual linear model and focusing on the linear-quadratic (LQ) one. We propose two provably robust and computationally tractable algorithms to tackle this problem under separability assumptions which require the sources to appear as samples in the data set. The first algorithm, referred to as SNPALQ, generalizes the successive nonnegative projection algorithm (SNPA), designed for linear BSS. By explicitly modeling the product terms inherent to the LQ model along the iterations of the SNPA scheme, the nonlinear contributions of the mixing are mitigated, thus improving the separation quality. SNPALQ is shown to be able to recover the ground truth factors that generated the data, even in the presence of noise. The second algorithm is a brute force (BF) algorithm, which can be used as a postprocessing step for SNPALQ. It then enables one to discard the spurious (mixed) samples extracted by SNPALQ, thus broadening its applicability. The BF is in turn shown to be robust to noise (under potentially easier-to-check conditions than those of SNPALQ). We show that SNPALQ with and without the BF postprocessing is relevant in realistic numerical experiments.

Tensor decompositions have become a central tool in machine learning to extract interpretable patterns from multiway arrays of data. However, computing the approximate Canonical Polyadic Decomposition (aCPD), one of the most important tensor decomposition model, remains a challenge. In this work, we propose several algorithms based on extrapolation that improve over existing alternating methods for aCPD. We show on several simulated and real data sets that carefully designed extrapolation can significantly improve the convergence speed hence reduce the computational time, especially in difficult scenarios.

We propose a novel approach to solve exactly the sparse nonnegative least squares problem, under hard ℓ0sparsity 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.

We propose inertial versions of block coordinate descent methods for solving non-convex non-smooth composite optimization problems. Our methods possess three main advantages compared to current state-of-the-art accelerated first-order methods: (1) they allow using two different extrapolation points to evaluate the gradients and to add the inertial force (we will empirically show that it is more efficient than using a single extrapolation point), (2) they allow to randomly select the block of variables to update, and (3) they do not require a restarting step. We prove the subsequential convergence of the generated sequence under mild assumptions, prove the global convergence under some additional assumptions, and provide convergence rates. We deploy the proposed methods to solve non-negative matrix factorization (NMF) and show that they compete favorably with the state-of-the-art NMF algorithms. Additional experiments on non-negative approximate canonical polyadic decomposition, also known as nonnegative tensor factorization, are also provided.

Nonnegative matrix factorization (NMF) is a widely used linear dimensionality reduction technique for nonnegative data. NMF requires that each data point is approximated by a convex combination of basis elements. Archetypal analysis (AA), also referred to as convex NMF, is a well-known NMF variant imposing that the basis elements are themselves convex combinations of the data points. AA has the advantage to be more interpretable than NMF because the basis elements are directly constructed from the data points. However, it usually suffers from a high data fitting error because the basis elements are constrained to be contained in the convex cone of the data points. In this letter, we introduce near-convex archetypal analysis (NCAA) which combines the advantages of both AA and NMF. As for AA, the basis vectors are required to be linear combinations of the data points and hence are easily interpretable. As for NMF, the additional flexibility in choosing the basis elements allows NCAA to have a low data fitting error. We show that NCAA compares favorably with a state-of-the-art minimum-volume NMF method on synthetic datasets and on a real-world hyperspectral image.

In this paper we consider a variant of the dictionary learning problem where the dictionary has full rank, the coefficients have a fixed sparsity level, and both the coefficients and the dictionary are nonnegative. It is equivalent to k-sparse nonnegative matrix factorization (K-NMF). This model is encountered in source separation where nonnegative linear combinations of a few components generate the data points (samples), such as in hyperspectral images. We first discuss the impact of nonnegativity on the identifiability of low-rank sparse component analysis (LRSCA), building upon recent advances. Then, as a main contribution, we propose two algorithms to train K-NMF: one based on alternating optimization and exact sparse coding, the other based on a nonnegative variant of K-subspace. We show on noiseless simulated data that our methods outperform by a large margin the state of the art. Finally, we apply our methods for the spectral unmixing of a hyperspectral image.

In this paper, we consider the following low-rank matrix approximation problem, referred to as separable simplex-structured matrix factorization: given an input matrix X, find W and H such that X ≈ WH where the columns of W are chosen among the columns of X and where the entries of each column of H are nonnegative and sum to at most one. This problem has been studied extensively in the literature and is a generalization of separable nonnegative matrix factorization, with applications for example in hyperspectral unmixing and document analysis. Many methods have been proposed to tackle this problem; the three main classes are greedy algorithms, convex relaxations and combinatorial approaches. For the first two classes, robustness to noise of several algorithms have been characterized precisely. As far as we know, no such result exist for combinatorial formulations. This paper fills in this gap: we provide a tight robustness analysis of an exact combinatorial formulation of the problem. Although such formulations are difficult to optimize, we show that they lead to stronger robustness to noise than greedy algorithms and convex relaxations.

In recent years, nonnegative matrix factorization (NMF) with volume regularization has been shown to be a powerful identifiable model; for example for hyperspectral unmixing, document classification, community detection and hidden Markov models. In this paper, we show that minimum-volume NMF (min-vol NMF) can also be used when the basis matrix is rank deficient, which is a reasonable scenario for some real-world NMF problems (e.g., for unmixing multispectral images). We propose an alternating fast projected gradient method for min-vol NMF and illustrate its use on rank-deficient NMF problems; namely a synthetic data set and a multispectral image.

We propose a general framework to accelerate significantly the algorithms for nonnegative matrix factorization (NMF). This framework is inspired from the extrapolation scheme used to accelerate gradient methods in convex optimization and from the method of parallel tangents. However, the use of extrapolation in the context of the exact coordinate descent algorithms tackling the nonconvex NMF problems is novel. We illustrate the performance of this approach on two state-of-the-art NMF algorithms: accelerated hierarchical alternating least squares and alternating nonnegative least squares, using synthetic, image, and document data sets.

Spectral unmixing aims at recovering the spectral signatures of materials, called endmembers, mixed in a hyperspectral image (HSI) or multispectral image, along with their abundances. A typical assumption is that the image contains one pure pixel per endmember, in which case spectral unmixing reduces to identifying these pixels. Many fully automated methods have been proposed in recent years, but little work has been done to allow users to select areas where pure pixels are present manually or using a segmentation algorithm. Additionally, in a nonblind approach, several spectral libraries may be available rather than a single one, with a fixed number (or an upper or lower bound) of endmembers to chose from each. In this letter, we propose a multiple-dictionary constrained low-rank matrix approximation model that addresses these two problems. We propose an algorithm to compute this model, dubbed multiple matching pursuit alternating least squares, and its performance is discussed on both synthetic and real HSIs.

A nonnegative matrix factorization (NMF) can be computed efficiently under the separability assumption, 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 conic basis columns 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.

In this paper, we analyze different preconditionings designed to enhance robustness of pure-pixel search algorithms, which are used for blind hyperspectral unmixing and which are equivalent to near-separable nonnegative matrix factorization algorithms. Our analysis focuses on the successive projection algorithm (SPA), a simple, efficient, and provably robust algorithm. Recently, a provably robust preconditioning was proposed by Gillis and Vavasis [SIAM J. Optim., 25 (2015), pp. 677--698] which requires the resolution of a semidefinite program (SDP). Since solving the SDP in high precisions can be time consuming, we generalize the robustness analysis to approximate solutions of the SDP showing that a high accuracy solution is not crucial for robustness, paving the way for faster preconditionings. This first contribution also allows us to provide a robustness analysis for two other preconditionings. The first one is prewhitening, which can be interpreted as an optimal solution of the same SDP with additional constraints. We analyze the robustness of prewhitening, which allows us to characterize situations in which it performs competitively with the SDP-based preconditioning. The second one is based on SPA itself and can be interpreted as an optimal solution of a relaxation of the SDP. It is extremely fast when competing with the SDP-based preconditioning on several synthetic data sets.

In this paper, we design a fast hierarchical clustering algorithm for high-resolution hyperspectral images (HSI). At the core of the algorithm, a new rank-two nonnegative matrix factorization (NMF) algorithm is used to split the clusters, which is motivated by convex geometry concepts. The method starts with a single cluster containing all pixels and, at each step, performs the following: 1) selects a cluster in such a way that the error at the next step is minimized and 2) splits the selected cluster into two disjoint clusters using rank-two NMF in such a way that the clusters are well balanced and stable. The proposed method can also be used as an endmember extraction algorithm in the presence of pure pixels. The effectiveness of this approach is illustrated on several synthetic and real-world HSIs and is shown to outperform standard clustering techniques such as k-means, spherical k-means, and standard NMF.

In this paper, we study the nonnegative matrix factorization problem under the separability assumption (that is, there exists a cone spanned by a small subset of the columns of the input nonnegative data matrix containing all columns), which is equivalent to the hyperspectral unmixing problem under the linear mixing model and the pure-pixel assumption. We present a family of fast recursive algorithms and prove they are robust under any small perturbations of the input data matrix. This family generalizes several existing hyperspectral unmixing algorithms and hence provides for the first time a theoretical justification of their better practical performance.

In this paper, we propose a new fast and robust recursive algorithm for near-separable nonnegative matrix factorization, a particular nonnegative blind source separation problem. This algorithm, which we refer to as the successive nonnegative projection algorithm (SNPA), is closely related to the popular successive projection algorithm (SPA) but takes advantage of the nonnegativity constraint in the decomposition. We prove that SNPA is more robust than SPA and can be applied to a broader class of nonnegative matrices. This is illustrated on some synthetic data sets and on a real-world hyperspectral image.

Nonnegative matrix factorization (NMF) is a data analysis technique used in a great variety of applications such as text mining, image processing, hyperspectral data analysis, computational biology, and clustering. In this letter, we consider two well-known algorithms designed to solve NMF problems: the multiplicative updates of Lee and Seung and the hierarchical alternating least squares of Cichocki et al. We propose a simple way to significantly accelerate these schemes, based on a careful analysis of the computational cost needed at each iteration, while preserving their convergence properties. This acceleration technique can also be applied to other algorithms, which we illustrate on the projected gradient method of Lin. The efficiency of the accelerated algorithms is empirically demonstrated on image and text data sets and compares favorably with a state-of-the-art alternating nonnegative least squares algorithm.

In this study, we use nonnegative matrix factorization (NMF) and nonnegative matrix underapproximation (NMU) approaches to generate feature vectors that can be used to cluster aviation safety reporting system (ASRS) documents obtained from the distributed national ASAP archive (DNAA). By preserving nonnegativity, both the NMF and NMU facilitate a sum-of-parts representation of the underlying term usage patterns in the ASRS document collection. Both the training and test sets of ASRS documents are parsed and then factored by both algorithms to produce a reduced-rank representations of the entire document space. The resulting feature and coefficient matrix factors are used to cluster ASRS documents so that the (known) associated anomalies of training documents are directly mapped to the feature vectors. Dominant features of test documents are then used to generate anomaly relevance scores for those documents.We demonstrate that the approximate solution obtained by NMU using Lagrangrian duality can lead to a better sum-of-parts representation and document classification accuracy.