Multi-resolution autonomous linear state space filters for N-dimensional signals

Abstract

Linear filtering or convolution operations can be computationally expensive, especially in low-resource environ ments, high data rate applications, or scenarios involving large datasets. In particular, for multi-dimensional signals, the compu tational cost scales polynomially with the kernel size. In this paper, we propose the use of multi-dimensional Autonomous Linear State Space Models (ALSSMs) to reduce the computa tional complexity of convolution and correlation operations on N-dimensional signals and extend the method to (windowed) least-squares filters. For that, we work in an ALSSM subspace and provide efficient recursive computation rules that signifi cantly improve the efficiency of those filters. In addition, we provide various window functions and demonstrate paralleliza tion of computations and reuse of intermediate results for multi resolution analyses. Our method is particularly interesting for systems with limited resources, such as battery-powered and wearable devices, or when (real-time) processing of very large data sets is required, such as in the field of image processing and machine learning. We conclude with several practical examples, with ready-to-use implementations of the proposed methods as an open source Python repository.