2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ I never thought it was that simple. No wonder the paper just related it by a few words! $\endgroup$ – Vito Chou Oct 19 '16 at 3:10

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.