pith. sign in

arxiv: 2604.15135 · v3 · submitted 2026-04-16 · 🧮 math.NA · cs.NA

On the exponential rate of the condition number of Fourier submatrices and Vandermonde matrices

Rikhav Shah , John Urschel This is my paper

Pith reviewed 2026-05-10 10:13 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords Fourier submatricesVandermonde matricescondition numbersexponential ill-conditioninglogarithmic potentialsCatalan's constantnumerical stability
0
0 comments X

The pith

Square submatrices of the discrete Fourier transform with contiguous rows and columns have an exactly determined exponential ill-conditioning rate, which yields a tight upper bound of 2G/π for all contiguous-column cases and Vandermonde sub

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines the precise exponential rate at which condition numbers grow for square submatrices of the discrete Fourier transform when rows and columns are taken contiguously. This matters because such submatrices arise in many numerical applications, where their ill-conditioning limits computational accuracy. Using a general analysis of Vandermonde and Vandermonde-like matrices via logarithmic potentials, the work also proves that the exponential rate is bounded above by 2G/π, with G Catalan's constant, for every submatrix with contiguous columns or every Vandermonde matrix on distinct points. The bound is shown to be tight. These explicit rates let practitioners predict when such matrices remain usable in floating-point arithmetic.

Core claim

By developing exact estimates for the exponential ill-conditioning of Vandermonde and Vandermonde-like matrices in terms of logarithmic potentials, the paper resolves the precise rate for square Fourier submatrices with contiguous rows and columns, and establishes that 2G/π is a tight upper bound on the rate for all submatrices with contiguous columns or Vandermonde matrices with distinct support points.

What carries the argument

Logarithmic potential analysis of Vandermonde and Vandermonde-like matrices, which supplies exact estimates for the exponential growth of their condition numbers.

If this is right

  • The exact exponential rate is now known for every contiguous square Fourier submatrix.
  • Every contiguous-column Fourier submatrix and every Vandermonde submatrix on distinct points has exponential conditioning rate at most 2G/π.
  • The bound 2G/π is tight, so the worst-case rate is achieved or approached for some choices of columns.
  • Applications that rely on these submatrices can use the known rate to forecast numerical stability limits more precisely.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same potential-theoretic approach could be applied to other structured matrices such as Toeplitz or Hankel forms to obtain their conditioning rates.
  • Large-scale numerical tests that plot log(condition number) versus size would directly verify the predicted rates.
  • Selecting non-contiguous rows may allow avoidance of the worst exponential growth when working with Fourier data.
  • The appearance of Catalan's constant hints at possible deeper connections to other analytic problems involving that constant.

Load-bearing premise

That logarithmic potentials accurately capture the exponential ill-conditioning for the stated classes of submatrices without extra unstated restrictions on dimensions or point distributions.

What would settle it

Numerical computation of condition numbers for a sequence of large contiguous square Fourier submatrices, checking whether log(kappa(A_n))/n converges to the rate predicted by the potential analysis or exceeds 2G/π for some contiguous-column Vandermonde example.

Figures

Figures reproduced from arXiv: 2604.15135 by John Urschel, Rikhav Shah.

Figure 1
Figure 1. Figure 1: A comparison of our and Barnett’s theoretical results to computed condi￾tion numbers for N = 512. Figure (A) contains the computed value of 1 N log κ(FS,T ) for contiguous S, T with α = |S| N and β = |T| N . Barnett’s lower bound π 2 (min(α, β)−αβ) is plotted in Figure (C), and matches Figure (A) quite well away from the diagonal α = β. Figure (B) compares, for α = β, 1 N log κ(FS,T ), Barnett’s bound π 2 … view at source ↗
Figure 2
Figure 2. Figure 2: Plots of f(x) and Cl2(θ) on the interval [0, 2π]. and for x ∈ [π + ε, 2π), [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
read the original abstract

The discrete Fourier transform matrix is one of the most important matrices in linear algebra, and submatrices of it arise in a variety of applications. Though the discrete Fourier transform matrix is unitary, its submatrices can be exponentially ill-conditioned, an obstacle to accurate computation. This work resolves the exact rate of the exponential ill-conditioning for square submatrices with contiguous rows and columns. As a consequence, we obtain a tight upper bound of $2 G/\pi$ on the exponential rate for all submatrices with contiguous columns, or, equivalently, all Vandermonde submatrices with distinct support points, where $G$ is Catalan's constant. These results follow from a more general analysis of Vandermonde and Vandermonde-like matrices for which exact estimates for exponential ill-conditioning are developed in terms of logarithmic potentials.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript resolves the exact exponential rate of ill-conditioning for square submatrices of the DFT matrix with contiguous rows and columns. Using logarithmic potential theory, it derives a tight upper bound of 2G/π (G Catalan's constant) on the rate for all submatrices with contiguous columns, equivalently for Vandermonde matrices with distinct nodes. This follows from a general analysis providing exact estimates for exponential ill-conditioning of Vandermonde and Vandermonde-like matrices in terms of logarithmic potentials.

