# Dimensionality reduction of SDPs through sketching

arXiv: https://arxiv.org/abs/1707.09863 · HTML: https://mlsanity.com/paper/1707.09863/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2017.

## Built on by (most cited first, 2 of 2)

- [Sketch-and-Lift: Scalable Subsampled Semidefinite Program for K-means Clustering](https://mlsanity.com/paper/2201.08226/) (2022)
- [Community Detection with a Subsampled Semidefinite Program](https://mlsanity.com/paper/2102.01419/) (2021)

## Abstract (arXiv)

We show how to sketch semidefinite programs (SDPs) using positive maps in order to reduce their dimension. More precisely, we use JohnsonhypLindenstrauss 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.