Let $\mathbf{Y}\in\mathbb{R}^{n\times n}$ be a symmetric matrix. Let $\mathbf{x}\in\mathbb{R}^n$ be random vectors with entries i.i.d. $\pm 1$ with equal probability. I'm interested in a lower bound on


where the expectation is w.r.t. $\mathbf{x}$. An obvious lower bound based on Jenson's inequality is $|tr(\mathbf{Y})|$. I was wondering if anything sharper is known.

To be more clear about the kind of problem I care about assume $\mathbf{Y}=\mathbf{y}\mathbf{y}^T-\mathbf{z}\mathbf{z}^T$ then $|tr(\mathbf{Y})|=\big|||\mathbf{y}||_{\ell_2}^2-||\mathbf{z}||_{\ell_2}^2\big|$. However, I would like to prove something like

$\mathbb{E}[|\mathbf{x}^T\mathbf{Y}\mathbf{x}|]\ge c ||\mathbf{y}-\mathbf{z}||_{\ell_2}||\mathbf{y}+\mathbf{z}||_{\ell_2}$

with $c$ a fixed numerical constant.


If diagonal entries of $Y$ are zero then there is an open question of Pełczyński which asks whether we have the lower bound
$$ \mathbb{E} |x^{T}Yx| \geq \frac{1}{2} \sqrt{\mathbb{E} |x^{T}Yx|^{2}} ? $$

K. Oleszkiewicz writes in his slides (see slides 170) https://simons.berkeley.edu/sites/default/files/docs/481/oleszkiewiczslides.pdf

Known to be true for n ≤ 6. In general, unknown ...

Remark: One can weaken the assumption "diagonal entries of $Y$ are zero" to "$\mathrm{Tr}(Y)=0$" but then the conclusion would be $$ \mathbb{E} |x^{T}Yx| \geq \frac{1}{2} \sqrt{\mathbb{E} |x^{T}Y^{0}x|^{2}}? $$ where $Y^{0}$ is obtained from $Y$ by removing diagonal entries. Indeed, this follows from the identity $x^{T}Yx=x^{T}Y^{0}x$.


Since $Y$ is diagonal you get $M$ such that $M^TM=Y$ so $x^TYx=|Mx|^2$

let's say $X_1$ is centered

then $$E(X^T Y X)=\sum_{i=1}^n\text{Var}(\sum_{j=1}^n M_{ij}X_j)$$

then since $X_j$ are independent you get : $$\text{Var}(\sum_{j=1}^n M_{ij}X_j)=\sum_{j=1} M_{ij}^2\text{Var}(X_j)$$ because they have same law $$\text{Var}(\sum_{j=1}^n M_{ij}X_j)=\text{Var}(X_1)\sum_{j=1} M_{ij}^2$$ now you sum over $i$ and you get : $$E(X^T Y X)=\text{Var}(X_1)\bf{1}^T Y \bf{1}$$ where $\bf{1}$ is the vector full of ones

  • $\begingroup$ The problem with your calculation is that Y is not PSD. In particular as I mentioned $\mathbf{Y}=\mathbf{y}\mathbf{y}^T-\mathbf{z}\mathbf{z}^T$ which is not PSD. $\endgroup$ – Anahita Apr 6 '16 at 17:02
  • $\begingroup$ you're right but you get $$E(|X^TYX|)\geq \text{Var}(X_1)|\mathbf{1}^TY\mathbf{1}|$$ there are many ways to get to the same point but you can get it by saying that it exists $Y_1,Y_2$ spd and using that $E|A-B|\geq E(A)-E(B)$ $\endgroup$ – MJ73550 Apr 7 '16 at 8:16
  • $\begingroup$ Thanks, I'm not sure about the part on |1^TY1| and where that comes from. But if I use the E|A-B|\ge |E(A)-E(B)| trick I get $|tr(\mathbf{Y})|=|||\mathbf{y}||_{\ell_2}^2-||\mathbf{z}||_{\ell_2}^2|$. Please note that I want something stronger as I explained in the question. $\endgroup$ – Anahita Apr 8 '16 at 19:11
  • 1
    $\begingroup$ $Y=Y_1 - Y_2$, with $Y_1,Y_2$ SPD $$E(|X^TYX|)=E(|X^TY_1X - X^TY_2X|)\geq |E(X^TY_1X)-E(X^TY_2X)|=\text{Var}(X_1)|\mathbf{1}^TY\mathbf{1}|$$ using the result in the answer. in the case $Y=yy^T-zz^T$, you get : $\mathbf{1}^TY\mathbf{1} = (\sum_i y_i)^2 - (\sum_i z_i)^2$ $\endgroup$ – MJ73550 Apr 11 '16 at 7:40

