Exercise 8.11

(a) Change ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{n=1}^N{y}_n{\alpha }_n=0$ into ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{n=1}^N{y}_n{\alpha }_n\ge 0$ and ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{n=1}^N{y}_n{\alpha }_n\le 0$, i.e. $-{\sum <!--\; FUNCTION\; APPLICATION\; -->}_{n=1}^N{y}_n{\alpha }_n\ge 0$, combine these two conditions with ${\alpha }_n\ge 0$, we have

We set $M=\left[\begin{array}{cccc}\hfill y_1{x}_1\hfill & \hfill y_2{x}_2\hfill & \hfill \dots \hfill & \hfill y_N{x}_N\hfill \end{array}\right]$, where $x_n,n=1,\dots ,N$ are the column vectors with dimension $d\times 1$, so $M$ has a dimension of $d\times N$.

We also have column vectors of $y=\left[\begin{array}{c}\hfill y_1\hfill \\ \hfill y_2\hfill \\ \hfill ⋮\hfill \\ \hfill y_N\hfill \end{array}\right]$ and $\alpha =\left[\begin{array}{c}\hfill {\alpha }_1\hfill \\ \hfill {\alpha }_2\hfill \\ \hfill ⋮\hfill \\ \hfill {\alpha }_N\hfill \end{array}\right]$

Let $Q_D=M^{T}M=\left[\begin{array}{cccc}\hfill y_1{y}_1{x}_1^T{x}_1\hfill & \hfill y_1{y}_2{x}_1^T{x}_2\hfill & \hfill \dots \hfill & \hfill y_1{y}_N{x}_1^T{x}_N\hfill \\ \hfill y_n{y}_1{x}_n^T{x}_1\hfill & \hfill y_n{y}_2{x}_n^T{x}_2\hfill & \hfill \dots \hfill & \hfill y_n{y}_N{x}_n^T{x}_N\hfill \\ \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill \\ \hfill y_N{y}_1{x}_N^T{x}_1\hfill & \hfill y_N{y}_2{x}_N^T{x}_2\hfill & \hfill \dots \hfill & \hfill y_N{y}_N{x}_N^T{x}_N\hfill \end{array}\right]$. $M$ has a dimension of $N\times N$.

So we can write

(b) This part is proved in problem (a) when we construct matrix $Q_D$. So $X_s=M^T$, and $Q_D=X_s{X}_s^T$

For any vector $\alpha \ne 0$, we have

So $Q_D$ is positive semi-definite.