Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

share|improve this question
1  
Could you please add a reference to the work on the quadratic form? Thanks. –  blabler Jun 26 '13 at 22:36
add comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
add comment

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$).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.