Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming

2012/01/24 by Richard Peng, Peng, Richard, Kanat Tangwongsan +3 · 4 citations
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Machine Learning and Algorithms #Parallel #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1201.5135

openalex publication_date 2012/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper studies the problem of finding an (1+ε)-approximate solution to positive semidefinite programs. These are semidefinite programs in which all matrices in the constraints and objective are positive semidefinite and all scalars are non-negative. We present a simpler \NC parallel algorithm that on input with n constraint matrices, requires O((1)/(ε³) log³ n) iterations, each of which involves only simple matrix operations and computing the trace of the product of a matrix exponential and a positive semidefinite matrix. Further, given a positive SDP in a factorized form, the total work of our algorithm is nearly-linear in the number of non-zero entries in the factorization.

Cited by

• An SDP-Based Algorithm for Linear-Sized Spectral Sparsification
• A Rank-1 Sketch for Matrix Multiplicative Weights
• A parallel approximation algorithm for mixed packing and covering semidefinite programs
• Optimal Robust Linear Regression in Nearly Linear Time

Related

• A Parallel Approximation Algorithm for Positive Semidefinite Programming
• Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
• Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver
• Fast implementation for semidefinite programs with positive matrix completion
• A parallel approximation algorithm for mixed packing and covering semidefinite programs