- A Unified Theorem on SDP Rank Reduction Anthony Man-Cho So (manchosocs.stanford.edu) Yinyu Ye (yinyu-yestanford.edu) Jiawei Zhang (jzhangstern.nyu.edu) Abstract: We consider the problem of finding a low-rank approximate solution to a system of linear equations in symmetric, positive semidefinite matrices. Specifically, let $A_1,\ldots,A_m \in \R^{n\times n}$ be symmetric, positive semidefinite matrices, and let $b_1,\ldots,b_m \ge 0$. We show that if there exists a symmetric, positive semidefinite matrix $X$ to the system $A_i \bullet X = b_i$ (where $i = 1,\ldots,m$), then for any fixed $d = 1,\ldots,O(\log m)$, there exists an $X_0 \succeq 0$ of rank at most $d$ such that $\beta \cdot b_i \le A_i \bullet X_0 \le \alpha \cdot b_i$ for all $i = 1,\ldots,m$, where $\alpha = 1+O(\log m/d)$; $\beta = \Omega(m^{-2/d})$ for $d = O(\log m / \log\log m)$, and $\beta = \Omega((\log m)^{-3\log m / (d\log\log m)})$. Moreover, such an $X_0$ can be found in randomized polynomial time. This complements a result of Barvinok and provides a unified treatment of and generalizes several results in the literature. Keywords: Semidefinite Programming, Rank Reduction Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Category 2: Combinatorial Optimization (Approximation Algorithms ) Citation: Download: [PDF]Entry Submitted: 11/19/2006Entry Accepted: 11/19/2006Entry Last Modified: 11/21/2006Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.