Suppose we have $N$ constant matrices $A_i \in R^{m\times m}, 1\leq i \leq N$. Consider $N$ random rotationmatrices $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.

1$\begingroup$ Peter, I think it'd be better if you write in the OP what precisely do you mean by a concentration bound. $\endgroup$ – Amir Sagiv Aug 2 '16 at 6:21

$\begingroup$ Do you know that $E[R_i A_i]=0$? $\endgroup$ – Aryeh Kontorovich Aug 2 '16 at 12:06

$\begingroup$ Yes, for random rotations, we have $E[R_i] = 0$. $\endgroup$ – Peter Huang Aug 4 '16 at 5:23
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).

$\begingroup$ I am looking for asymmetric matrices, can Corollary 6.1 be easily extended to asymmetric matrices? $\endgroup$ – Peter Huang Aug 4 '16 at 5:22

$\begingroup$ Corollary 6.1 actually doesn't apply the way I initially thought. I've edited my answer. See also Theorem 1.6 in Tropp's paper linked above for a tail bound stated in the rectangular case. $\endgroup$ – Nick Cook Aug 4 '16 at 21:25