A Superfast Direct Solver for 2D Type-II Inverse Nonuniform Discrete Fourier Transform Based on Hierarchically Semiseparable Matrix

Jul 16, 2026

Upload by Anda

A superfast direct inversion method addresses the 2D type-II nonuniform discrete Fourier transform (NUDFT) by factoring the NUDFT matrix A as A = G F, where F is the 2D DFT matrix and G is represented through a kernel matrix. The work approximates G with a hierarchically semiseparable (HSS) matrix and estimates its HSS rank. Combining an HSS least-squares solver with a 2D inverse fast Fourier transform yields efficient offline and online solvers, and the method is designed to serve as a robust preconditioner for ill-conditioned inverse NUDFT problems with grid-like sample layouts.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages22

Reading Time55 min

Abstract

Introduction

Related Work

arXiv :2607 .00928v1 [math .NA] 1 Jul 2026 A Superfast Direct Solver for 2D Type-II Inverse Nonuniform Discrete Fourier Transform Based on Hierarchically Semiseparable Matrix Yingzhou Li∗, Jingyu Liu† July 2, 2026 Abstract This paper proposes a direct inversion method for the 2D type-II nonuniform discrete Fourier transform (NUDFT) . The NUDFT matrix A is factored as A = GF , where G can be expressed as a kernel matrix and F is the 2D DFT matrix. We show that G can be approximated by a hierarchically semiseparable (HSS) matrix and give an estimate of the HSS rank. Then, using the least-squares solver for HSS matrix and the two-dimensional inverse fast Fourier transform, the inverse NUDFT problem can be solved efficiently. Our algorithm has an offline complexity of O 􀀀 M + N3/2 log3 N􀀁 where M and N are the size of rows and columns of the NUDFT matrix, respectively. Once the direct solver is built, it can be applied to a vector with an online complexity of O􀀀 M +N log3 N􀀁 . The proposed method can be used as a preconditioner for iterative methods, especially when the sample points are distributed on a grid such that A is ill-conditioned. Numerical results are provided to show the scaling performance of the inversion method and demonstrate the efficiency and robustness of it as apreconditioner. Keywords nonuniform discrete Fourier transform, hierarchically semi-separable matrix 1 Introduction This paper considers the two-dimensional type-II nonuniform discrete Fourier transform (NUDFT) of the following form: n [x] −1 n[y] −1 fj = X X ck [x], k [y]e−2πi(k[x]xj+k[y]yj) , 0 ≤ j ≤ M − 1 , (1.1) k [x]=0 k [y]=0 where the sample points { (xj , yj)} are distributed arbitrarily in [0 , 1)2 and the frequencies { (k[x], k [y])} are distributed on a Cartesian grid of contiguous integers. Throughout the paper, the number of samples points M is assumed to be larger than or equal to the number of frequencies, i.e. , N = n [x]n [y] . When the coefficients {ck [x], k [y] } are given and one aims to compute the target values {fj }, the problem is called the forward ∗ School of Mathematical Sciences, Fudan University; Shanghai Key Laboratory for Contemporary Applied Mathematics, Fudan University, [yingzhouli@fudan.edu.cn](yingzhouli@fudan.edu.cn) †School of Mathematical Sciences, Fudan University, [jyliu22@m.fudan.edu.cn](jyliu22@m.fudan.edu.cn) NUDFT. When the target values {fj } are given and one aims to determine the coefficients {ck [x], k [y] }, the problem is called the inverse NUDFT. Both the forward and inverse NUDFT have wide applications in scientific computing, such as signal processing [2], image reconstruction [7], and fast convolution [19] etc. Let the NUDFT matrix A be defined as 1 A 􀀀j,(k[x], k [y])􀀁 = e−2πi(k[x]xj+k[y]yj) , 0 ≤ j ≤ M − 1 , 0 ≤ k [x] ≤ n [x] − 1 , 0 ≤ k [y] ≤ n [y] − 1 , (1 .2) where the column index (k[x], k [y]) is ordered in a lexicographical manner. That is, we have an underlying 1-to-1 map (k[x], k [y]) ↔ k [y] + k[x]n [y] . The forward NUDFT can be expressed as a matrix-vector multiplication f = Ac and the inverse NUDFT can be formulated as a linear least-squares problem minc ∥Ac−f∥2 , where c ∈ CN is the vectorized form of the coefficients {ck [x], k [y] } and f ∈ CM is the vector corresponding to the target values {fj } . Typically, the forward and inverse NUDFT have a complexity of O (MN) and O (MN2 ) respectively. 1.1 Related Work If the sample points are distributed on a uniformly Cartesian grid, i.e., (xj [x] , yj [y] ) = (j[x]/n [x], j [y]/n [y]) for 0 ≤ j [x] ≤ n [x] − 1 and 0 ≤ j [y] ≤ n [y] − 1, the NUDFT reduces to the discrete Fourier transform (DFT) . Consequently, the NUDFT matrix A has a Kronecker product structure A = A [x] ⊗ A [y], where A[x](j[x], k [x]) = e −2πk[x]j [x]/n [x] and A[y](j[y], k [y]) = e −2πik[y]j [y]/n [y] are the DFT matrices in the x and y directions, respectively. In this case, the forward NUDFT can be efficiently computed by the fast F

FAQs

What problem does the paper solve?

The paper solves the inverse 2D type-II nonuniform discrete Fourier transform (NUDFT), formulated as a linear least-squares problem for recovering coefficients from target samples.

How is the NUDFT matrix factored in the proposed method?

The NUDFT matrix A is factored as A = G F, where F is the 2D DFT matrix and G is expressed via a kernel matrix that is approximated using a hierarchically semiseparable (HSS) structure.

Why can the method be useful for iterative solvers?

After building a direct solver, the approach can act as a preconditioner, especially when sample points are distributed so the system becomes ill-conditioned, improving efficiency and robustness of iterative methods.

Jul 16, 2026

Upload by Anda