Optimization Online


A Unified Theorem on SDP Rank Reduction

Anthony Man-Cho So (manchoso***at***cs.stanford.edu)
Yinyu Ye (yinyu-ye***at***stanford.edu)
Jiawei Zhang (jzhang***at***stern.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 )


Download: [PDF]

Entry Submitted: 11/19/2006
Entry Accepted: 11/19/2006
Entry Last Modified: 11/21/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society