On Concentration Inequalities for Random Matrix Products

Authors Tarun Kathuria, Satyaki Mukherjee, Nikhil Srivastava

Publication date 13 March 2020

Abstract: Consider

n

complex random matrices

X_{1}, l d o t s, X_{n}

of size

d i m e s d

sampled i.i.d. from a distribution with mean

E [X] = m u

. While the concentration of averages of these matrices is well-studied, the concentration of other functions of such matrices is less clear. One function which arises in the context of stochastic iterative algorithms, like Oja's algorithm for Principal Component Analysis, is the normalized matrix product defined as

p r o d l i m i t s_{i = 1}^{n} l e f t (I + f r a c X_{i} n i g h t) .

Concentration properties of this normalized matrix product were recently studied by cite{HW19}. However, their result is suboptimal in terms of the dependence on the dimension of the matrices as well as the number of samples. In this paper, we present a stronger concentration result for such matrix products which is optimal in

n

and

d

up to constant factors. Our proof is based on considering a matrix Doob martingale, controlling the quadratic variation of that martingale, and applying the Matrix Freedman inequality of Tropp cite{TroppIntro15}.

This page was built for publication: On 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 Q6336706)