Home | english  | Impressum | Datenschutz | Sitemap | KIT
On the computational benefit of tensor separation for high-dimensional discrete convolutions



Jan Calliess
Michael Mai
Sebastian Pfeiffer


Multidimensional Systems and Signal Processing 23 Nr. 1-2, Springer, 2012.



Utilizing separation to decompose a local filter mask is a well-known technique to accelerate its convolution with discrete two-dimensional signals such as images. However, many modern days' applications involve higher-dimensional, discrete data that needs to be processed but whose inherent spatial complexity would render immediate/naive convolutions computationally infeasible. In this paper, we show how separability of general higher-order tensors can be leveraged to reduce the computational effort for discrete convolutions from super-polynomial to polynomial (in both the filter mask's tensor order and spatial expansion). Thus, where applicable, our method compares favorably to current tensor convolution methods and, it renders linear filtering applicable to signal domains whose spatial complexity would otherwise have been prohibitively high. In addition to our theoretical guarantees, we experimentally illustrate our approach to be highly beneficial not only in theory but also in practice.