Dimensionality reduction of SDPs through sketching

DOI10.1016/J.LAA.2018.11.012MaRDI QIDQ1713333zbMATH OpenOpenAlexWikidataFDO

Authors Andreas Bluhm, Daniel Stilck França

Publication date 24 January 2019

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.09863

zbMATH Keywords

dimensionality reductionsketchingsemidefinite programmingJohnson-Lindenstrauss transforms

Mathematics Subject Classification ID

Randomized algorithms (68W20) Semidefinite programming (90C22) Positive matrices and their generalizations; cones of matrices (15B48) Linear inequalities of matrices (15A39)

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

Recommendations

• Algorithms and Data Structures
• Randomized sketch descent methods for non-separable linearly constrained optimization
• Randomized Sketches of Convex Programs With Sharp Guarantees
• scientific article; zbMATH DE number 2119731
• Explicit dimension reduction and its applications
• Publication:4727306
• Dimensionality reduction: beyond the Johnson-Lindenstrauss bound
• scientific article; zbMATH DE number 1130207
• Approximate dynamic programming. Solving the curses of dimensionality
• A non-Euclidean gradient descent method with sketching for unconstrained matrix minimization

Cites work

• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring
• Aspects of semidefinite programming. Interior point algorithms and selected applications
• Compressibility of Positive Semidefinite Factorizations and Quantum Models
• Convex optimization: algorithms and complexity
• Geometric algorithms and combinatorial optimization
• Limitations on quantum dimensionality reduction
• Linear Matrix Inequalities in System and Control Theory
• Semidefinite programming for discrete optimization and matrix completion problems
• Semidefinite programs for completely bounded norms
• Sketching as a tool for numerical linear algebra
• Sparser Johnson-Lindenstrauss transforms

Cited in

(9)

• Random projections for conic programs
• Community detection with a subsampled semidefinite program
• Random projections of linear and semidefinite problems with linear inequalities
• An efficient superpostional quantum Johnson-Lindenstrauss lemma via unitary \(t\)-designs
• Random projections for linear programming: an improved retrieval phase
• Dimension reduction for semidefinite programs via Jordan algebras
• Slide reduction, revisited -- filling the gaps in SVP approximation
• Dimension reduction and its application to model-based exploration in continuous spaces
• Convexification with bounded gap for randomly projected quadratic optimization

This page was built for publication: Dimensionality reduction of SDPs through sketching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1713333)