This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by So, A. M.-C. Articles by Zhang, J. Search for Related Content

A Unified Theorem on SDP Rank Reduction

Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong
Department of Management Science and Engineering, Stanford University, Stanford, California 94305, USA
Department of Information, Operations, and Management Sciences, Stern School of Business, New York University, New York, New York 10012, USA
manchoso{at}se.cuhk.edu.hk
yinyu-ye{at}stanford.edu
jzhang{at}stern.nyu.edu

We consider the problem of finding a low-rank approximate solution to a system of linear equations in symmetric, positive semidefinite matrices, where the approximation quality of a solution is measured by its maximum relative deviation, both above and below, from the prescribed quantities. We show that a simple randomized polynomial-time procedure produces a low-rank solution that has provably good approximation qualities. Our result provides a unified treatment of and generalizes several well-known results in the literature. In particular, it contains as special cases the Johnson–Lindenstrauss lemma on dimensionality reduction, results on low-distortion embeddings into low-dimensional Euclidean space, and approximation results on certain quadratic optimization problems.

Key Words: semidefinite programming; low-rank matrices; randomized algorithm; metric embedding; quadratic optimization
History: Received: January 28, 2007; revision received: March 12, 2008;