2
$\begingroup$

I have found a lot of references on quadratic forms of Normal Random Variables but was not able to find any reference on quadratic forms of {+1,-1} random variables. Formally, let $X_i$ be independent random variables taking values $1,-1$ with equal probability. A quadratic form on these is defined by

$$A = \sum a_{ij}X_i.X_j$$

What bounds can we get on moments of such forms or what can be said about their tails ? References would be great.

$\endgroup$

2 Answers 2

3
$\begingroup$

You may take a look at Proposition 8.13 in A Mathematical Introduction to Compressive Sensing by Simon Foucart and Holger Rauhut.

Let $\mathbf x$ be a Rademacher vector. For a self-adjoint matrix $\mathbf M$ with zero diagonal we consider the homogeneous Rademacher chaos

$$X := \mathbf x^*\mathbf M \mathbf x = \sum_{i\neq j} x_iM_{ij}x_j.$$

They showed Hanson-Wright type tail bound with specific constants.

$$\Pr[|x| \geq t] \leq 2 \exp\left(-\min\left[ \frac{3t^2}{128||\mathbf M||_F^2}, \frac{t}{32||\mathbf M||_{2\to 2}} \right]\right)$$

If your matrix $\mathbf M$ is not diagonal-free, you may take a look at the paper by Mark Rudelson and Roman Vershynin on how to handle the diagonal entries separately.

$\endgroup$
2
$\begingroup$

See the paper A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables by D. L. Hanson and F. T. Wright, The Annals of Mathematical Statistics Vol. 42, No. 3 (Jun., 1971), pp. 1079-1083.

$\endgroup$
1
  • $\begingroup$ The paper has bounds for variables that are sub-gaussian. My case is much simpler and probably tighter bounds can be expected. $\endgroup$ Jul 14, 2013 at 4:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .