A polynomial-time algorithm for computing low CP-rank decompositions

DOI10.1016/J.IPL.2016.09.004zbMath1392.68200OpenAlexW2518945775MaRDI QIDQ344517

Trung Thanh Nguyen, Khaled M. Elbassioni

Publication date: 23 November 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2016.09.004

zbMATH Keywords

computational complexitypolynomial-time algorithmcompletely positive matrixCP-decompositionCP-rank

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Positive matrices and their generalizations; cones of matrices (15B48)

Related Items (1)

Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions

Uses Software

• SymNMF

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the computational complexity of membership problems for the completely positive cone and its dual
• The structure of completely positive matrices according to their CP-rank and CP-plus-rank
• On nonnegative factorization of matrices
• Computing symmetric nonnegative rank factorizations
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• On reduced rank nonnegative matrix factorization for symmetric nonnegative matrices
• A note on the computation of the CP-rank
• On the parameterization of the CreditRisk\(^+\) model for estimating credit portfolio risk
• On the computation of \(C^*\) certificates
• A note on upper bounds on the cp-rank
• Solving systems of polynomial inequalities in subexponential time
• Nonnegative factorization of positive semidefinite nonnegative matrices
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• The maximal cp-rank of rank \(k\) completely positive matrices
• SymNMF: nonnegative low-rank approximation of a similarity matrix for graph clustering
• On the copositive representation of binary and continuous nonconvex quadratic programs
• On the Complexity of Nonnegative Matrix Factorization
• Matrix Analysis
• Bipartite completely positive matrices
• On the combinatorial and algebraic complexity of quantifier elimination
• Non-Negative Matrix Factorization Revisited: Uniqueness and Algorithm for Symmetric Decomposition
• A Test of the Markovian Model of DNA Evolution
• Linear-Time Complete Positivity Detection and Decomposition of Sparse Matrices
• Computing a nonnegative matrix factorization -- provably
• An Almost Optimal Algorithm for Computing Nonnegative Rank

This page was built for publication: A polynomial-time algorithm for computing low CP-rank decompositions