Kernel/Basis function design with regularizer

I am solving this problem: $$\sum_i \parallel f(x_i)- y_i\parallel_2^2 + \lambda <\psi f, \psi f>_{L_2}^2$$ where the second part $<\psi f, \psi f>_2^2$ is regularizer using the linear operand in hilbert space $\psi$. When I model my function $f$ as $$f(x)=\sum_k k(x, x_k) \alpha_k$$ the regression problem becomes $$\parallel K\alpha -y \parallel_2^2 + \lambda \alpha^T F_{reg} \alpha$$

And now to the question:

Which functions types $k(x,y)$ can be used with respoect to the regularizer?

• Gaussian: $F_{reg}=I$ since the kernel is the optimal result for the smoothness regularizer $\parallel \psi f\parallel^2=\int dx \sum_m \frac{\sigma^{2m}}{m!2^m}(\psi f)$ (see A. Smola, B. Schölkopf, On a Kernel-based Method for Pattern Recognition, Regression, Approximation, and Operator Inversion, 1997)

• What happens in the case of a (conditional) positive semi definite function k like $$k(x_i,x)=n_i^T(x_i-x)$$ with $n_i$ being the surface normal vector at $x_i$.

Will I need a polynomial $b(x)^Tc$ with orthogonality constraints to restrict the solution, like in the case of thin plate kernels? $$\begin{pmatrix} K & B^T\\ B & 0\end{pmatrix} \begin{pmatrix} \alpha\\ c \end{pmatrix} = \begin{pmatrix} y\\0 \end{pmatrix}$$

Can I then design my regularizator using the standard procedure? $$[F_{reg}]_{i,j}=<\psi f(x_i), \psi f(x_j)>_{L_2}$$ (where $[\cdot, \cdot]_{i,j}$ means the i-th and j-th element of the matrix in the braces).

• A Hinge functions PSD ?? :)

• You can use any $\psi$ to define your kernel. If you want to specify the kernel function directly, a necessary condition is that the induced matrix $F_reg$ is positive semi-definite (PSD). – Theja Oct 14 '13 at 20:43
• Ahh oh, cool! And what's about the case when I derive the kernel from $\psi$? Did I assume correctly that the regularization matrix should/may be $I$? Or even the same kernel? Or just PSD? :) – mojovski Oct 16 '13 at 16:24
• When you specify $\psi$, you have defined a PSD kernel implicitly. For the $F_{reg}$ to be identity matrix, you need an identity map $\psi:\mathbb{R}^d\rightarrow\mathbb{R}^d$, that is $\psi(x) = x$ where $x$ is d-dimensional. – Theja Oct 16 '13 at 21:13