Dimensionality reduction of SDPs through sketching

DOI10.1016/j.laa.2018.11.012zbMath1405.90097arXiv1707.09863OpenAlexW2742057422WikidataQ128959464 ScholiaQ128959464MaRDI QIDQ1713333

Daniel Stilck França, Andreas Bluhm

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

sketchingsemidefinite programmingdimensionality reductionJohnson-Lindenstrauss transforms

Mathematics Subject Classification ID

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

Related Items

Community detection with a subsampled semidefinite program, Convexification with Bounded Gap for Randomly Projected Quadratic Optimization, An efficient superpostional quantum Johnson-Lindenstrauss lemma via unitary \(t\)-designs, Random projections of linear and semidefinite problems with linear inequalities, Random projections for conic programs

Cites Work

• Semidefinite programming for discrete optimization and matrix completion problems
• Geometric algorithms and combinatorial optimization
• Aspects of semidefinite programming. Interior point algorithms and selected applications
• Computational Advertising: Techniques for Targeting Relevant Ads
• Compressibility of Positive Semidefinite Factorizations and Quantum Models
• Limitations on Quantum Dimensionality Reduction
• Sparser Johnson-Lindenstrauss Transforms
• Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring
• Linear Matrix Inequalities in System and Control Theory
• Unnamed Item
• Unnamed Item
• Unnamed Item