Concentration inequalities for random matrix products

DOI10.1016/J.LAA.2020.01.040zbMATH Open1436.65047arXiv1907.05833OpenAlexW3006252341MaRDI QIDQ2310409FDOQ2310409

Authors: Amelia Henriksen, Rachel Ward 

Publication date: 6 April 2020

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: Suppose ${X_k}_{kinmathbbZ}$ is a sequence of bounded independent random matrices with common dimension $dimesd$ and common expectation $mathbbE[X_k]=X$. Under these general assumptions, the normalized random matrix product ${\displaystyle }$Z_n = (I + frac{1}{n}X_n)(I + frac{1}{n}X_{n-1}) cdots (I + frac{1}{n}X_1)${\displaystyle }$ converges to $Z_{n}ightarrow{e}^X$ as $nightarrowinfty$. Normalized random matrix products of this form arise naturally in stochastic iterative algorithms, such as Oja's algorithm for streaming Principal Component Analysis. Here, we derive nonasymptotic concentration inequalities for such random matrix products. In particular, we show that the spectral norm error satisfies $|Z_n-e^X|=O((log(n){)}^{2}log(d/delta)/sqrtn)$ with probability exceeding $1-delta$. This rate is sharp in $n$, $d$, and $delta$, up to possibly the $log(n)$ and $log(d)$ factors. The proof relies on two key points of theory: the Matrix Bernstein inequality concerning the concentration of sums of random matrices, and Baranyai's theorem from combinatorial mathematics. Concentration bounds for general classes of random matrix products are hard to come by in the literature, and we hope that our result will inspire further work in this direction.

Full work available at URL: https://arxiv.org/abs/1907.05833

Recommendations

• Matrix concentration for products
• Concentration of norms and eigenvalues of random matrices
• Matrix concentration inequalities via the method of exchangeable pairs
• An introduction to matrix concentration inequalities
• Second-order matrix concentration inequalities

zbMATH Keywords

large deviationsnoncommutativitystochastic gradient descentrandom matrix product

Mathematics Subject Classification ID

Probabilistic methods, stochastic differential equations (65C99) Random matrices (algebraic aspects) (15B52) Numerical computation of matrix norms, conditioning, scaling (65F35)

Cites Work

• An introduction to matrix concentration inequalities
• User-friendly tail bounds for sums of random matrices
• Title not available (Why is that?)
• Some asymptotic properties of random walks on free groups
• Title not available (Why is that?)
• Random walks on reductive groups
• A simplified neuron model as a principal component analyzer
• Strong converse for identification via quantum channels
• Method of stochastic approximation in the determination of the largest eigenvalue of the mathematical expectation of random matrices
• Central Limit Theorem for Products of Random Matrices
• Limit laws for random matrix products

Cited In (8)

• Matrix concentration for products
• Free transport-entropy inequalities for non-convex potentials and application to concentration for random matrices
• Tightness of products of iid random matrices
• On the concentration of random multilinear forms and the universality of random block matrices
• Nonlinear matrix concentration via semigroup methods
• Non-asymptotic results for singular values of Gaussian matrix products
• Concentration of permanent estimators for certain large matrices.
• On concentration of high-dimensional matrices with randomly signed entries

This page was built for publication: Concentration inequalities for random matrix products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2310409)