Title: A Unified Theorem on SDP Rank Reduction
Speaker:  Anthony Man-Cho So
CUHK

Date: Friday, October 12, 2007
Time 11-12PM
Venue: Room  3464, HKUST

 
Abstract:
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.
 
Joint Work with Yinyu Ye and Jiawei Zhang