On the geometric interpretation of the nonnegative rank

DOI10.1016/j.laa.2012.06.038zbMath1258.65039arXiv1009.0880MaRDI QIDQ1758469

Nicolas Gillis, François Glineur

Publication date: 9 November 2012

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

computational complexity; computational geometry; extended formulations; linear Euclidean distance matrices; nonnegative rank; nested polytopes problem; restricted nonnegative rank

Mathematics Subject Classification ID

15A23: Factorization of matrices

52B05: Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)

52B11: (n)-dimensional polytopes

90C27: Combinatorial optimization

15B48: Positive matrices and their generalizations; cones of matrices

65D99: Numerical approximation and computational geometry (primarily algorithms)

Related Items

On Ranks of Regular Polygons, Lifting for Simplicity: Concise Descriptions of Convex Sets, Uniqueness of Nonnegative Matrix Factorizations by Rigidity Theory, Nonnegative Matrix Factorization Requires Irrationality, Positive semidefinite rank and nested spectrahedra, A Sampling Algorithm to Compute the Set of Feasible Solutions for NonNegative Matrix Factorization with an Arbitrary Rank, Extended formulations for convex heptagons, Heuristics for exact nonnegative matrix factorization, Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank, Polytopes of minimum positive semidefinite rank, Semi-nonnegative rank for real matrices and its connection to the usual rank, On the linear extension complexity of regular \(n\)-gons, Lower bounds on nonnegative rank via nonnegative nuclear norms, Tropical lower bounds for extended formulations, Positive semidefinite rank, Worst-case results for positive semidefinite rank, Matrix product constraints by projection methods, Euclidean distance matrices and separations in communication complexity theory, Enumeration of 2-level polytopes, A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector, An efficient method for non-negative low-rank completion, Completely positive factorizations associated with Euclidean distance matrices corresponding to an arithmetic progression, The NMF problem and lattice-subspaces, Lifts of non-compact convex sets and cone factorizations, Nonnegative rank depends on the field, On the similarity to nonnegative and Metzler Hessenberg forms, Nonnegative rank factorization -- a heuristic approach via rank reduction, Polynomial size linear programs for problems in \textsc{P}, Lower bounds on matrix factorization ranks via noncommutative polynomial optimization, An upper bound for nonnegative rank, Approximate cone factorizations and lifts of polytopes, Tropical lower bound for extended formulations. II. Deficiency graphs of matrices, Exact and Heuristic Algorithms for Semi-Nonnegative Matrix Factorization, Studying Non-negative Factorizations with Tools from Linear Algebra over a Semiring, Approximation Limits of Linear Programs (Beyond Hierarchies)

Cites Work

• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Smallest compact formulation for the permutahedron
• Finding minimal nested polygons
• Probability matrices, non-negative rank, and parameterization of mixture models
• On the nonnegative rank of Euclidean distance matrices
• Non-negative matrix factorization: Ill-posedness and a geometric algorithm
• Algorithms and applications for approximate nonnegative matrix factorization
• Real rank versus nonnegative rank
• Expressing combinatorial optimization problems by linear programs
• On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
• The maximum edge biclique problem is NP-complete
• Finding minimal convex nested polygons
• Fractional biclique covers and partitions of graphs
• Euclidean Distance Matrices and Applications
• On the Complexity of Nonnegative Matrix Factorization
• Hierarchical ALS Algorithms for Nonnegative Matrix and 3D Tensor Factorization
• Low-Dimensional Polytope Approximation and Its Applications to Nonnegative Matrix Factorization
• Lectures on Polytopes
• Algorithms for polytope covering and approximation
• Constructing Extended Formulations from Reflection Relations
• Learning the parts of objects by non-negative matrix factorization
• Computing a nonnegative matrix factorization -- provably
• On Polyhedral Approximations of the Second-Order Cone
• Extended formulations in combinatorial optimization
• Unnamed Item
• Unnamed Item
• Unnamed Item