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