Approximate completely positive semidefinite factorizations and their ranks

In this paper we show the existence of approximate completely positive semidefinite (cpsd) factorizations with a cpsd-rank bounded above (almost) independently from the cpsd-rank of the initial matrix. This is particularly relevant since the cpsd-rank of a matrix cannot, in general, be upper bounded...

Full description

Saved in:
Bibliographic Details
Published in:Linear algebra and its applications 2023-11, Vol.677, p.323-336
Main Authors: Abbasi, Paria, Klingler, Andreas, Netzer, Tim
Format: Article
Language:English
Subjects:
Approximate rank
Carathéodory
Completely positive
Completely positive semidefinite
Johnson-Lindenstrauss Lemma
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we show the existence of approximate completely positive semidefinite (cpsd) factorizations with a cpsd-rank bounded above (almost) independently from the cpsd-rank of the initial matrix. This is particularly relevant since the cpsd-rank of a matrix cannot, in general, be upper bounded by a function only depending on its size. For this purpose, we make use of the Approximate Carathéodory Theorem in order to construct an approximate matrix with a low-rank Gram representation. We then employ the Johnson-Lindenstrauss Lemma to improve to a logarithmic dependence of the cpsd-rank on the size.
ISSN:0024-3795
1873-1856
DOI:10.1016/j.laa.2023.08.005