On the computational benefit of tensor separation for high-dimensional discrete convolutions

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 masks 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. © 2010 Springer Science+Business Media, LLC.