Dimensionality reduction of SDPs through sketching

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Dimensionality reduction of SDPs through sketching. / Bluhm, Andreas; Stilck França, Daniel.

In: Linear Algebra and Its Applications, Vol. 563, 15.02.2019, p. 461-475.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Bluhm, A & Stilck França, D 2019, 'Dimensionality reduction of SDPs through sketching', Linear Algebra and Its Applications, vol. 563, pp. 461-475. https://doi.org/10.1016/j.laa.2018.11.012

APA

Bluhm, A., & Stilck França, D. (2019). Dimensionality reduction of SDPs through sketching. Linear Algebra and Its Applications, 563, 461-475. https://doi.org/10.1016/j.laa.2018.11.012

Vancouver

Bluhm A, Stilck França D. Dimensionality reduction of SDPs through sketching. Linear Algebra and Its Applications. 2019 Feb 15;563:461-475. https://doi.org/10.1016/j.laa.2018.11.012

Author

Bluhm, Andreas ; Stilck França, Daniel. / Dimensionality reduction of SDPs through sketching. In: Linear Algebra and Its Applications. 2019 ; Vol. 563. pp. 461-475.

Bibtex

@article{689b244896fe4ad4bc52dc866f02a375,
title = "Dimensionality reduction of SDPs through sketching",
abstract = "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.",
keywords = "Dimensionality reduction, Johnson–Lindenstrauss transforms, Semidefinite programming, Sketching",
author = "Andreas Bluhm and {Stilck Fran{\c c}a}, Daniel",
year = "2019",
month = feb,
day = "15",
doi = "10.1016/j.laa.2018.11.012",
language = "English",
volume = "563",
pages = "461--475",
journal = "Linear Algebra and Its Applications",
issn = "0024-3795",
publisher = "Elsevier",

}

RIS

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

VL - 563

SP - 461

EP - 475

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

ER -

ID: 231872633