Fast multidimensional convolution in low-rank formats via cross approximation

M. V. Rakhuba, I. V. Oseledets
2/23/2014
math.NA

Official code: rakhuba/tucker3d (11 stars, MIT, last commit 2019-10-08).

Abstract

We propose a new cross-conv algorithm for approximate computation of convolution in different low-rank tensor formats (tensor train, Tucker, Hierarchical Tucker). It has better complexity with respect to the tensor rank than previous approaches. The new algorithm has a high potential impact in different applications. The key idea is based on applying cross approximation in the "frequency domain", where convolution becomes a simple elementwise product. We illustrate efficiency of our algorithm by computing the three-dimensional Newton potential and by presenting preliminary results for solution of the Hartree-Fock equation on tensor-product grids.

View on arXivView PDF

Code Implementations(1)

rakhuba/tucker3dOfficial100%
MIT
113C, PythonFeb 21, 20147 years agoMIT

Similar Papers

Low-Rank Tucker Approximation of a Tensor From Streaming Data

80% match1 repo72019

Is 3D Convolution with 5D Tensors Really Necessary for Video Analysis?

79% match2024

Multi-dimensional Signal Recovery using Low-rank Deconvolution

78% match2023

Convolutions and More as Einsum: A Tensor Network Perspective with Advances for Second-Order Methods

78% match2023

conv_einsum: A Framework for Representation and Fast Evaluation of Multilinear Operations in Convolutional Tensorial Neural Networks

77% match2024

A Unifying Tensor View for Lightweight CNNs

76% match2023

Cite this paper

@article{rakhuba2014fast,
  title  = {Fast multidimensional convolution in low-rank formats via cross approximation},
  author = {M. V. Rakhuba and I. V. Oseledets},
  year   = {2014},
  eprint = {1402.5649},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/1402.5649}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/1402.5649.svg)](https://codeofpaper.com/paper/1402.5649)

Discussion