Computing a Nonnegative Matrix Factorization---Provably

DOI10.1137/130913869zbMath1350.68123OpenAlexW2507533531MaRDI QIDQ2817794

Ankur Moitra, Sanjeev Arora, Rong Ge, Ravindran Kannan

Publication date: 2 September 2016

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

Full work available at URL: https://doi.org/10.1137/130913869

zbMATH Keywords

separabilitynonnegative matrix factorizationprovable algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Factorization of matrices (15A23)

Related Items (8)

Nonnegative Matrix Factorization Requires Irrationality ⋮ Extension complexity of low-dimensional polytopes ⋮ Exact solutions in low-rank approximation with zeros ⋮ Nonnegative matrix factorization with local similarity learning ⋮ Conic optimization-based algorithms for nonnegative matrix factorization ⋮ Simplex-Structured Matrix Factorization: Sparsity-Based Identifiability and Provably Correct Algorithms ⋮ A novel update rule of HALS algorithm for nonnegative matrix factorization and Zangwill's global convergence ⋮ Provably Robust Blind Source Separation of Linear-Quadratic Near-Separable Mixtures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the number of separable partitions
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Extended formulations for polygons
• Solving systems of polynomial inequalities in subexponential time
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Expressing combinatorial optimization problems by linear programs
• Separable partitions
• Communication complexity and combinatorial lattice theory
• A new decision method for elementary algebra
• On the Complexity of Nonnegative Matrix Factorization
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• On the combinatorial and algebraic complexity of quantifier elimination
• 10.1162/jmlr.2003.3.4-5.993
• Learning the parts of objects by non-negative matrix factorization
• Computing a nonnegative matrix factorization -- provably
• The number of partitions of a set of N points in k dimensions induced by hyperplanes
• An Almost Optimal Algorithm for Computing Nonnegative Rank
• On the complexity of \(k\)-SAT

This page was built for publication: Computing a Nonnegative Matrix Factorization---Provably