CUED Publications database

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

Calliess, JP and Mai, M and Pfeiffer, S (2012) On the computational benefit of tensor separation for high-dimensional discrete convolutions. Multidimensional Systems and Signal Processing, 23. pp. 255-279. ISSN 0923-6082

Full text not available from this repository.


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.

Item Type: Article
Divisions: Div F > Computational and Biological Learning
Depositing User: Cron Job
Date Deposited: 17 Jul 2017 19:05
Last Modified: 17 May 2018 07:53