Computing a nonnegative matrix factorization -- provably

DOI10.1145/2213977.2213994zbMath1286.15014arXiv1111.0952OpenAlexW2111604514MaRDI QIDQ5415472

Rong Ge, Ankur Moitra, Sanjeev Arora, Ravindran Kannan

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

data analysisnonnegative matrix factorizationsemi-algebric sets

Mathematics Subject Classification ID

Related Items (53)

Estimating Mixed Memberships With Sharp Eigenvector Deviations ⋮ Robust vertex enumeration for convex hulls in high dimensions ⋮ Low Permutation-rank Matrices: Structural Properties and Noisy Completion ⋮ Heuristics for exact nonnegative matrix factorization ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Enhancing Pure-Pixel Identification Performance via Preconditioning ⋮ Minimal positive realizations: A survey ⋮ Common information and unique disjointness ⋮ A polynomial-time algorithm for computing low CP-rank decompositions ⋮ Statistical Methods for Minimax Estimation in Linear Models with Unknown Design Over Finite Alphabets ⋮ Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions ⋮ Matrices of Bounded Psd Rank are Easy to Detect ⋮ DC-NMF: nonnegative matrix factorization based on divide-and-conquer for fast clustering and topic modeling ⋮ 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 ⋮ Approximate nonnegative rank is equivalent to the smooth rectangle bound ⋮ The Complexity of Positive Semidefinite Matrix Factorization ⋮ Smoothed separable nonnegative matrix factorization ⋮ Nonnegative Matrix Factorization Via Archetypal Analysis ⋮ Parameterized low-rank binary matrix approximation ⋮ Recovering Structured Probability Matrices ⋮ Non-Negative Sparse Regression and Column Subset Selection with L1 Error ⋮ Parameterized Low-Rank Binary Matrix Approximation ⋮ A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector ⋮ Multiscale blind source separation ⋮ Robust subspace clustering ⋮ On the geometric interpretation of the nonnegative rank ⋮ An Almost Optimal Algorithm for Computing Nonnegative Rank ⋮ Unnamed Item ⋮ Methods for nonnegative matrix factorization based on low-rank cross approximations ⋮ Analyzing Raman spectral data without separabiliy assumption ⋮ Maximum Volume Inscribed Ellipsoid: A New Simplex-Structured Matrix Factorization Framework via Facet Enumeration and Convex Optimization ⋮ Non-negative matrix factorization under equality constraints -- a study of industrial source identification ⋮ SAGA: sparse and geometry-aware non-negative matrix factorization through non-linear local embedding ⋮ Factoring a band matrix over a semiring ⋮ Trace Refinement in Labelled Markov Decision Processes ⋮ Lower bounds on nonnegative rank via nonnegative nuclear norms ⋮ Tropical lower bounds for extended formulations ⋮ Positive semidefinite rank ⋮ Convex programming based spectral clustering ⋮ Computing a Nonnegative Matrix Factorization---Provably ⋮ Toward Quantifying Vertex Similarity in Networks ⋮ An operator theoretic approach to nonparametric mixture models ⋮ Simplex-Structured Matrix Factorization: Sparsity-Based Identifiability and Provably Correct Algorithms ⋮ Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization ⋮ Provably Robust Blind Source Separation of Linear-Quadratic Near-Separable Mixtures ⋮ Multilinear Compressive Sensing and an Application to Convolutional Linear Networks ⋮ Robustness analysis of preconditioned successive projection algorithm for general form of separable NMF problem

This page was built for publication: Computing a nonnegative matrix factorization -- provably