Faster and simpler width-independent parallel algorithms for positive semidefinite programming

This paper studies the problem of finding a (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 nonnegative. At FOCS'11, Jain and Yao gave an NC algorithm that requires O(1/ε ¹³ log ¹³ mlog n) iterations on input n constraint matrices of dimension m-by-m, where each iteration performs at least Δ(m ^ω) work since it involves computing the spectral decomposition. We present a simpler NC parallel algorithm that on input with n constraint matrices, requires O(1/ε ⁴ log ⁴ n log(1/ε )) 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. Our algorithm can be viewed as a generalization of Young's algorithm and analysis techniques for positive linear programs (Young, FOCS'01 ) to the semidefinite programming setting.