Sums of random symmetric matrices and quadratic optimization under orthogonality constraints
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   Omega(1/6)(m)}   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.
orthogonality constraints semidefinite relaxations large deviations random perturbations of linear matrix inequalities procrustes problem