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.

  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.