Are there results/techniques pertaining to the analysis of squares of random matrices ?

More specifically, let $A$ be an $n\times n$ matrix such that each entry is $1$ or $-1$ independently and with equal probability. Now if we want to analyze for any $u,v \in \{-1,1\}^n$, we can make a case for concentration of the value of $u^TAv$ using chernoff bound arguements. However suppose now we want to analyze the value of $u^TA^2v$. This time due to a lot of dependencies among the variables a chernoff type arguement becomes difficult or at least I cannot see it straightaway. Could someone point me to an analysis for this scenario ?

  • $\begingroup$ While this is not an answer, it seems that powers of such an A will become "more and more Gaussian": maybe this might yield a back of the envelope estimate for the behavior ? $\endgroup$ Jun 15, 2013 at 4:24
  • $\begingroup$ Yes, thats what my guess is and I have been trying to formalize it exactly but havent got much progress yet .. was just wondering if there is already work on it $\endgroup$
    – NAg
    Jun 15, 2013 at 17:11
  • 1
    $\begingroup$ There is the notion of subgaussian tails that is sufficient to prove a number of tail bounds on variables of this kind. It might be that you can show that the variables in A^2 have this property. See for example this paper by Matousek: dl.acm.org/citation.cfm?id=1400129 $\endgroup$ Jun 15, 2013 at 17:30
  • $\begingroup$ Thanks a lot for the links. Yes we would get that each entry in A^2 has a sub-gaussian tail, however I am not yet sure as to how to avoid the problem of dependence between these entries when we take their sum when computing uA^2v. The paper referred above does give a sub-gaussian behaviour result for sums of independent sub-gaussian variables. I am not sure how to avoid the dependence issues that arise here. $\endgroup$
    – NAg
    Jun 15, 2013 at 22:50
  • $\begingroup$ again, I'm just wildly speculating, but maybe the dependency can be controlled and you can use a "weak dependence" chernoff bound (of which there are a few flavors) $\endgroup$ Jun 16, 2013 at 6:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.