  


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 (Semidefinite 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 Modify/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  