I am seeking for help about whether the following inequality is true:
I have k rank-one real matrices in $R^{d\times d}$, $x_1x_1^T, x_2x_2^T,...,x_kx_k^T$, where each $x_i$ is a vector in $R^d$ and $||x_i||_2\leq 1$, and I have k real vectors $y_1,y_2,...,y_k$ in $R^d$ and $||y_i||_2\leq c$ for each i. Is the following inequality true?
$||\sum_{i=1}^k x_ix_i^Ty_i||_2\leq c\sqrt{d}||\sum_{i=1}^k x_ix_i^T||_2$?
I have tried to prove it but so far I have not found a way to do that.
I can get the following: $||\sum_{i=1}^k x_ix_i^Ty_i||_2\leq \sum_{i=1}^{k}||x_ix_i^Ty_i||_2\leq \sum_{i=1}^{k}||x_ix_i^T||_2||y_i||_2\leq c\sum_{i=1}^{k}\lambda_{max}(x_ix_i^T)\leq ck$. But I want to prove $||\sum_{i=1}^k x_ix_i^Ty_i||_2\leq c\sqrt{d}||\sum_{i=1}^k x_ix_i^T||_2$.
At first I wanted to prove $||\sum_{i=1}^k x_ix_i^Ty_i||_2\leq c||\sum_{i=1}^k x_ix_i^T||_2$, but I found a counter-example by taking $x_1x_1^T=\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}$， $x_2x_2^T=\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}$, and $y_1=[1, 0]$, $y_2=[0,1]$, by this, $c=1$, LHS=$\sqrt{2}$, so I guess there should be a $\sqrt{d}$ in the RHS. I have not found a counter-example for $||\sum_{i=1}^k x_ix_i^Ty_i||_2\leq c\sqrt{d}||\sum_{i=1}^k x_ix_i^T||_2$. Could anyone please help prove it right or wrong?
Exodd has helped me with the question below. I want to further prove the following result: $||(\sum_{i=1}^k x_ix_i^T+\lambda I)^{-1}\sum_{i=1}^k x_ix_i^Ty_i||_2\leq c\sqrt{d}$.
Is this provable? Previously I thought if the first inequality is true, then this one will directly follows, but I made a mistake, below is what I tried:
$||(\sum_{i=1}^k x_ix_i^T+\lambda I)^{-1}\sum_{i=1}^k x_ix_i^Ty_i||_2\leq ||(\sum_{i=1}^k x_ix_i^T+\lambda I)^{-1}||_2 ||\sum_{i=1}^k x_ix_i^Ty_i||_2\\\leq c\sqrt{d}||(\sum_{i=1}^k x_ix_i^T+\lambda I)^{-1}||_2 ||\sum_{i=1}^k x_ix_i^T||_2\leq c\sqrt{d}$.
But I found that I can not get $||(\sum_{i=1}^k x_ix_i^T+\lambda I)^{-1}||_2 ||\sum_{i=1}^k x_ix_i^T||_2 \leq 1$. Then, can we prove the inequality holds?
Million thanks!
First of all, call $A$ the $d\times k$ matrix that has $x_i$ as columns, and $z$ a length $k$ vector whose entries are $x_i^Ty_i$.
$$ \|\sum_{i=1}^k x_ix_i^Ty_i\|_2^2 = \|Az\|_2^2 \le \|A\|_2^2 \|z\|_2^2\\ =\|A\|_2^2\sum_i (x_i^Ty_i)^2 \le \|A\|_2^2\sum_i \|x_i\|_2^2\|y_i\|_2^2\\ \le c^2\|A\|_2^2\sum_i \|x_i\|_2^2 = c^2\|A\|_2^2\|A\|_F^2\\ \le c^2d\|A\|_2^4 = c^2d\|AA^T\|_2^2 = c^2d||\sum_{i=1}^k x_ix_i^T||_2^2. $$ I used only the submultiplicative property of the norm for vectors and matrices, the fact that $d\|M\|^2_2\ge\|M\|_F^2$ and $\|M\|_2^2=\|MM^T\|_2$.