- 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/2004Entry Accepted: 12/09/2004Entry Last Modified: 12/09/2004Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.