Concentration inequalities for random matrix products

DOI10.1016/J.LAA.2020.01.040MaRDI QIDQ2310409zbMATH OpenOpenAlexFDO

Authors Amelia Henriksen, Rachel Ward

Publication date 6 April 2020

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

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

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)

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.

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

Cites work

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

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)