Kernel SVM and Sparsity

Support vector machines become far more powerful when we move beyond linear boundaries, and kernels make this possible without ever computing features explicitly. Kernel SVMs map data into high-dimensional spaces where complex patterns become separable, all while keeping computations efficient through the Gram matrix.

In this lesson, we will explore how kernels work in the dual formulation and implement them using cvxpy and sklearn-style functions. We will also examine an important property of SVMs, sparsity, which explains why SVMs generalize well even in very high-dimensional spaces.

Kernels in SVM

The dual formulation straightforwardly offers kernelization of SVM. As we notice in the following dual optimization problem, the Gram matrix $K$ can be computed using any kernel function:

$$\begin{aligned} \max_{\bold a} \quad & \bold a^T\bold 1 - \frac{1}{2}\bold a^T_{\bold y}K\bold a_{\bold y}\\ \textrm{s.t.} \quad & 0\le \bold a \le C \end{aligned}$$ ...