On semiseparable kernels and efficient implementation for regularized system identification and function estimation

A long-standing problem for kernel-based regularization methods is their high computational complexity O(N3), where N is the number of data points. In this paper, we make a breakthrough for this problem. In particular, we show that it is possible to design general semiseparable kernels through either the system theory perspective or the machine learning perspective, leading to semiseparable simulation-induced kernels or amplitude modulated locally stationary kernels, respectively. Moreover, for many frequently used test input signals in automatic control, and by exploring the semiseparable structure of a kernel and the corresponding output kernel, their computational complexity, without any approximations, can be lowered to O(Nq2) or O(Nq3), where q is the semiseparability rank of the output kernel that only depends on the chosen kernel and the input signal. Numerical simulation shows that the proposed implementation can be 104 times faster than a state of art implementation.