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 complexity polynomial-time algorithm completely positive matrix CP-decomposition CP-rank

Mathematics Subject Classification ID

Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).

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