Let $\|\cdot\|_2$ be the spectral norm. Let $x_1,\dots,x_n$ be i.i.d. draws from $N(0,S)$. Let $\lambda_1,\dots,\lambda_n$ be some real numbers.

Is it true that $$\|\sum_{i=1}^n \lambda_i x_i x_i^T\|\le \|\sum_{i=1}^nx_i x_i^T\|\cdot\max_i|\lambda_i|\text{ ?}$$

I know this seems like it should be straightforward, but it seems to me that this should not work since the $\lambda_i$ could be negative. Yet this is basically the same conclusion reached here on page 19, and I don't see the justification.


Since the involved matrices are symmetric, it holds $$ \|\sum_{i=1}^n \lambda_ix_ix_i^T\|_2 = \max_{\|v\|=1} \left| v^T(\sum_{i=1}^n \lambda_i x_ix_i^T)v\right| = \max_{\|v\|=1}\left|\sum_{i=1}^n \lambda_i (x_i^Tv)^2\right|. $$ Now take $v$ with $\|v\|=1$. Then $$ \left|\sum_{i=1}^n \lambda_i (x_i^Tv)^2\right| \le \sum_{i=1}^n |\lambda_i| (x_i^Tv)^2 \le \sum_{i=1}^n(x_i^Tv)^2 \cdot \max_i|\lambda_i| \le \|\sum_{i=1}^n x_ix_i^T\|_2 \cdot \|v\|^2\cdot \max_i|\lambda_i|. $$ Taking the maximum over all $v$ with $\|v\|=1$ proves $$ \left\|\sum_{i=1}^n \lambda_i (x_i^Tv)^2\right\|_2 \le \|\sum_{i=1}^n x_ix_i^T\|_2\cdot \max_i|\lambda_i|. $$ The result is a seemingly counterintuitive inequality, in the sense that the sum is inside the norm (and not outside as one might expect). In the arguments above, we apply the triangle inequality in the form $$ \left|\sum \lambda_i b_i \right| \le \sum |\lambda_i| \cdot b_i \le \max_i|\lambda_i| \cdot \sum b_i =\max_i|\lambda_i| \cdot |\sum b_i |, $$ which works as $b_i = (x_i^Tv)^2$ is non-negative.

  • $\begingroup$ Does this inequality hold for all norms, or just the spectral norm? In particular I wonder if it holds for the $\infty$ norm. $\endgroup$ – user21725 Jan 9 '15 at 20:20
  • $\begingroup$ I made this a new question: math.stackexchange.com/questions/1098220/… $\endgroup$ – user21725 Jan 9 '15 at 21:50

Your Answer

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