Dimensionality reduction of SDPs through sketching

TY - JOUR

T1 - Dimensionality reduction of SDPs through sketching

AU - Bluhm, Andreas

AU - Stilck França, Daniel

PY - 2019/2/15

Y1 - 2019/2/15

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

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

KW - Dimensionality reduction

KW - Johnson–Lindenstrauss transforms

KW - Semidefinite programming

KW - Sketching

UR - http://www.mendeley.com/research/dimensionality-reduction-sdps-through-sketching

U2 - 10.1016/j.laa.2018.11.012

DO - 10.1016/j.laa.2018.11.012

M3 - Journal article

SN - 0024-3795

VL - 563

SP - 461

EP - 475

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -