On the Complexity of Nonnegative Matrix Factorization
From MaRDI portal
Publication:3586139
DOI10.1137/070709967zbMath1206.65130arXiv0708.4149OpenAlexW2124172487WikidataQ56533359 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
complexitylinear programmingdata mininglocal search heuristicnonnegative matrix factorizationnonnegative rankNP harddatabase analysis, information retrieval
Analysis of algorithms and problem complexity (68Q25) Factorization of matrices (15A23) Searching and sorting (68P10) Database theory (68P15) Abstract computational complexity for mathematical programming problems (90C60) Nonconvex programming, global optimization (90C26) Positive matrices and their generalizations; cones of matrices (15B48) Information storage and retrieval of data (68P20) Complexity and performance of numerical algorithms (65Y20) Direct numerical methods for linear systems and matrix inversion (65F05)
Related Items
The maximum feasible subset problem (maxFS) and applications, Partial Identifiability for Nonnegative Matrix Factorization, Nonnegative Matrix Factorization Requires Irrationality, Heuristics for exact nonnegative matrix factorization, Lifting for Simplicity: Concise Descriptions of Convex Sets, Learning without loss, Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank, A very brief introduction to nonnegative tensors from the geometric viewpoint, Algebraic boundary of matrices of nonnegative rank at most three, Bounding the separable rank via polynomial optimization, Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations, Newton-based optimization for Kullback–Leibler nonnegative tensor factorizations, Minimal positive realizations: A survey, A polynomial-time algorithm for computing low CP-rank decompositions, Exact and Heuristic Algorithms for Semi-Nonnegative Matrix Factorization, A Nonmonotone Alternating Updating Method for a Class of Matrix Factorization Problems, Supervised nonnegative matrix factorization via minimization of regularized Moreau-envelope of divergence function with application to music transcription, Extension complexity of low-dimensional polytopes, Matrices of Bounded Psd Rank are Easy to Detect, Matrix product constraints by projection methods, A survey on deep matrix factorizations, RP-LGMC: rating prediction based on local and global information with matrix clustering, Refinement of Hottopixx Method for Nonnegative Matrix Factorization Under Noisy Separability, Enhanced matrix power function for cryptographic primitive construction, Convex nonnegative matrix factorization with manifold regularization, Sketching for a low-rank nonnegative matrix approximation: numerical study, Coseparable Nonnegative Matrix Factorization, A literature survey of matrix methods for data science, The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions, Nonnegative matrix factorization with local similarity learning, Approximate nonnegative rank is equivalent to the smooth rectangle bound, Spurious Valleys, NP-Hardness, and Tractability of Sparse Matrix Factorization with Fixed Support, Conic optimization-based algorithms for nonnegative matrix factorization, Novel Proximal Gradient Methods for Nonnegative Matrix Factorization with Sparsity Constraints, Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks, Unilateral Orthogonal Nonnegative Matrix Factorization, A multilevel approach for nonnegative matrix factorization, On \(\epsilon\)-sensitive monotone computations, A Blind Source Separation Technique for Document Restoration, Nonnegative tensor factorizations using an alternating direction method, Some \(0/1\) polytopes need exponential size extended formulations, Positive semidefinite rank and nested spectrahedra, Quadratic regularization projected Barzilai-Borwein method for nonnegative matrix factorization, Efficient Nonnegative Matrix Factorization by DC Programming and DCA, Computing symmetric nonnegative rank factorizations, Global convergence of modified multiplicative updates for nonnegative matrix factorization, Algorithms for approximate subtropical matrix factorization, Nonnegative rank depends on the field, Nonnegative Tensor Train Factorizations and Some Applications, Sparse convex hull coverage, Block-diagonal approach to non-negative factorization of sparse linguistic matrices and tensors of extra-large dimension using the latent Dirichlet distribution, Orthogonal Nonnegative Tucker Decomposition, Uniqueness of Nonnegative Matrix Factorizations by Rigidity Theory, Subtractive clustering for seeding non-negative matrix factorizations, A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector, An alternating nonmonotone projected Barzilai-Borwein algorithm of nonnegative factorization of big matrices, The real nonnegative inverse eigenvalue problem is NP-hard, Nonnegative rank factorization -- a heuristic approach via rank reduction, Using underapproximations for sparse nonnegative matrix factorization, On the geometric interpretation of the nonnegative rank, An Almost Optimal Algorithm for Computing Nonnegative Rank, Extended formulations in combinatorial optimization, Relaxation methods for constrained matrix factorization problems: solving the phase mapping problem in materials discovery, Information-theoretic approximations of the nonnegative rank, Methods for nonnegative matrix factorization based on low-rank cross approximations, Analyzing Raman spectral data without separabiliy assumption, A unified global convergence analysis of multiplicative update rules for nonnegative matrix factorization, Non-negative matrix factorization under equality constraints -- a study of industrial source identification, Best Nonnegative Rank-One Approximations of Tensors, Optimal Bayesian clustering using non-negative matrix factorization, Factoring a band matrix over a semiring, Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework, Trace Refinement in Labelled Markov Decision Processes, Accelerating Nonnegative Matrix Factorization Algorithms Using Extrapolation, Lower bounds on nonnegative rank via nonnegative nuclear norms, Positive semidefinite rank, Worst-case results for positive semidefinite rank, Computing a Nonnegative Matrix Factorization---Provably, Nonnegative tensor train factorization with DMRG technique, Adaptive Low-Nonnegative-Rank Approximation for State Aggregation of Markov Chains, Generalized Conditional Gradient for Sparse Estimation, Lower bounds on matrix factorization ranks via noncommutative polynomial optimization, Unnamed Item, A novel update rule of HALS algorithm for nonnegative matrix factorization and Zangwill's global convergence, Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization, Fixed points of the EM algorithm and nonnegative rank boundaries, An upper bound for nonnegative rank, A Sampling Algorithm to Compute the Set of Feasible Solutions for NonNegative Matrix Factorization with an Arbitrary Rank, An efficient monotone projected Barzilai-Borwein method for nonnegative matrix factorization, Common Information, Noise Stability, and Their Extensions, Communication tasks in operational theories, Provably Robust Blind Source Separation of Linear-Quadratic Near-Separable Mixtures, Multilinear Compressive Sensing and an Application to Convolutional Linear Networks, Four algorithms to solve symmetric multi-type non-negative matrix tri-factorization problem, Robustness analysis of preconditioned successive projection algorithm for general form of separable NMF problem
