A Unified Theorem on SDP Rank Reduction

References

• Alon N. Problems and results in extremal combinatorics I. Discrete Math. (2003) 273(6):31–53Crossref, Google Scholar
• Barvinok A. A course in convexity. Graduate Studies in Mathematics (2002) 54(American Mathematical Society, Providence, RI) Google Scholar
• Barvinok A. I. Problems of distance geometry and convex properties of quadratic maps. Discrete Computational Geometry (1995) 13(2):189–202Crossref, Google Scholar
• Dasgupta S., Gupta A. An elementary proof of the Johnson–Lindenstrauss lemma. (1999) . Technical Report TR-99-06, International Computer Science Institute, Berkeley, CAGoogle Scholar
• Gnedenko B. D. The best constant in an inequality of Khinchin type for quadratic forms. Russian Math. Surveys (2000) 55(2):340–341Crossref, Google Scholar
• He S., Luo Z.-Q., Nie J., Zhang S. Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization. SIAM J. Optimization (2008) 19(2):503–523Crossref, Google Scholar
• Johnson W. B., Lindenstrauss J. Extensions of Lipschitz mapping into Hilbert space. Contemporary Math. (1984) 26:189–206Crossref, Google Scholar
• Laurent B., Massart P. Adaptive estimation of a quadratic functional by model selection. Ann. Statist. (2000) 28(5):1302–1338Crossref, Google Scholar
• Luo Z.-Q., Sidiropoulos N. D., Tseng P., Zhang S. Approximation bounds for quadratic optimization with homogeneous quadratic constraints. SIAM J. Optim. (2007) 18(1):1–28Crossref, Google Scholar
• Matoušek J. Bi-Lipschitz embeddings into low-dimensional Euclidean spaces. Commentationes Mathematicae Universitatis Carolinae (1990) 31(3):589–600Google Scholar
• Matoušek J.Lectures on Discrete Geometry (2002) (Springer-Verlag, New York) Crossref, Google Scholar
• Nemirovski A., Roos C., Terlaky T. On maximization of quadratic form over intersection of ellipsoids with common center. Math. Programming, Series A (1999) 86:465–473Crossref, Google Scholar
• Pataki G. On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. (1998) 23(2):339–358Link, Google Scholar
• So A. M.-C., Ye Y. A semidefinite programming approach to tensegrity theory and realizability of graphs. Proc. 17th Annual ACM-SIAM Sympos. Discrete Algorithms (2006) Miami:766–775Crossref, Google Scholar
• Weinberger K. Q., Saul L. K. An introduction to nonlinear dimensionality reduction by maximum variance unfolding. Proc. 21st National Conf. Artificial Intelligence (2006) Boston:1683–1686Google Scholar