5.6 Sparse SVM. One can give two types of arguments in favor of the SVM algorithm:

one based on the sparsity of the support vectors, another based on the notion of margin. Suppose that instead of maximizing the margin, we choose instead to maximize sparsity by minimizing the Lp norm of the vector that denes the weight vector w, for some p  1. First, consider the case p = 2.

This gives the following optimization problem:

min

;b 1

2 Xm i=1 2

i + C Xm i=1

i (5.50)

subject to yi

Xm j=1 jyjxi
xj + b



 1 ???? i; i 2 [m]

i; i  0; i 2 [m]:

(a) Show that modulo the non-negativity constraint on , the problem coincides with an instance of the primal optimization problem of SVM.

(b) Derive the dual optimization of problem of (5.50).

(c) Setting p = 1 will induce a more sparse . Derive the dual optimization in this case.