Let B_i be deterministic symmetric m\times m matrices, and \xi_i be independent random scalars with zero mean and “of order of one” (e.g., \xi_i are Gaussian with zero mean and unit standard deviation). We are interested in conditions for the “typical norm” of the random matrix S_N = \xi_1B_1+…+\xi_NB_N to be of order of 1. An evident necessary condition is E\{S_N^2\} \preceq O(1)I, which, essentially, translates to B_1^2+…+B_N^2\preceq 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, show 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. 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=\max\{F(X_1,…,X_k): X_jX_j^T=I\right\}, where F is quadratic in X=(X_1,…,X_k). We show that when F is convex in every one ofm 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\leq \Opt(SDP)\leq O(1) [m^{1/3}+\ln k]\Opt.
Citation
Research Report, Minerva Optimization Center, Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology, Technion City, Haifa, Israel, December 2004