bilinear form tail bound

Question

Let $A\in \mathbb{R}^{n\times n}$ and $u$ and $v$ be independent random $\{-1,1\}^n$-vectors. (i.e., each coordinate of $u$ is $1$ with prob. $1/2$ and $-1$ with prob. 1/2 and the coordinates of $u$ are independent with each other)

Question. Is there a tail bound for $\Pr\{u^T A v > t\}$?

I am hoping something like $\Pr\{|u^T A v| > t\} \leq e^{-c_n ||A||_F^2}$, where $||A||_F$ is the Frobenius norm of $A$ and $c_n < 1$ is some constant dependent on $n$. Is this possible?

I saw that there had been work to bound the quadratic form $\Pr\{u^T A u > t\}$ but I cannot find anything regarding the bilinear form $u^T Av$.

Answer 1

You can write the bilinear form as a quadratic form, by letting x = (u,v) and rewrite the matrix A.

Answer 2

The Hanson-Wright inequality says $$ \mathop{\mathbb{P}}_{u,v}(|u^T A v| > t) \le C\cdot \max\left\{e^{-c t^2/\|A\|_F^2}, e^{-c t/\|A\|}\right\} $$ where $\|\cdot\|$ is the largest singular value and $C,c>0$ are universal constants (independent of $A,n$).