Heuristics for exact nonnegative matrix factorization

DOI10.1007/S10898-015-0350-ZzbMATH Open1341.65057arXiv1411.7245OpenAlexW1802310826MaRDI 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

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

Cited In (17)

• 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
• 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)