Significance. If the derivations hold, the work supplies precise, closed-form characterizations of exponential ill-conditioning for structured matrices central to numerical linear algebra and approximation theory. The appearance of Catalan's constant as a sharp bound and the parameter-free nature of the potential-theoretic estimates are notable strengths. The results extend prior understanding by handling contiguous-row-and-column cases exactly and providing a uniform bound for the contiguous-column/Vandermonde setting without additional restrictions on dimension or node distribution.

minor comments (2)
  1. In the general Vandermonde analysis, the transition from the logarithmic potential to the precise exponential rate (likely in the main theorem) would benefit from an explicit statement of the error term or remainder estimate to make the 'exact' claim fully transparent.
  2. Notation for the submatrix indices (contiguous rows/columns) and the support points could be standardized earlier to avoid minor ambiguity when moving between the DFT and Vandermonde settings.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We are grateful to the referee for the positive and accurate summary of our manuscript, as well as for the encouraging assessment of its significance. We note the recommendation for minor revision. As the report lists no specific major comments, we have no point-by-point responses to provide.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives exact exponential rates for the condition numbers of contiguous Fourier submatrices and a tight bound of 2G/π for contiguous-column (Vandermonde) cases by applying standard logarithmic potential theory to the underlying measures. This is an external analytic framework from approximation theory, not a self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation chain. The results are obtained by evaluating potentials on the specific supports (contiguous intervals or DFT frequencies) without reducing the target quantities to the inputs by construction. No uniqueness theorems or ansatzes are imported from the authors' prior work in a manner that forces the conclusion.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard results from complex analysis and potential theory together with the known unitarity of the full DFT matrix; no free parameters, ad-hoc constants, or new postulated entities are introduced in the abstract.

axioms (2)
  • standard math The discrete Fourier transform matrix is unitary
    Background fact used to contrast the conditioning of the full matrix with that of its submatrices.
  • standard math Logarithmic potentials yield exact asymptotic estimates for the condition numbers of Vandermonde and Vandermonde-like matrices
    Central tool invoked for the general analysis that produces the exact rates and the 2G/π bound.

