Learning From Data – A Short Course: Exercise 8.11

(a) Show that the problem in (8.21) is a standard QP-problem:

2016-11-18_151059

where Q_{D} and A_{D} (D for dual) are given by:

2016-11-20_112416

It is easy to show this, what should be noted here is that:

    \[ y^{T}\alpha = 0 \Leftrightarrow \left\{\begin{matrix} y^{T}\alpha \geq 0\\ y^{T}\alpha \leq 0 \Leftrightarrow -y^{T}\alpha \geq 0 \end{matrix}\right. \]

(b) The matrix Q_{D} of quadratic coefficients is  \left [ Q_{D} \right ]_{mn} = y_{m}y_{n}x_{m}^{T}x_{n}. Show that Q_{D} = X_{s}X^{T}_{s}, where X_{s} is the ‘signed data matrix’,

2016-11-20_113006

Hence, show that Q_{D} is positive semi-definite. This implies that the QP-problem is convex.

It is easy to show that Q_{D} = X_{s}X^{T}_{s}, what should be noted here is that:

    \[ x^{T}Q_{D}x = x^{T}X_{s}X_{s}^{T}x = (X_{s}^{T}x)^{T}(X_{s}^{T}x) = \left \| X_{s}^{T}x \right \| \geq 0 \]

Hence Q_{D} is positive semi-definite.


Facebooktwittergoogle_plusredditpinterestlinkedinmail

1 comment on “Learning From Data – A Short Course: Exercise 8.11”

Leave a Reply

Your email address will not be published. Required fields are marked *