On the Complexity of Nonnegative Matrix Factorization

DOI10.1137/070709967zbMath1206.65130arXiv0708.4149WikidataQ56533359 ScholiaQ56533359MaRDI QIDQ3586139

Publication date: 6 September 2010

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

complexity; linear programming; data mining; local search heuristic; nonnegative matrix factorization; nonnegative rank; NP hard; database analysis, information retrieval

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

15A23: Factorization of matrices

68P10: Searching and sorting

68P15: Database theory

90C60: Abstract computational complexity for mathematical programming problems

90C26: Nonconvex programming, global optimization

15B48: Positive matrices and their generalizations; cones of matrices

68P20: Information storage and retrieval of data

65Y20: Complexity and performance of numerical algorithms

65F05: Direct numerical methods for linear systems and matrix inversion

Related Items

Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization, An Almost Optimal Algorithm for Computing Nonnegative Rank, Extended formulations in combinatorial optimization, Robustness analysis of preconditioned successive projection algorithm for general form of separable NMF problem, Global convergence of modified multiplicative updates for nonnegative matrix factorization, Subtractive clustering for seeding non-negative matrix factorizations, Computing symmetric nonnegative rank factorizations, Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework, Lower bounds on nonnegative rank via nonnegative nuclear norms, Positive semidefinite rank, Worst-case results for positive semidefinite rank, Convex nonnegative matrix factorization with manifold regularization, Using underapproximations for sparse nonnegative matrix factorization, On the geometric interpretation of the nonnegative rank, Nonnegative tensor factorizations using an alternating direction method, Nonnegative rank factorization -- a heuristic approach via rank reduction, Fixed points of the EM algorithm and nonnegative rank boundaries, An upper bound for nonnegative rank, An efficient monotone projected Barzilai-Borwein method for nonnegative matrix factorization, A multilevel approach for nonnegative matrix factorization, Some \(0/1\) polytopes need exponential size extended formulations, Non-negative matrix factorization under equality constraints -- a study of industrial source identification, Exact and Heuristic Algorithms for Semi-Nonnegative Matrix Factorization, Newton-based optimization for Kullback–Leibler nonnegative tensor factorizations