6
$\begingroup$

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 ?

Improve this question
$\endgroup$
8
  • $\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$
    – Suresh Venkat
    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$
    – Suresh Venkat
    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$
    – Suresh Venkat
    Jun 16, 2013 at 6:12

0

Reset to default

Your Answer

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