Fast multidimensional convolution in low-rank tensor formats via cross approximation

M. V. Rakhuba, I. V. Oseledets

    Research output: Contribution to journalArticlepeer-review

    32 Citations (Scopus)


    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.

    Original languageEnglish
    Pages (from-to)A565-A582
    JournalSIAM Journal on Scientific Computing
    Issue number2
    Publication statusPublished - 2015


    • Black box approximation
    • Cross approximation
    • Multidimensional convolution
    • Multilinear algebra
    • Tensor decompositions
    • Tensor train


    Dive into the research topics of 'Fast multidimensional convolution in low-rank tensor formats via cross approximation'. Together they form a unique fingerprint.

    Cite this