Optimization Online


Sums of Random Symmetric Matrices and Applications

Arkadi Nemirovski (nemirovs***at***isye.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society