An Almost Optimal Algorithm for Computing Nonnegative Rank
From MaRDI portal
Publication:5743610
DOI10.1137/140990139zbMath1334.68102OpenAlexW2290482318MaRDI QIDQ5743610
Publication date: 5 February 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1721.1/108665
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Vector spaces, linear dependence, rank, lineability (15A03)
Related Items
Nonnegative Matrix Factorization Requires Irrationality ⋮ Unnamed Item ⋮ Minimal positive realizations: A survey ⋮ Extension complexity of low-dimensional polytopes ⋮ Matrices of Bounded Psd Rank are Easy to Detect ⋮ Exact solutions in low-rank approximation with zeros ⋮ Parameterized low-rank binary matrix approximation ⋮ Parameterized Low-Rank Binary Matrix Approximation ⋮ Uniqueness of Nonnegative Matrix Factorizations by Rigidity Theory ⋮ Information-theoretic approximations of the nonnegative rank ⋮ Worst-case results for positive semidefinite rank ⋮ Fixed points of the EM algorithm and nonnegative rank boundaries ⋮ Common Information, Noise Stability, and Their Extensions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Common information and unique disjointness
- On the nonnegative rank of distance matrices
- Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
- Extended formulations for polygons
- Positive semidefinite rank
- The algebraic degree of semidefinite programming
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- Expressing combinatorial optimization problems by linear programs
- Communication complexity and combinatorial lattice theory
- Latent semantic indexing: A probabilistic analysis
- A new decision method for elementary algebra
- Global Optimization with Polynomials and the Problem of Moments
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- On the Complexity of Nonnegative Matrix Factorization
- On the Computational Complexity of Approximating Solutions for Real Algebraic Formulae
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- On the combinatorial and algebraic complexity of quantifier elimination
- The Matching Polytope has Exponential Extension Complexity
- Lifts of Convex Sets and Cone Factorizations
- Learning the parts of objects by non-negative matrix factorization
- Linear vs. semidefinite extended formulations
- Computing a nonnegative matrix factorization -- provably
- An information complexity approach to extended formulations
- An Almost Optimal Algorithm for Computing Nonnegative Rank
- On the complexity of \(k\)-SAT
