Fast Kernel Smoothing by a Low-Rank Approximation of the Kernel Toeplitz Matrix

Abstract

Kernel smoothing methods, including the bilateral filter, are commonly used in data processing/modeling and edge-aware image smoothing. Due to their nonlinear nature, these filters require significant computational time. In this paper, we address this problem by studying a practical case in which the data to be processed are integers. The basic idea is to use eigendecomposition to approximate the kernel matrix which is a real symmetric Toeplitz matrix. This approximation leads to more efficient computation. We study the distribution of its eigenvalues and show that the upper bounds of the eigenvalues can be expressed analytically in terms of the Fourier transform of the kernel function. This..