On Semiseparable Kernels and Efficient Computation of Regularized System Identification and Function Estimation⁎This work was supported by the Thousand Youth Talents Plan funded by the central government of China, the general project funded by NSFC under contract No. 61773329, the Shenzhen research projects funded by the Shenzhen Science and Technology Innovation Council under contract No. Ji-20170189 (JCY20170411102101881), the President's grant under contract No. PF. 01.000249 and the Start-up grant under contract No. 2014.0003.23 funded by the Chinese University of Hong Kong, Shenzhen. Issue 2 (2020) - Chen, Tianshi; Andersen, Martin S.
Abstract: A long-standing problem for kernel-based regularization methods is their high computational complexity O(N 3 ), where N is the number of data points. In this paper, we show that for semiseparable kernels and some typical input signals, their computational complexity can be lowered to O(Nq 2 ), where q is the output kernel's semiseparability rank that only depends on the chosen kernel and the input signal.