Sums of random symmetric matrices and quadratic optimization under orthogonality constraints (Q868470)

Let \(B_i\) be deterministic real symmetric \(m \times m\) matrices, and \(\xi_i\) be independent random scalars with zero mean and ``of order of one '' (e.g., \(\xi_i \sim \mathcal{N}\)\,\((0,1)\)). An interesting question is to know under what conditions ``typical norm '' of the random matrix \(S_N = \sum_{i=1}^{N}\,\xi_i B_i\) is of order of \(1\). An evident necessary condition is \(\mathbf{E}\{S^2_N\} \preceq O(1)\,I\), which, essentially, translates to \(\sum_{i=1}^{N}\,B_i^2 \preceq I\); a natural conjecture is that the latter condition is sufficient as well. In the paper, a relaxed version of this conjecture is proven, specifically, that under the above condition the typical norm of \(S_N\) is \(\leq O(1)\,m^{1/6}\): Prob\(\{\|S_N\| > \Omega\,m^{1/6}\} \leq O(1)\) exp\(\{-O(1)\,\Omega^2\}\) for all \(\Omega >0\). Some applications of this result are outlined, primarily in investigating the quality of semidefinite relaxations of a general quadratic optimization problem with orthogonality constraints Opt \( = \max_{X_j \in \mathbb{R}^{m \times m}}\,\{F(X_1,\dots,X_k)\,:\,X_jX_j^T = I,\,j=1,\dots,k\}\), where \(F\) is quadratic in \(X = (X_1,\dots,X_k)\). It is shown 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 \(X_j\,\): Opt\((SDP) \leq O(1)\,[m^{1/3} + \ln{k}]\)\,Opt.