On the complexity of nonnegative matrix factorization
From MaRDI portal
data mininglinear programmingcomplexitynonnegative matrix factorizationnonnegative rankNP hardlocal search heuristicdatabase analysis, information retrieval
Direct numerical methods for linear systems and matrix inversion (65F05) Complexity and performance of numerical algorithms (65Y20) Information storage and retrieval of data (68P20) Factorization of matrices (15A23) Analysis of algorithms and problem complexity (68Q25) Nonconvex programming, global optimization (90C26) Searching and sorting (68P10) Abstract computational complexity for mathematical programming problems (90C60) Positive matrices and their generalizations; cones of matrices (15B48) Database theory (68P15)
Abstract: Nonnegative matrix factorization (NMF) has become a prominent technique for the analysis of image databases, text databases and other information retrieval and clustering applications. In this report, we define an exact version of NMF. Then we establish several results about exact NMF: (1) that it is equivalent to a problem in polyhedral combinatorics; (2) that it is NP-hard; and (3) that a polynomial-time local search heuristic exists.
Recommendations
Cited in
(only showing first 100 items - show all)- A sampling algorithm to compute the set of feasible solutions for nonnegative matrix factorization with an arbitrary rank
- The real nonnegative inverse eigenvalue problem is NP-hard
- Approximate nonnegative rank is equivalent to the smooth rectangle bound
- Nonnegative tensor factorizations using an alternating direction method
- Quadratic regularization projected Barzilai-Borwein method for nonnegative matrix factorization
- Robustness analysis of preconditioned successive projection algorithm for general form of separable NMF problem
- Information-theoretic approximations of the nonnegative rank
- A geometric lower bound on the extension complexity of polytopes based on the f-vector
- Accelerating nonnegative matrix factorization algorithms using extrapolation
- Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
- Coseparable Nonnegative Matrix Factorization
- Novel proximal gradient methods for nonnegative matrix factorization with sparsity constraints
- scientific article; zbMATH DE number 7404610 (Why is no real title available?)
- Lifting for simplicity: concise descriptions of convex sets
- Nonnegative matrix factorization requires irrationality
- Efficient nonnegative matrix factorization by DC programming and DCA
- Optimal Bayesian clustering using non-negative matrix factorization
- Enhanced matrix power function for cryptographic primitive construction
- Generalized conditional gradient for sparse estimation
- Block-diagonal approach to non-negative factorization of sparse linguistic matrices and tensors of extra-large dimension using the latent Dirichlet distribution
- Four algorithms to solve symmetric multi-type non-negative matrix tri-factorization problem
- Sparse convex hull coverage
- Unilateral Orthogonal Nonnegative Matrix Factorization
- Relaxation methods for constrained matrix factorization problems: solving the phase mapping problem in materials discovery
- Worst-case results for positive semidefinite rank
- Heuristics for exact nonnegative matrix factorization
- Multilinear compressive sensing and an application to convolutional linear networks
- A nonmonotone alternating updating method for a class of matrix factorization problems
- Communication tasks in operational theories
- An alternating nonmonotone projected Barzilai-Borwein algorithm of nonnegative factorization of big matrices
- Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
- Global convergence of modified multiplicative updates for nonnegative matrix factorization
- Conic optimization-based algorithms for nonnegative matrix factorization
- Partial Identifiability for Nonnegative Matrix Factorization
- Algorithms for approximate subtropical matrix factorization
- A multilevel approach for nonnegative matrix factorization
- An efficient monotone projected Barzilai-Borwein method for nonnegative matrix factorization
- A very brief introduction to nonnegative tensors from the geometric viewpoint
- The maximum feasible subset problem (maxFS) and applications
- On rationality of nonnegative matrix factorization
- Methods for nonnegative matrix factorization based on low-rank cross approximations
- Sketching for a low-rank nonnegative matrix approximation: numerical study
- Multiplicative updates for symmetric-cone factorizations
- Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Algebraic boundary of matrices of nonnegative rank at most three
- Extension complexity of low-dimensional polytopes
- On the geometric interpretation of the nonnegative rank
- Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations
- Semidefinite programming based preconditioning for more robust near-separable nonnegative matrix factorization
- Learning without loss
- Bounding the separable rank via polynomial optimization
- Factoring a band matrix over a semiring
- Using underapproximations for sparse nonnegative matrix factorization
- Computing a nonnegative matrix factorization -- provably
- On restricted nonnegative matrix factorization
- A Blind Source Separation Technique for Document Restoration
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Positive semidefinite rank
- Uniqueness of Nonnegative Matrix Factorizations by Rigidity Theory
- Refinement of Hottopixx method for nonnegative matrix factorization under noisy separability
- Convex nonnegative matrix factorization with manifold regularization
- The nonnegative rank of a matrix: hard problems, easy solutions
- Matrices of bounded psd rank are easy to detect
- Extended formulations in combinatorial optimization
- A literature survey of matrix methods for data science
- Supervised nonnegative matrix factorization via minimization of regularized Moreau-envelope of divergence function with application to music transcription
- An upper bound for nonnegative rank
- Nonnegative Tensor Train Factorizations and Some Applications
- Two to five truths in non-negative matrix factorization
- Minimal positive realizations: A survey
- Nonnegative matrix factorization with local similarity learning
- Newton-based optimization for Kullback-Leibler nonnegative tensor factorizations
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- Exact and heuristic algorithms for semi-nonnegative matrix factorization
- RP-LGMC: rating prediction based on local and global information with matrix clustering
- Matrix product constraints by projection methods
- The complexity of tropical matrix factorization
- A polynomial-time algorithm for computing low CP-rank decompositions
- Robust asymmetric non-negative matrix factorization for clustering nodes in directed networks
- A survey on deep matrix factorizations
- Non-negative matrix factorization under equality constraints -- a study of industrial source identification
- Nonnegative rank depends on the field
- Nonnegative rank factorization -- a heuristic approach via rank reduction
- Computing symmetric nonnegative rank factorizations
- PD-ML-Lite: Private Distributed Machine Learning from Lightweight Cryptography
- Orthogonal nonnegative Tucker decomposition
- Common Information, Noise Stability, and Their Extensions
- A combinatorial approach to \(L_1\)-matrix factorization
- An almost optimal algorithm for computing nonnegative rank
- Provably robust blind source separation of linear-quadratic near-separable mixtures
- Spurious Valleys, NP-Hardness, and Tractability of Sparse Matrix Factorization with Fixed Support
- A unified global convergence analysis of multiplicative update rules for nonnegative matrix factorization
- Adaptive low-nonnegative-rank approximation for state aggregation of Markov chains
- Subtractive clustering for seeding non-negative matrix factorizations
- Analyzing Raman spectral data without separabiliy assumption
- Best nonnegative rank-one approximations of tensors
- Robustness analysis of Hottopixx, a linear programming model for factoring nonnegative matrices
- Positive semidefinite rank and nested spectrahedra
- Fixed points of the EM algorithm and nonnegative rank boundaries
This page was built for publication: On the complexity of nonnegative matrix factorization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586139)
