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

DOI10.1016/J.IPL.2016.09.004zbMATH Open1392.68200OpenAlexW2518945775MaRDI QIDQ344517FDOQ344517

Authors: Trung Thanh Nguyen, Khaled 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

Recommendations

• Decomposition of homogeneous polynomials with low rank
• New lower bounds and asymptotics for the cp-rank
• A note on the computation of the CP-rank
• Some structural properties of low-rank matrices related to computational complexity
• A simplex algorithm for rational cp-factorization
• A polynomial time algorithm for computing all minimal decompositions of a polynomial
• Computing lower rank approximations of matrix polynomials
• An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
• A Practical Randomized CP Tensor Decomposition
• Computation of the nearest non-prime polynomial matrix: structured low-rank approximation approach

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)

Cites Work

• SymNMF: nonnegative low-rank approximation of a similarity matrix for graph clustering
• Matrix Analysis
• On the complexity of nonnegative matrix factorization
• Computing a nonnegative matrix factorization -- provably
• On the copositive representation of binary and continuous nonconvex quadratic programs
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Nonnegative factorization of positive semidefinite nonnegative matrices
• Title not available (Why is that?)
• On the computational complexity of membership problems for the completely positive cone and its dual
• On reduced rank nonnegative matrix factorization for symmetric nonnegative matrices
• An almost optimal algorithm for computing nonnegative rank
• On nonnegative factorization of matrices
• The structure of completely positive matrices according to their CP-rank and CP-plus-rank
• Solving systems of polynomial inequalities in subexponential time
• On the combinatorial and algebraic complexity of quantifier elimination
• Non-Negative Matrix Factorization Revisited: Uniqueness and Algorithm for Symmetric Decomposition
• On the computation of \(C^*\) certificates
• A note on upper bounds on the cp-rank
• 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
• Title not available (Why is that?)
• Bipartite completely positive matrices
• A Test of the Markovian Model of DNA Evolution
• Linear-time complete positivity detection and decomposition of sparse matrices
• Title not available (Why is that?)
• Computing symmetric nonnegative rank factorizations
• A note on the computation of the CP-rank
• On the parameterization of the CreditRisk\(^+\) model for estimating credit portfolio risk

Cited In (7)

• A simplex algorithm for rational cp-factorization
• Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions
• Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
• Computing approximate PSD factorizations
• Binary component decomposition. I: The positive-semidefinite case
• A note on the computation of the CP-rank
• Linear-time complete positivity detection and decomposition of sparse matrices

Uses Software

• SymNMF

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344517)