In SVM approach, quadratic programming is often used to minimize the error function.
$$\begin{align}&\min_{\Lambda} W(\Lambda)=-\Lambda^T\mathbf 1+{1\over 2}\Lambda^TD\Lambda\\
&\text{subject to}\\
&\hspace{80px}\Lambda^T\mathbf y=0\\
&\hspace{80px}\Lambda-C\mathbf 1 \le \mathbf 0\\
&\hspace{80px}-\Lambda \le \mathbf 0\\
\end{align}\\
$$
$\hspace{500px}$[Osuna et al. 1997a]
where $\Lambda^T=[\lambda_1\dots\lambda_n]$, $\mathbf 1 \in \Bbb R^{n\times 1}$ is a column vector with all elements 1, $\mathbf y \in\Bbb R^{n\times 1}$ is a column vector that $y_i\in \{+1, -1\}$, and $C$ is a positive constant.
$D\in \Bbb R^{n\times n}$ where $D_{ij}=y_iy_jK_{ij}$ and $K$ is a kernel matrix which is positive definite or positive semidefinite.
You can totally ignore the quadratic optimization problem above, I just want to show where I came out this problem.
You can just see this question below.
Let $K\in\Bbb R^{n\times n}$ be positive semidefinite and $\mathbf y\in\{1, -1\}^{n}$, show that $D\in\Bbb R^{n\times n}$ where $D_{ij}= y_iy_jK_{ij}$
Prove that $D$ is positive semidefinite.
I've seen some papers that they only related like
[Osuba et al. 1997a]: "$D$ is a positive semi-definite matrix (the kernel function $K$ is positive definite)"
or
[Joachims 1998]: "it is guaranteed to have a positive-semidefinite Hessian $Q$"
(he use $Q$ as we use $D$ to present the same matrix)
Also, I have tried to prove myself, but I got stuck facing $\mathbf y$. So for now, I only came out a few examples to convince me that it's true.
Any prove or any ideas?
Best Answer
So, I'll assume you're using the definition of positive semidefinite as follows: a matrix $M$ is PSD if $x^TMx\geq 0$ for all $x$ of appropriate dimension. Well, taking some $x\in\mathbb{R}^n$ we have that $$x^TDx = \sum_{ij} x_iD_{ij}x_j = \sum_{ij}x_iy_iK_{ij}y_jx_j = (x\odot y)^T K (x\odot y)\geq0$$
where $x\odot y$ is the $\textbf{Hadamard product}$ of the vectors $x$ and $y$, i.e. the vector with $i$-th coordinate $x_iy_i$, and the last line follows by PSDness of $K$.