Dimensionality reduction of SDPs through sketching
arXiv:1707.09863 · doi:10.1016/j.laa.2018.11.012
Abstract
We show how to sketch semidefinite programs (SDPs) using positive maps in order to reduce their dimension. More precisely, we use Johnson\hyp{}Lindenstrauss transforms to produce a smaller SDP whose solution preserves feasibility or approximates the value of the original problem with high probability. These techniques allow to improve both complexity and storage space requirements. They apply to problems in which the Schatten 1-norm of the matrices specifying the SDP and also of a solution to the problem is constant in the problem size. Furthermore, we provide some results which clarify the limitations of positive, linear sketches in this setting.
15 pages. Significantly shortened and presentation streamlined
References in corpus (6)
- Sketching as a Tool for Numerical Linear Algebra
- Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
- Semidefinite programs for completely bounded norms
- Compressibility of positive semidefinite factorizations and quantum models
- Efficient First-Order Methods for Linear Programming and Semidefinite Programming
- Using the Johnson-Lindenstrauss lemma in linear and integer programming