Fast Hankel Tensor-Vector Products and Application to Exponential Data Fitting

Weiyang Ding, Liqun Qi, Yimin WeiarXiv 2014 · DOI · arXiv

TL;DR

This paper introduces a fast algorithm for computing products between Hankel tensors and vectors, reducing computational complexity from exponential $O(n^m)$ to nearly linear $O(m^2 n \log mn)$. By embedding Hankel tensors into a larger class of "anti-circulant" tensors diagonalized by the Fourier matrix, the authors enable the use of Fast Fourier Transforms (FFT) to dramatically accelerate exponential data fitting in both 1D and 2D.

What Problem Does This Paper Address?

In signal processing, we often model data as a sum of decaying sinusoids (exponential data fitting). While matrices have long been used for this, "tensors"—the multi-dimensional generalization of matrices—offer better performance and robustness. However, tensors come with a "curse of dimensionality."

A general tensor-vector product for a tensor of order $m$ and dimension $n$ requires $O(n^m)$ operations, which quickly becomes impossible as the order or dimension grows. Hankel tensors (where entries depend only on the sum of their indices) are highly structured and have far fewer degrees of freedom than general tensors, yet until this paper, there wasn't a widely discussed "fast" way to exploit that structure for tensor-vector products.

Methods

The authors bridge the gap between matrix theory and tensor algebra using a three-step approach:

  1. Defining Anti-Circulant Tensors: They identify a special class of Hankel tensors called anti-circulant tensors. Much like circulant matrices, these tensors can be diagonalized using the Fourier matrix.
  2. The Embedding Trick: To handle a general Hankel tensor, the authors "embed" it into a larger anti-circulant tensor. This is analogous to how a Toeplitz matrix is often embedded into a larger circulant matrix to allow for fast multiplication via FFT.
  3. FFT-Based Computation: Once embedded, the tensor-vector product can be computed entirely in the frequency domain. Instead of massive multi-dimensional sums, the algorithm performs a series of 1D FFTs, element-wise multiplications, and an inverse FFT.

The authors also extend this to Block Hankel Tensors (BHHB - Block Hankel with Hankel Blocks) to handle multi-dimensional signals, such as 2D image data or multi-channel sensor arrays.

Datasets

The paper evaluates the algorithm using synthetic numerical examples rather than public repositories:

  • 1D Signal Simulation: A 3rd-order square Hankel tensor used to compare running times between the new fast algorithm and the standard non-structured approach.
  • 2D Exponential Data Fitting: A complex signal modeled with two "peaks" (exponential items) and varying levels of Gaussian noise (from $10^{-8}$ to $10^{-4}$). This was used to test the accuracy and noise-robustness of the block-version algorithm.

Key Insights and Ideas

  • The Diagonalization "Aha!": The realization that anti-circulant tensors are diagonalized by the Fourier matrix is the cornerstone. It transforms a complex spatial-domain operation into a simple frequency-domain operation.
  • Compact Representation: The algorithm never actually "forms" the full tensor in memory. It only requires the generating vector (the unique values that define the Hankel structure). This makes the algorithm extremely memory-efficient.
  • Ensemble Processing: Unlike standard methods that multiply the tensor by vectors mode-by-mode, this algorithm treats the tensor as an "ensemble," processing the entire structure simultaneously through the FFT.

Key Results

  • Massive Speedup: For a square Hankel tensor, the complexity drops from $O(n^m)$ to $O(m^2 n \log mn)$. In practical tests (Figure 2), the running time for the non-structured algorithm grew exponentially with size, while the fast algorithm's runtime remained nearly flat.
  • High Precision: In 2D data fitting tasks, the relative error of the estimated signal poles stayed at the same level as the input noise. This proves that the speedup doesn't come at the cost of numerical accuracy.
  • Scalability: The block version successfully handled 2D signal recovery, which is typically much more computationally demanding than 1D cases.

Limitations and Future Work

  • Square Tensor Focus: Much of the detailed complexity analysis and the specific HOOI (Higher-Order Orthogonal Iteration) application focus on square tensors ($n_1 = n_2 = \dots = n_m$). While the theory supports rectangular tensors, the most optimized implementations are for the square case.
  • Algorithm Integration: The authors note that this fast scheme is a "building block." The next step is to integrate it into a wider variety of tensor decomposition algorithms (beyond HOOI) and other signal processing applications like image deblurring or wireless communication channel estimation.
  • Higher-Level Blocks: While 2D fitting is addressed, the paper only briefly mentions higher-level (level-$k$) block tensors, leaving the implementation details for very high-dimensional data for future research.

Summary updated

Abstract

This paper is contributed to a fast algorithm for Hankel tensor-vector products. For this purpose, we first discuss a special class of Hankel tensors that can be diagonalized by the Fourier matrix, which is called \emph{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 $\mathcal{O}(m^2 n \log mn)$ 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 as well. Finally, we apply the fast algorithm to exponential data fitting and the block version to 2D exponential data fitting for higher performance.
BibTeX
@misc{ding2014fast,
  author = {Weiyang Ding and Liqun Qi and Yimin Wei},
  title = {{Fast Hankel Tensor-Vector Products and Application to Exponential Data Fitting}},
  year = {2014},
  eprint = {1401.6238},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1401.6238},
}
Figure