Superfast direct inversion of the nonuniform discrete Fourier transform via hierarchically semi-separable least squares

Understand

A direct solver is introduced for solving overdetermined linear systems involving nonuniform discrete Fourier transform matrices.

• Such matrices can be transformed into a Cauchy-like form that has hierarchical low rank structure.
• The rank structure of this matrix is explained, and it is shown that the ranks of the relevant submatrices grow only logarithmically with the number of columns of the matrix.
• A fast rank-structured hierarchical approximation method based on this analysis is developed, along with a hierarchical least-squares solver for these and related systems.