4
$\begingroup$

We define weighting matrix $W$ as follows

$$W := \frac{1}{Md}\left[\sum_{m=1}^{M}x^{(m)}(x^{(m)})^{T}\right] - \frac 1d \Bbb I_d$$

where $\Bbb I_d$ is the $d \times d$ identity matrix and $x^{(m)} \in \{\pm 1\}^d$. Why is $\| W \|_2 \leq 1$?


For reference, the claim that $\| W \|_2 \leq 1$ is made on page 4 here, on the bottom left.

$\endgroup$
2
$\begingroup$

Consider the matrix $ A=\frac{1}{M}\sum\limits_{m=1}^{M}x^{(m)}(x^{(m)})^{T}: $ $$ |A_{i,j}| = \left|\frac{1}{M}\sum\limits_{m=1}^{M}x_i^{(m)}x^{(m)}_j\right| \leq 1. $$ Moreover, diagonal elements $A_{i,i} = \frac{1}{M}\sum\limits_{m=1}^{M}\left(x_i^{(m)}\right)^2 = 1$. Let's $B = A - \Bbb I_d$, then $$|B_{i,j}| = |(A-\Bbb I_d)_{i,j}| \leq 1$$

Now, for $W = \frac{1}{d}B$ and arbitrary vector $x$ we have $$ \|Wx\| = \frac{1}{d}\|Bx\| = \frac{1}{d}\sqrt{\sum_i\left(\sum_jB_{i,j}x_j\right)^2} \leq \frac{1}{d}\sqrt{\sum_i\left(\sum_jB_{i,j}^2\right)\left(\sum_jx_j^2\right)} \leq \\ \le \frac{1}{d}\sqrt{d^2 \|x\|^2} = \|x\|, $$ which means $\|W\| \leq 1$.

$\endgroup$

Your Answer

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