Heuristics for exact nonnegative matrix factorization

DOI10.1007/s10898-015-0350-zzbMath1341.65057arXiv1411.7245OpenAlexW1802310826MaRDI QIDQ288239

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

Publication date: 25 May 2016

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

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

zbMATH Keywords

heuristicssimulated annealingKronecker productnonnegative matrix factorizationhybridizationexact nonnegative matrix factorizationextension complexitygrasplinear Euclidean distance matricesnonnegative rankslack matrices

Mathematics Subject Classification ID

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

Related Items

Learning without loss, Solving the maximum clique problem with symmetric rank-one non-negative matrix approximation, Extension complexity of low-dimensional polytopes, Matrix product constraints by projection methods, The NMF problem and lattice-subspaces, On Ranks of Regular Polygons, Conic optimization-based algorithms for nonnegative matrix factorization, Positive semidefinite rank and nested spectrahedra, Uniqueness of Nonnegative Matrix Factorizations by Rigidity Theory, On the linear extension complexity of regular \(n\)-gons, Algorithms for positive semidefinite factorization, Extension Complexity of Polytopes with Few Vertices or Facets, Tropical lower bound for extended formulations. II. Deficiency graphs of matrices, Unnamed Item, Common Information, Noise Stability, and Their Extensions

Uses Software

• QEPCAD

Cites Work

• On the nonnegative rank of distance matrices
• Global convergence of modified multiplicative updates for nonnegative matrix factorization
• On the linear extension complexity of regular \(n\)-gons
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Extended formulations for polygons
• Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework
• Smallest compact formulation for the permutahedron
• Worst-case results for positive semidefinite rank
• Using underapproximations for sparse nonnegative matrix factorization
• Probability matrices, non-negative rank, and parameterization of mixture models
• Real rank versus nonnegative rank
• Expressing combinatorial optimization problems by linear programs
• General local search methods
• On the geometric interpretation of the nonnegative rank
• 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
• An upper bound for nonnegative rank
• SVD based initialization: A head start for nonnegative matrix factorization
• 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
• On the Complexity of Nonnegative Matrix Factorization
• Hierarchical ALS Algorithms for Nonnegative Matrix and 3D Tensor Factorization
• The Matching Polytope has Exponential Extension Complexity
• QEPCAD B
• Lifts of Convex Sets and Cone Factorizations
• Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization
• Learning the parts of objects by non-negative matrix factorization
• Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing
• Linear vs. semidefinite extended formulations
• Computing a nonnegative matrix factorization -- provably
• On Polyhedral Approximations of the Second-Order Cone
• An Almost Optimal Algorithm for Computing Nonnegative Rank
• Extended formulations in combinatorial optimization
• Unnamed Item
• Unnamed Item