Fast Hankel tensor-vector product and its application to exponential data fitting

This paper is contributed to a fast algorithm for Hankel tensor-vector products. First, we explain the necessity of fast algorithms for Hankel and block Hankel tensor-vector products by sketching the algorithm for both one-dimensional and multi-dimensional exponential data fitting. For proposing the fast algorithm, we define and investigate a special class of Hankel tensors that can be diagonalized by the Fourier matrices, which is called anti-circulant tensors. Then, we obtain a fast algorithm for Hankel tensor-vector products by embedding a Hankel tensor into a larger anti-circulant tensor. The computational complexity is about O(m²nlogmn) for a square Hankel tensor of order m and dimension n, and the numerical examples also show the efficiency of this scheme. Moreover, the block version for multi-level block Hankel tensors is discussed.