Sums of Random Symmetric Matrices and Applications

Arkadi Nemirovski (nemirovsisye.gatech.edu)

Abstract: 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.

Keywords: large deviations, random perturbations of linear matrix inequalities, orthogonality constraints, quality of semidefinite relaxations, Procrustes problem

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Citation: Research Report, Minerva Optimization Center, Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology, Technion City, Haifa, Israel, December 2004

Download: [PDF]

Entry Submitted: 12/09/2004
Entry Accepted: 12/09/2004
Entry Last Modified: 12/09/2004

Modify/Update this entry