pith-pipeline@v0.9.0 · 5440 in / 1438 out tokens · 53682 ms · 2026-05-10T10:13:29.239803+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages

  1. [1]

    On the numerical stability of Fourier extensions.Foun- dations of Computational Mathematics, 14(4):635–687, 2014

    Ben Adcock, Daan Huybrechs, and Jes´ us Mart´ ın-Vaquero. On the numerical stability of Fourier extensions.Foun- dations of Computational Mathematics, 14(4):635–687, 2014

    work page 2014

  2. [2]

    A spectral FC solver for the compressible Navier–Stokes equations in general domains i: Explicit time-stepping.Journal of Computational Physics, 230(16):6248–6270, 2011

    Nathan Albin and Oscar P Bruno. A spectral FC solver for the compressible Navier–Stokes equations in general domains i: Explicit time-stepping.Journal of Computational Physics, 230(16):6248–6270, 2011

    work page 2011

  3. [3]

    Vandermonde matrices with nodes in the unit disk and the large sieve.Applied and Computational Harmonic Analysis, 47(1):53–86, 2019

    C´ eline Aubel and Helmut B¨ olcskei. Vandermonde matrices with nodes in the unit disk and the large sieve.Applied and Computational Harmonic Analysis, 47(1):53–86, 2019

    work page 2019

  4. [4]

    How exponentially ill-conditioned are contiguous submatrices of the Fourier matrix?Siam Review, 64(1):105–131, 2022

    Alex H Barnett. How exponentially ill-conditioned are contiguous submatrices of the Fourier matrix?Siam Review, 64(1):105–131, 2022

    work page 2022

  5. [5]

    Conditioning of partial nonuniform Fourier matrices with clustered nodes.SIAM Journal on Matrix Analysis and Applications, 41(1):199–220, 2020

    Dmitry Batenkov, Laurent Demanet, Gil Goldman, and Yosef Yomdin. Conditioning of partial nonuniform Fourier matrices with clustered nodes.SIAM Journal on Matrix Analysis and Applications, 41(1):199–220, 2020

    work page 2020

  6. [6]

    Conditioning of rectangular Vandermonde matrices with nodes in the unit disk.SIAM Journal on Matrix Analysis and Applications, 21(2):679–693, 2000

    Ferm´ ın SV Baz´ an. Conditioning of rectangular Vandermonde matrices with nodes in the unit disk.SIAM Journal on Matrix Analysis and Applications, 21(2):679–693, 2000

    work page 2000

  7. [7]

    Fourier phase retrieval: Uniqueness and algorithms

    Tamir Bendory, Robert Beinert, and Yonina C Eldar. Fourier phase retrieval: Uniqueness and algorithms. InCom- pressed Sensing and its Applications: Second International MATHEON Conference 2015, pages 55–91. Springer, 2018

    work page 2015

  8. [8]

    A comparison of numerical algorithms for Fourier extension of the first, second, and third kinds

    John P Boyd. A comparison of numerical algorithms for Fourier extension of the first, second, and third kinds. Journal of Computational Physics, 178(1):118–160, 2002

    work page 2002

  9. [9]

    Vandermonde with Arnoldi.Siam Review, 63(2):405– 415, 2021

    Pablo D Brubeck, Yuji Nakatsukasa, and Lloyd N Trefethen. Vandermonde with Arnoldi.Siam Review, 63(2):405– 415, 2021

    work page 2021

  10. [10]

    Towards a mathematical theory of super-resolution.Commu- nications on pure and applied Mathematics, 67(6):906–956, 2014

    Emmanuel J Cand` es and Carlos Fernandez-Granda. Towards a mathematical theory of super-resolution.Commu- nications on pure and applied Mathematics, 67(6):906–956, 2014

    work page 2014

  11. [11]

    Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information.IEEE Transactions on information theory, 52(2):489–509, 2006

    Emmanuel J Cand` es, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information.IEEE Transactions on information theory, 52(2):489–509, 2006

    work page 2006

  12. [12]

    Channel estimation techniques based on pilot arrange- ment in OFDM systems.IEEE Transactions on broadcasting, 48(3):223–229, 2002

    Sinem Coleri, Mustafa Ergen, Anuj Puri, and Ahmad Bahai. Channel estimation techniques based on pilot arrange- ment in OFDM systems.IEEE Transactions on broadcasting, 48(3):223–229, 2002

    work page 2002

  13. [13]

    The recoverability limit for superreso- lution via sparsity,

    Laurent Demanet and Nam Nguyen. The recoverability limit for superresolution via sparsity.arXiv preprint arXiv:1502.01385, 2015

    work page arXiv 2015

  14. [14]

    Superresolution via sparsity constraints.SIAM journal on mathematical analysis, 23(5):1309–1331, 1992

    David L Donoho. Superresolution via sparsity constraints.SIAM journal on mathematical analysis, 23(5):1309–1331, 1992

    work page 1992

  15. [15]

    The future fast Fourier transform?SIAM Journal on Scientific Computing, 20(3):1094–1114, 1998

    Alan Edelman, Peter McCorquodale, and Sivan Toledo. The future fast Fourier transform?SIAM Journal on Scientific Computing, 20(3):1094–1114, 1998

    work page 1998

  16. [16]

    Analysis of DFT-based channel estimators for OFDM.Wireless Personal Communications, 12(1):55–70, 2000

    Ove Edfors, Magnus Sandell, Jan-Jaap Van De Beek, Sarah Kate Wilson, and Per Ola B¨ orjesson. Analysis of DFT-based channel estimators for OFDM.Wireless Personal Communications, 12(1):55–70, 2000

    work page 2000

  17. [17]

    Super-resolution, the recovery of missing samples and Vandermonde matrices on the unit circle

    PJSG Ferreira. Super-resolution, the recovery of missing samples and Vandermonde matrices on the unit circle. In Proceedings of the Workshop on Sampling Theory and Applications, Loen, Norway, 1999

    work page 1999

  18. [18]

    On the Fourier extension of nonperiodic functions.SIAM Journal on Numerical Analysis, 47(6):4326–4355, 2010

    Daan Huybrechs. On the Fourier extension of nonperiodic functions.SIAM Journal on Numerical Analysis, 47(6):4326–4355, 2010

    work page 2010

  19. [19]

    On the smallest singular value of multivariate Vandermonde matrices with clus- tered nodes.Linear Algebra and its Applications, 604:1–20, 2020

    Stefan Kunis and Dominik Nagel. On the smallest singular value of multivariate Vandermonde matrices with clus- tered nodes.Linear Algebra and its Applications, 604:1–20, 2020

    work page 2020

  20. [20]

    On the condition number of Vandermonde matrices with pairs of nearly-colliding nodes.Numerical Algorithms, 87(1):473–496, 2021

    Stefan Kunis and Dominik Nagel. On the condition number of Vandermonde matrices with pairs of nearly-colliding nodes.Numerical Algorithms, 87(1):473–496, 2021

    work page 2021

  21. [21]

    Multiscale estimates for the condition number of non-harmonic Fourier matrices.Mathematics of Com- putation, 94(356):2895–2929, 2025

    Weilin Li. Multiscale estimates for the condition number of non-harmonic Fourier matrices.Mathematics of Com- putation, 94(356):2895–2929, 2025

    work page 2025

  22. [22]

    Stable super-resolution limit and smallest singular value of restricted Fourier matrices

    Weilin Li and Wenjing Liao. Stable super-resolution limit and smallest singular value of restricted Fourier matrices. Applied and Computational Harmonic Analysis, 51:118–156, 2021

    work page 2021

  23. [23]

    Michael Lustig, David Donoho, and John M Pauly. Sparse MRI: The application of compressed sensing for rapid MR imaging.Magnetic Resonance in Medicine: An Official Journal of the International Society for Magnetic Resonance in Medicine, 58(6):1182–1195, 2007

    work page 2007

  24. [24]

    Fast algorithms for the computation of Fourier extensions of arbitrary length

    Roel Matthysen and Daan Huybrechs. Fast algorithms for the computation of Fourier extensions of arbitrary length. SIAM Journal on Scientific Computing, 38(2):A899–A922, 2016

    work page 2016

  25. [25]

    Beyond crystallography: Diffractive imaging using coherent x-ray light sources.Science, 348(6234):530–535, 2015

    Jianwei Miao, Tetsuya Ishikawa, Ian K Robinson, and Margaret M Murnane. Beyond crystallography: Diffractive imaging using coherent x-ray light sources.Science, 348(6234):530–535, 2015

    work page 2015

  26. [26]

    Super-resolution, extremal functions and the condition number of Vandermonde matrices

    Ankur Moitra. Super-resolution, extremal functions and the condition number of Vandermonde matrices. InPro- ceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 821–830, 2015

    work page 2015

  27. [27]

    How bad are Vandermonde matrices?SIAM Journal on Matrix Analysis and Applications, 37(2):676– 694, 2016

    Victor Y Pan. How bad are Vandermonde matrices?SIAM Journal on Matrix Analysis and Applications, 37(2):676– 694, 2016. CONDITION NUMBER OF FOURIER SUBMATRICES 27

    work page 2016

  28. [28]

    Frame-theoretic analysis of DFT codes with erasures.IEEE Transactions on Signal Processing, 52(2):447–460, 2004

    Gagan Rath and Christine Guillemot. Frame-theoretic analysis of DFT codes with erasures.IEEE Transactions on Signal Processing, 52(2):447–460, 2004

    work page 2004

  29. [29]

    Recent advances in DFT codes based quantized frame expansions for erasure channels.Digital Signal Processing, 14(4):332–354, 2004

    Gagan Rath and Christine Guillemot. Recent advances in DFT codes based quantized frame expansions for erasure channels.Digital Signal Processing, 14(4):332–354, 2004

    work page 2004

  30. [30]

    Springer, 1997

    Edward B Saff, Vilmos Totik, et al.Logarithmic potentials with external fields, volume 316. Springer, 1997

    work page 1997

  31. [31]

    Deconstructing multiantenna fading channels.IEEE Transactions on Signal processing, 50(10):2563–2579, 2002

    Akbar M Sayeed. Deconstructing multiantenna fading channels.IEEE Transactions on Signal processing, 50(10):2563–2579, 2002

    work page 2002

  32. [32]

    SIAM, 2000

    Lloyd N Trefethen.Spectral methods in MATLAB. SIAM, 2000

    work page 2000

  33. [33]

    Die bestimmung der dichtigkeit einer menge von primzahlen, welche zu einer gegebenen substitutionsklasse geh¨ oren.Mathematische Annalen, 95(1):191–228, 1926

    Nikolaj Tschebotareff. Die bestimmung der dichtigkeit einer menge von primzahlen, welche zu einer gegebenen substitutionsklasse geh¨ oren.Mathematische Annalen, 95(1):191–228, 1926

    work page 1926

  34. [34]

    Bichai Wang, Linglong Dai, Zhaocheng Wang, Ning Ge, and Shidong Zhou. Spectrum and energy-efficient beamspace MIMO-NOMA for millimeter-wave communications using lens antenna array.IEEE Journal on Selected Areas in Communications, 35(10):2370–2382, 2017

    work page 2017

  35. [35]

    Heather Wilber, Ethan N Epperly, and Alex H Barnett. Superfast direct inversion of the nonuniform discrete Fourier transform via hierarchically semiseparable least squares.SIAM Journal on Scientific Computing, 47(3):A1702– A1732, 2025

    work page 2025

  36. [36]

    The eigenvalue distribu- tion of discrete periodic time-frequency limiting operators.IEEE Signal Processing Letters, 25(1):95–99, 2017

    Zhihui Zhu, Santhosh Karnik, Mark A Davenport, Justin Romberg, and Michael B Wakin. The eigenvalue distribu- tion of discrete periodic time-frequency limiting operators.IEEE Signal Processing Letters, 25(1):95–99, 2017

    work page 2017