Lifts of convex sets and cone factorizations

Abstract

In this paper we address the basic geometric question of when a given convex set is the image under a linear map of an affine slice of a given closed convex cone. Such a representation or 'lift' of the convex set is especially useful if the cone admits an efficient algorithm for linear optimization over its affine slices. We show that the existence of a lift of a convex set to a cone is equivalent to the existence of a factorization of an operator associated to the set and its polar via elements in the cone and its dual. This generalizes a theorem of Yannakakis that established a connection between polyhedral lifts of a polytope and nonnegative factorizations of its slack matrix. Symmetric lifts of convex sets can also be characterized similarly. When the cones live in a family, our results lead to the definition of the rank of a convex set with respect to this family. We present results about this rank in the context of cones of positive semidefinite matrices. Our methods provide new tools for understanding cone lifts of convex sets.

20 pages, 2 figures

Cited by in corpus (42)

• Purifications of multipartite states: limitations and constructive methods
• Matrix product operators and states: NP-hardness and undecidability
• Positive semidefinite rank
• Semidefinite descriptions of the convex hull of rotation matrices
• Self-consistent tomography of the state-measurement Gram matrix
• Minimum Dimension of a Hilbert Space Needed to Generate a Quantum Correlation
• Heuristics for Exact Nonnegative Matrix Factorization
• Sparse sum-of-squares certificates on finite abelian groups
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
• Quantum learning of classical stochastic processes: The Completely-Positive Realization Problem
• Matrices with high completely positive semidefinite rank
• Lower bounds on nonnegative rank via nonnegative nuclear norms
• Bounding the Distance to Unsafe Sets with Convex Optimization
• Device-independent dimension tests in the prepare-and-measure scenario
• Algorithms for Positive Semidefinite Factorization
• Polynomial-sized Semidefinite Representations of Derivative Relaxations of Spectrahedral Cones
• Error bounds, facial residual functions and applications to the exponential cone
• Communication tasks in operational theories
• Lifting for Simplicity: Concise Descriptions of Convex Sets
• Amenable cones are particularly nice
• Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices
• Fitting Tractable Convex Sets to Support Function Evaluations
• Equivariant semidefinite lifts and sum-of-squares hierarchies
• Completely positive semidefinite rank
• Tensor decompositions on simplicial complexes with invariance
• On the Linear Extension Complexity of Regular n-gons
• Learning optimal quantum models is NP-hard
• On Approximations of the PSD Cone by a Polynomial Number of Smaller-sized PSD Cones
• Separability for mixed states with operator Schmidt rank two
• Positive Semidefinite Matrix Factorization: A Connection with Phase Retrieval and Affine Rank Minimization
• Two results on the size of spectrahedral descriptions
• Assessing the Quality of a Set of Basis Functions for Inverse Optimal Control via Projection onto Global Minimizers
• On polyhedral approximations of the positive semidefinite cone
• Approximate cone factorizations and lifts of polytopes
• Equivariant semidefinite lifts of regular polygons
• A Matrix Positivstellensatz with lifting polynomials
• Polynomial decompositions with invariance and positivity inspired by tensors
• Self-dual polyhedral cones and their slack matrices
• Approximate tensor decompositions: disappearance of many separations
• Border Ranks of Positive and Invariant Tensor Decompositions: Applications to Correlations
• Spectral Polyhedra
• On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs