Some upper and lower bounds on PSD-rank

Lee, T; Wei, Z; de Wolf, R

Some upper and lower bounds on PSD-rank

Lee, T

Wei, Z de Wolf, R

Permalink

Publisher:: Springer
Publication Type:: Journal Article
Citation:: Mathematical Programming, 2017, 162, (1-2), pp. 495-521
Issue Date:: 2017-03-01

Closed Access

	Filename	Description	Size
	Some_upper_and_lower_bounds_on.pdf		565.93 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Lee, T https://orcid.org/0000-0001-6912-2338
dc.contributor.author	Wei, Z
dc.contributor.author	de Wolf, R
dc.date.accessioned	2022-08-17T03:05:18Z
dc.date.available	2022-08-17T03:05:18Z
dc.date.issued	2017-03-01
dc.identifier.citation	Mathematical Programming, 2017, 162, (1-2), pp. 495-521
dc.identifier.issn	0025-5610
dc.identifier.issn	1436-4646
dc.identifier.uri	http://hdl.handle.net/10453/160414
dc.description.abstract	Positive semidefinite rank (PSD-rank) is a relatively new complexity measure on matrices, with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix M as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.
dc.language	en
dc.publisher	Springer
dc.relation.ispartof	Mathematical Programming
dc.relation.isbasedon	10.1007/s10107-016-1052-0
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0102 Applied Mathematics, 0103 Numerical and Computational Mathematics, 0802 Computation Theory and Mathematics
dc.subject.classification	Operations Research
dc.title	Some upper and lower bounds on PSD-rank
dc.type	Journal Article
utslib.citation.volume	162
utslib.for	0102 Applied Mathematics
utslib.for	0103 Numerical and Computational Mathematics
utslib.for	0802 Computation Theory and Mathematics
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	closed_access	*
pubs.consider-herdc	false
dc.date.updated	2022-08-17T03:05:16Z
pubs.issue	1-2
pubs.publication-status	Published
pubs.volume	162
utslib.citation.issue	1-2

Abstract:

Positive semidefinite rank (PSD-rank) is a relatively new complexity measure on matrices, with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix M as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/160414