期刊
MATHEMATICS OF OPERATIONS RESEARCH
卷 33, 期 4, 页码 910-920出版社
INFORMS
DOI: 10.1287/moor.1080.0326
关键词
semidefinite programming; low-rank matrices; randomized algorithm; metric embedding; quadratic optimization
资金
- National Science Foundation (NSF) [DMS-0604513]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据