Matrix Infinitely Divisible Series: Tail Inequalities and Their Applications

Abstract

In this paper, we study tail inequalities of the largest eigenvalue of a matrix infinitely divisible (i.d.) series, which is a finite sum of fixed matrices weighted by i.d. random variables. We obtain several types of tail inequalities, including Bennett-type and Bernstein-type inequalities. This allows us to further bound the expectation of the spectral norm of a matrix i.d. series. Moreover, by developing a new lower-bound function for $Q(s)=(s+1)\log (s+1)-s$ that appears in the Bennett-type inequality, we derive a tighter tail inequality of the largest eigenvalue of the matrix i.d. series than the Bernstein-type inequality when the matrix dimension is high. The resulting lower-bound function is of independent interest and can improve any Bennett-type concentration inequality that involves the function $Q(s)$. The class of i.d. probability distributions is large and includes Gaussian and Poisson distributions, among many others. Therefore, our results encompass the existing work \cite{tropp2012user} on matrix Gaussian series as a special case. Lastly, we show that the tail inequalities of a matrix i.d. series have applications in several optimization problems including the chance constrained optimization problem and the quadratic optimization problem with orthogonality constraints. In addition, we also use the resulting tail bounds to show that random matrices constructed from i.d. random variables satisfy the restricted isometry property (RIP) when it acts as a measurement matrix in compressed sensing.

arXiv commentFinal Version

References in corpus (15)

• User-friendly tail bounds for sums of random matrices
• Matrix concentration inequalities via the method of exchangeable pairs
• Generalized Gamma Convolutions, Dirichlet means, Thorin measures, with explicit examples
• Analysis of Regularized LS Reconstruction and Random Matrix Ensembles in Compressed Sensing
• Robust Estimates of Covariance Matrices in the Large Dimensional Regime
• Concentration of norms and eigenvalues of random matrices
• An introduction to Lévy processes with applications in finance
• On the probability that all eigenvalues of Gaussian, Wishart, and double Wishart random matrices lie within an interval
• Recycling Randomness with Structure for Sublinear time Kernel Expansions
• Improved Bound for the Nystrom's Method and its Application to Kernel Classification
• Exponential Decay of Matrix $\Phi$-Entropies on Markov Semigroups with Applications to Dynamical Evolutions of Quantum Ensembles
• Deriving Matrix Concentration Inequalities from Kernel Couplings
• Bennett-type Generalization Bounds: Large-deviation Case and Faster Rate of Convergence
• From Random Matrix Theory to Coding Theory: Volume of a Metric Ball in Unitary Group
• Characteristic Kernels and Infinitely Divisible Distributions