Matrix concentration bound

Question

Suppose we have $N$ constant matrices $A_i \in R^{m\times m}, 1\leq i \leq N$. Consider $N$ random rotation-matrices $R_i \in SO(m), 1\leq i \leq N$. Is it possible to obtain a concentration bound on $$ \left\|\sum\limits_{i=1}^{N}R_i A_i\right\| $$ based on $$ \left\|\sum\limits_{i=1}^{N}A_i^{T}A_i\right\| . $$ Note that we do not assume the spectral norm of each individual $A_i$ is bounded by a smaller constant.

Answer 1

Such a bound follows from Corollary 6.1 here: http://arxiv.org/pdf/1408.3470.pdf (a version of the matrix bounded differences inequality), assuming your matrices $R_i$ are independent. Corollary 13.2 in the same paper gives bounds for the case that that are dependent, in terms of the Dobrushin interdependence matrix.

Edit: I was thinking of applying that corollary to $H=\sum_{i=1}^N X_i$, with $X_i = \begin{pmatrix} 0 & R_iA_i \\ A_i^*R_i^* & 0 \end{pmatrix}$ (note that $H$ has the same spectral norm as $M=\sum_{i=1}^N R_iA_i$). However, we can't bound $X_i^2 = \begin{pmatrix} R_iA_iA_i^*R_i^* \\ 0 & A_i^*A_i \end{pmatrix}$ deterministically in terms of the $A_i$. One can show boundedness in expectation: $$\left\|\sum_{i=1}^N\mathbb{E} X_i^2\right\| \le \left\|\sum_{i=1}^N A_i^*A_i\right\|=: \sigma^2 $$ which allows us to apply the matrix Bernstein inequality (see Theorem 1.4 here: http://arxiv.org/pdf/1004.4389.pdf), but this will still require a uniform bound $\max_{i\le N} \|A_i\|\le R$. It gives $$ \mathbb{P}\left( \lambda_{\max}\left(H\right) \ge t\right) \le m \exp\left( \frac{-t^2}{2\sigma^2 + \frac23 Rt}\right).$$ This still offers an improvement over what you get from the assumption $\max_{i\le N} \|A_i\|\le R$ alone when $\sigma^2$ is of lower order than $NR^2$. In general it seems you will need some kind of uniform control on the individual summands to have exponential tail bounds (just as in the scalar case).