The expectation can be computed in closed form, and I think that without further assumptions on entries of the matrix $Y$, the Jensen bound is sharp according to following calculation: $\begin{align}\mathbb{E}\left[\boldsymbol{X^{t}YX}\right] & =\mathbb{E}\left[\sum_{\substack{1\le i,j\le n} }X_{i}X_{j}Y_{ij}\right]\\ & =\sum_{m=-n}^{n}\mathbb{E}\left[\sum_{1\le i,j\le n}X_{i}X_{j}Y_{ij}\left|\sum_{i=1}^{n}X_{i}=m\right.\right]\mathbb{P}\left(\sum_{i=1}^{n}X_{i}=m\right)\\ & =\sum_{m=-n}^{n}\sum_{1\le i,j\le n}Y_{ij}\mathbb{E}\left[X_{i}X_{j}\left|\sum_{i=1}^{n}X_{i}=m\right.\right]\mathbb{P}\left(\sum_{i=1}^{n}X_{i}=m\right)\\ & =\sum_{m=-n}^{n}\sum_{1\le i,j\le n}Y_{ij}\left\{ x_{i}x_{j}\mathbb{P}\left(X_{i}=x_{i},X_{j}=x_{j}\left|\sum_{i=1}^{n}X_{i}=m\right.\right)\right\} \mathbb{P}\left(\sum_{i=1}^{n}X_{i}=m\right)\\ & =\sum_{m=-n}^{n}\sum_{1\le i,j\le n}Y_{ij}\left\{ \sum_{x_{i},x_{j}\in\{\pm1\}}x_{i}x_{j}\mathbb{P}\left(\left.\sum_{i=1}^{n}X_{i}=m\right|X_{i}=x_{i},X_{j}=x_{j}\right)\mathbb{P}\left(X_{i}=x_{i},X_{j}=x_{j}\right)\right\} \\ & \text{The probability }\mathbb{P}\left(X_{i}=x_{i},X_{j}=x_{j}\right)=\left(\frac{1}{2}\right)^{x_{i}+x_{j}}\left(\frac{1}{2}\right)^{2-x_{i}-x_{j}}=\frac{1}{4},\forall x_{i},x_{j}\in\{\pm1\}\\ & =\sum_{m=-n}^{n}\sum_{1\le i,j\le n}Y_{ij}\frac{1}{4}\left\{ \sum_{x_{i},x_{j}\in\{\pm1\}}x_{i}x_{j}\mathbb{P}\left(\left.\sum_{i=1}^{n}X_{i}=m\right|X_{i}=x_{i},X_{j}=x_{j}\right)\right\} \\ & \text{The probability }\mathbb{P}\left(\left.\sum_{i=1}^{n}X_{i}=m\right|X_{i}=x_{i},X_{j}=x_{j}\right)=\begin{cases} m\neq\pm n,\pm(n-2) & \begin{cases} \frac{\left(\begin{array}{c} n-2\\ \frac{n-2-m}{2} \end{array}\right)\left(\frac{1}{2}\right)^{\frac{n-2-m}{2}+m}\left(\frac{1}{2}\right)^{\frac{n-2-m}{2}}}{1/4} & n-m\,even\\ 0 & n-m\,odd \end{cases}\\ m=\pm n & \left(\frac{1}{2}\right)^{n}I_{(x_{i}=x_{j}=1)}\text{ or }\left(\frac{1}{2}\right)^{n}I_{(x_{i}=x_{j}=-1)}\\ m=\pm(n-2) & \left(\frac{1}{2}\right)^{n}I_{(x_{i}=1,x_{j}=-1)}\text{ or }\left(\frac{1}{2}\right)^{n}I_{(x_{i}=-1,x_{j}=1)} \end{cases}\,\text{treated as a 1-d random walk.}\\ & \text{Following simplification assumes }m\neq\pm n,\pm(n-2)\\ & =\sum_{m=-n}^{n}\sum_{1\le i,j\le n}Y_{ij}\frac{1}{4}\left\{ \sum_{x_{i},x_{j}\in\{\pm1\}}x_{i}x_{j}\left(\frac{1+(-1)^{n-m}}{2}\right)\cdot\frac{\left(\begin{array}{c} n-2\\ \frac{n-2-m}{2} \end{array}\right)\left(\frac{1}{2}\right)^{\frac{n-2-m}{2}+m}\left(\frac{1}{2}\right)^{\frac{n-2-m}{2}}}{1/4}\right\} \\ & =\sum_{m=-n}^{n}\sum_{1\le i,j\le n}Y_{ij}\left\{ \sum_{x_{i},x_{j}\in\{\pm1\}}x_{i}x_{j}\left(\frac{1+(-1)^{n-m}}{2}\right)\cdot\left(\begin{array}{c} n-2\\ \frac{n-2-m}{2} \end{array}\right)\left(\frac{1}{2}\right)^{\frac{n-2-m}{2}+m}\left(\frac{1}{2}\right)^{\frac{n-2-m}{2}}\right\} \end{align} $ If $Y=I_n$ then the lower bound is literally reached. If you want a Hanson-Wright type concentration bound, then it can be improved since Bernoulli random vectors are sub-gaussian:

