Heuristics for exact nonnegative matrix factorization

DOI10.1007/S10898-015-0350-ZzbMATH Open1341.65057OpenAlexW1802310826MaRDI QIDQ288239FDOQ288239

Authors: Arnaud Vandaele, Nicolas Gillis, François Glineur, Daniel Tuyttens 

Publication date: 25 May 2016

Published in: Journal of Global Optimization (Search for Journal in Brave)

Abstract: The exact nonnegative matrix factorization (exact NMF) problem is the following: given an $m$-by-$n$ nonnegative matrix $X$ and a factorization rank $r$, find, if possible, an $m$-by-$r$ nonnegative matrix $W$ and an $r$-by-$n$ nonnegative matrix $H$ such that $X=WH$. In this paper, we propose two heuristics for exact NMF, one inspired from simulated annealing and the other from the greedy randomized adaptive search procedure. We show that these two heuristics are able to compute exact nonnegative factorizations for several classes of nonnegative matrices (namely, linear Euclidean distance matrices, slack matrices, unique-disjointness matrices, and randomly generated matrices) and as such demonstrate their superiority over standard multi-start strategies. We also consider a hybridization between these two heuristics that allows us to combine the advantages of both methods. Finally, we discuss the use of these heuristics to gain insight on the behavior of the nonnegative rank, i.e., the minimum factorization rank such that an exact NMF exists. In particular, we disprove a conjecture on the nonnegative rank of a Kronecker product, propose a new upper bound on the extension complexity of generic $n$-gons and conjecture the exact value of (i) the extension complexity of regular $n$-gons and (ii) the nonnegative rank of a submatrix of the slack matrix of the correlation polytope.

Full work available at URL: https://arxiv.org/abs/1411.7245

Recommendations

• Exact and heuristic algorithms for semi-nonnegative matrix factorization
• Nonnegative rank factorization -- a heuristic approach via rank reduction
• On the complexity of nonnegative matrix factorization
• The nonnegative matrix factorization: regularization and complexity
• On nonnegative factorization of matrices
• Algorithms and applications for approximate nonnegative matrix factorization
• Nonnegative matrix factorization with Hessian regularizer
• Computing a nonnegative matrix factorization -- provably
• Computing a nonnegative matrix factorization -- provably

zbMATH Keywords

simulated annealingheuristicsKronecker productnonnegative matrix factorizationhybridizationexact nonnegative matrix factorizationextension complexitygrasplinear Euclidean distance matricesnonnegative rankslack matrices

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Approximation methods and heuristics in mathematical programming (90C59) Factorization of matrices (15A23) Combinatorial optimization (90C27) Positive matrices and their generalizations; cones of matrices (15B48)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A short proof that the extension complexity of the correlation polytope grows exponentially
• Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework
• An almost optimal algorithm for computing nonnegative rank
• An upper bound for nonnegative rank
• Combinatorial bounds on nonnegative rank and extended formulations
• Computing a nonnegative matrix factorization -- provably
• Expressing combinatorial optimization problems by linear programs
• Extended formulations for polygons
• Extended formulations in combinatorial optimization
• Fast nonnegative matrix factorization: an active-set-like method and comparisons
• General local search methods
• Global convergence of modified multiplicative updates for nonnegative matrix factorization
• Hierarchical ALS Algorithms for Nonnegative Matrix and 3D Tensor Factorization
• Learning the parts of objects by non-negative matrix factorization
• Lifts of Convex Sets and Cone Factorizations
• Linear vs. semidefinite extended formulations
• Lower bounds in communication complexity
• Nonnegative rank depends on the field
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• On Polyhedral Approximations of the Second-Order Cone
• On the complexity of nonnegative matrix factorization
• On the geometric interpretation of the nonnegative rank
• On the linear extension complexity of regular \(n\)-gons
• On the nonnegative rank of distance matrices
• Perturbation of matrices and nonnegative rank with a view toward statistical models
• Polygons as sections of higher-dimensional polytopes
• Probability matrices, non-negative rank, and parameterization of mixture models
• QEPCAD B
• Rational and real positive semidefinite rank can be different
• Real rank versus nonnegative rank
• SVD based initialization: A head start for nonnegative matrix factorization
• Semidefinite programming based preconditioning for more robust near-separable nonnegative matrix factorization
• Smallest compact formulation for the permutahedron
• Sparse and unique nonnegative matrix factorization through data preprocessing
• Using underapproximations for sparse nonnegative matrix factorization
• Worst-case results for positive semidefinite rank

Cited In (18)

• Title not available (Why is that?)
• Tropical lower bound for extended formulations. II: Deficiency graphs of matrices
• On the complexity of nonnegative matrix factorization
• Algorithms for positive semidefinite factorization
• Conic optimization-based algorithms for nonnegative matrix factorization
• On the linear extension complexity of regular \(n\)-gons
• Extension complexity of low-dimensional polytopes
• Learning without loss
• Uniqueness of Nonnegative Matrix Factorizations by Rigidity Theory
• On ranks of regular polygons
• Exact and heuristic algorithms for semi-nonnegative matrix factorization
• Matrix product constraints by projection methods
• Common Information, Noise Stability, and Their Extensions
• Solving the maximum clique problem with symmetric rank-one non-negative matrix approximation
• The NMF problem and lattice-subspaces
• Positive semidefinite rank and nested spectrahedra
• A variable neighborhood search heuristic for nonnegative matrix factorization with application to microarray data
• Extension complexity of polytopes with few vertices or facets

Uses Software

• QEPCAD

This page was built for publication: Heuristics for exact nonnegative matrix factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q288239)