Sums of random symmetric matrices and quadratic optimization under orthogonality constraints

• 成果类型: Article
• 署名作者: Nemirovski, Arkadi
• 署名单位: University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0033-0
• 发表日期: 2007
• 页码: 283-317

摘要

Let B-i be deterministic real symmetric m x m matrices, and xi (i) be independent random scalars with zero mean and of order of one (e.g., xi(i) similar to N(o,1)). We are interested to know under what conditions typical norm of the random matrix S-N = Sigma(N)(i=1) xi B-i(i) is of order of 1. An evident necessary condition is E{S-N(2)} less than or similar to O(1)I, which, essentially, translates to Sigma(N)(i=1) B-i(2) less than or similar to I; a natural conjecture is that the latter condition is sufficient as well. In the paper, we prove a relaxed version of this conjecture, specifically, that under the above condition the typical norm of S-N is <= O(1)m(1/6): Prob{parallel to S-N parallel to > Omega(1/6)(m)} <= O(1)Omega(2) > 0 We outline some applications of this result, primarily in investigating the quality of semidefinite relaxations of a general quadratic optimization problem with orthogonality constraints Opt = [GRAPHICS] {F(X-1,...,X-k) : XjXjT = I, j = 1,...,k}, where F is quadratic in X = (X-1,...,X (k) ). We show that when F is convex in every one of X (j) , a natural semidefinite relaxation of the problem is tight within a factor slowly growing with the size m of the matrices Xj: Opt <= Opt(SDP) <= O(1)[m1/3 + ln k]Opt.