Hanson-Wright inequality.

Let $X=(X_{1},\cdots X_{n})\in\mathbb{R}^{n}$ be a random vector with independent components $X_{i}$ such that


(ii) $\left\Vert X_{i}\right\Vert _{\psi_{2}}= sup_{p\geq1}p^{-\frac{1}{2}}\left[E\left|X\right|^{p}\right]^{\frac{1}{p}}\leq K$ i.e. its components have uniform sub-gaussian norm.

Then for arbitrary n\times n constant matrix A and $\forall t\geq 0$ we can assert that

$Pr\left\{ \left|X^{t}AX-EX^{t}AX\right|>t\right\} \leq2exp\left(-c\cdot min\left(\frac{t^{2}}{K^{4}\left\Vert A\right\Vert _{HS}^{2}},\frac{t}{K^{2}\left\Vert A\right\Vert }\right)\right)$ for some constant $c>0$.

where $\left\Vert A\right\Vert =max_{x\neq0}\frac{\left\Vert Ax\right\Vert _{L^{2}}}{\left\Vert x\right\Vert _{L^{2}}}$ and $\left\Vert A\right\Vert _{HS}=\sqrt{\sum_{i,j}\left|a_{ij}\right|^{2}}$.

It is readily verifed that a Bernoulli random vector satisfies (i)(ii) with $K=2$. Therefore we can assert that

$$Pr\left\{ \left|X^{t}YX-EX^{t}YX\right|>t\right\} \leq2exp\left(-c\cdot min\left(\frac{t^{2}}{K^{4}\left\Vert Y\right\Vert _{HS}^{2}},\frac{t}{K^{2}\left\Vert Y\right\Vert }\right)\right)$$

where $Y=yy^{t}-zz^{t}$ is symmetric as stated in the OP.

  • $\begingroup$ But we need $\mathbb{E} |x^{T} Y x|$ not $\mathbb{E} x^{T} Yx$ correct? And by the way, of course $\mathbb{E} x^{T} Yx = \mathrm{Tr} \, Y$ $\endgroup$ – Paata Ivanishvili May 5 '17 at 4:03
  • $\begingroup$ Yes. So this is not the full answer. $\endgroup$ – Henry.L May 5 '17 at 4:14

If Y is any diagonal matrix then the lower bound is achieved so the lower bound is tight for diagonal matrices. There can't be any sharper bound defined in terms of eigen values since there exists a diagonal matrix with those eigenvalues.

Update after edit to the question:

If a bound of the type $c||y-z|| ||y + z||$ has to be better than the trace bound then it has to match the trace bound in the special case where $y,z$ are $[0, 1, \ldots ]$ and $[1, 0, \ldots]$ orthogonal basis vectors. In this case $Y$ would again be a diagonal matrix with only two non-zero entries. Moreover, $E[|x^TYx|]$ would be $E[|(x_1)^2 - (x_2)^2|] = 0$ and $||y-z|| = ||y + z|| = \sqrt{2}$. Which means $0 \ge c \times 2 \implies c = 0$. So this form of bound is not going to lead anywhere.

Thinking more geometrically what you need are constraints on the angle between $y,z$ and you need to quantify how much energy a hyperplane spanned by $y,z$ is allowed to receive. So the $c$ in your hypothesized bound can't be a constant but has to depend on $y,z$

  • $\begingroup$ Thanks I agree with that. But there could be additional terms involved in the lower-bound based on the off diagonal entries. I'm interested in those additional terms $\endgroup$ – Anahita Apr 6 '16 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.