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

Khaled Elbassioni; Trung Thanh Nguyen

doi:10.1016/j.ipl.2016.09.004

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

Khaled Elbassioni, Trung Thanh Nguyen

Electrical Engineering

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

This paper investigates computing completely positive (cp) decompositions of positive semi-definite (PSD) matrices, a problem which arises in many applications. We propose the first polynomial-time algorithm for checking if a given PSD matrix has cp-rank of at most r, when r is a given constant. In addition, we present a polynomial-time algorithm for computing a (rational) cp-decomposition of such a matrix if it exists, within any desired accuracy.

Original language	British English
Pages (from-to)	10-14
Number of pages	5
Journal	Information Processing Letters
Volume	118
DOIs	https://doi.org/10.1016/j.ipl.2016.09.004
State	Published - 1 Feb 2017

Keywords

Completely positive matrix
Computational complexity
CP-decomposition
CP-rank
Polynomial-time algorithm

Access to Document

10.1016/j.ipl.2016.09.004

Cite this

@article{582dbb72e3fa48399a15bbad35960876,

title = "A polynomial-time algorithm for computing low CP-rank decompositions",

abstract = "This paper investigates computing completely positive (cp) decompositions of positive semi-definite (PSD) matrices, a problem which arises in many applications. We propose the first polynomial-time algorithm for checking if a given PSD matrix has cp-rank of at most r, when r is a given constant. In addition, we present a polynomial-time algorithm for computing a (rational) cp-decomposition of such a matrix if it exists, within any desired accuracy.",

keywords = "Completely positive matrix, Computational complexity, CP-decomposition, CP-rank, Polynomial-time algorithm",

author = "Khaled Elbassioni and Nguyen, {Trung Thanh}",

note = "Funding Information: The authors thank the anonymous referees for their valuable comments and suggestions that substantially improved the paper. This work was supported by the MI-MIT Flagship Project 13CAMA1 . Publisher Copyright: {\textcopyright} 2016 Elsevier B.V.",

year = "2017",

month = feb,

day = "1",

doi = "10.1016/j.ipl.2016.09.004",

language = "British English",

volume = "118",

pages = "10--14",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

}

TY - JOUR

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

AU - Elbassioni, Khaled

AU - Nguyen, Trung Thanh

N1 - Funding Information: The authors thank the anonymous referees for their valuable comments and suggestions that substantially improved the paper. This work was supported by the MI-MIT Flagship Project 13CAMA1 . Publisher Copyright: © 2016 Elsevier B.V.

PY - 2017/2/1

Y1 - 2017/2/1

N2 - This paper investigates computing completely positive (cp) decompositions of positive semi-definite (PSD) matrices, a problem which arises in many applications. We propose the first polynomial-time algorithm for checking if a given PSD matrix has cp-rank of at most r, when r is a given constant. In addition, we present a polynomial-time algorithm for computing a (rational) cp-decomposition of such a matrix if it exists, within any desired accuracy.

AB - This paper investigates computing completely positive (cp) decompositions of positive semi-definite (PSD) matrices, a problem which arises in many applications. We propose the first polynomial-time algorithm for checking if a given PSD matrix has cp-rank of at most r, when r is a given constant. In addition, we present a polynomial-time algorithm for computing a (rational) cp-decomposition of such a matrix if it exists, within any desired accuracy.

KW - Completely positive matrix

KW - Computational complexity

KW - CP-decomposition

KW - CP-rank

KW - Polynomial-time algorithm

UR - http://www.scopus.com/inward/record.url?scp=84988421390&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2016.09.004

DO - 10.1016/j.ipl.2016.09.004

M3 - Article

AN - SCOPUS:84988421390

SN - 0020-0190

VL - 118

SP - 10

EP - 14

JO - Information Processing Letters

JF - Information Processing Letters

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this