A Superfast Direct Solver for 2D Type-II Inverse Nonuniform Discrete Fourier Transform Based on Hierarchically Semiseparable Matrices
Abstract
Reconstructing images on Cartesian grids from nonuniform Fourier samples is a basic computational task in Fourier reconstruction methods for computed tomography. This paper proposes a direct solver for the 2D type-II nonuniform discrete Fourier transform~(NUDFT) based on the face-splitting product of hierarchically semiseparable~(HSS) matrices. We define the face-splitting product of two HSS trees and prove that the face-splitting product of two HSS matrices admits an HSS representation on the resulting tree. The proof is constructive, providing explicit formulas for the HSS generators and bounds on the off-diagonal ranks at each level. For the NUDFT, a Fourier change of basis expresses the transformed 2D matrix as a face-splitting product of two transformed 1D NUDFT matrices. This identity yields an algebraic construction of a 2D HSS approximation from two 1D HSS approximations, for which we establish a Frobenius-norm approximation error bound. Combining this construction with recompression, URV factorization, and a two-dimensional inverse fast Fourier transform gives a direct solver for the associated least-squares problem. For fixed accuracy, square frequency grids, and balanced HSS trees with fixed leaf column sizes, the solver has an offline complexity of O(M log2 N + N3 / 2 log3 N) and an online complexity of O(M + N log3 N) per right-hand side, where M and N are the numbers of sample points and unknown coefficients, respectively. Numerical experiments on random and polar grids illustrate the computational scaling and reconstruction accuracy of the method, and demonstrate a substantial reduction in lsqr iteration counts when the direct solver is used as a preconditioner.
Related
- Approximate Inversion of Discrete Fourier Integral Operators via Hierarchically Semiseparable Matrices
- FASS: Discrete Fourier Transform Adapters for Speech Separation With Incremental Learning
- The Taylor Integral and a Generalization of the Discrete Fourier Transform
- Counterexamples to uniqueness for a discrete X-ray transform under quadratic decay
- Explicit formula for the discrete Laplace transform of the Möbius function, related special functions, and a criterion for the Riemann hypothesis
BibTeX
@misc{li2026superfast,
title = {{A Superfast Direct Solver for 2D Type-II Inverse Nonuniform Discrete Fourier Transform Based on Hierarchically Semiseparable Matrices}},
author = {Yingzhou Li and Jingyu Liu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.00928},
eprint = {2607.00928},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.00928},
}
RIS
TY - UNPB
TI - A Superfast Direct Solver for 2D Type-II Inverse Nonuniform Discrete Fourier Transform Based on Hierarchically Semiseparable Matrices
AU - Yingzhou Li
AU - Jingyu Liu
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2607.00928
UR - https://arxiv.org/abs/2607.00928
AB - Reconstructing images on Cartesian grids from nonuniform Fourier samples is a basic computational task in Fourier reconstruction methods for computed tomography. This paper proposes a direct solver for the 2D type-II nonuniform discrete Fourier transform~(NUDFT) based on the face-splitting product of hierarchically semiseparable~(HSS) matrices. We define the face-splitting product of two HSS trees and prove that the face-splitting product of two HSS matrices admits an HSS representation on the resulting tree. The proof is constructive, providing explicit formulas for the HSS generators and bounds on the off-diagonal ranks at each level. For the NUDFT, a Fourier change of basis expresses the transformed 2D matrix as a face-splitting product of two transformed 1D NUDFT matrices. This identity yields an algebraic construction of a 2D HSS approximation from two 1D HSS approximations, for which we establish a Frobenius-norm approximation error bound. Combining this construction with recompression, URV factorization, and a two-dimensional inverse fast Fourier transform gives a direct solver for the associated least-squares problem. For fixed accuracy, square frequency grids, and balanced HSS trees with fixed leaf column sizes, the solver has an offline complexity of O(M log^2 N + N^3 / 2 log^3 N) and an online complexity of O(M + N log^3 N) per right-hand side, where M and N are the numbers of sample points and unknown coefficients, respectively. Numerical experiments on random and polar grids illustrate the computational scaling and reconstruction accuracy of the method, and demonstrate a substantial reduction in lsqr iteration counts when the direct solver is used as a preconditioner.
ER -