Spectra of Multivariate Vandermonde Matrices and Min-max Error Bounds for the High-dimensional Super-resolution Problem
Abstract
We study multivariate rectangular Vandermonde matrices UN whose rows are indexed by the grid $G_N=\{-N,\ldots,N\}^d, $ and whose columns correspond to irregularly spaced points on the unit d-dimensional torus. Motivated by the problem of super-resolution (recovery of spike trains from low frequency noisy measurements), we consider configurations in which the points form several clusters, with points within each cluster separated by at most h and distinct clusters are well-separated. We show that the column subspaces associated with different clusters are nearly orthogonal, i.e. for N → ∞, Nh ≪ 1, the minimal principal angle between any such pair is at least $ {π\over 2} - \frac{C_1}{N} - C_2Nh - \frac{C_3}{\sqrt{N}}, $ for some constants C1,C2,C3 independent of N and h. This near-orthogonality enables the spectral analysis of such UN to be reduced to the analysis of each individual cluster. As a consequence, we derive sharp scaling for all singular values of UN, revealing how the geometry of clustered points controls the conditioning of the high-dimensional super-resolution problems. Then we establish min-max error bounds for the recovery of clustered point sources, requiring only an upper bound on the largest cluster size and no knowledge of the geometry within the clusters. These bounds coincide with the optimal rates known in the one-dimensional setting. Furthermore, when the clustered points are in generic position (i.e. do not lie on a low-dimensional algebraic variety) our results indicate that super-resolution in high dimensions is more stable than in one dimension.
Related
- Multi-Index Recovery for Total-Degree Multivariate Vandermonde Matrices
- From Inverse Vandermonde Matrices to the Shift Structure of the Dirichlet Eta and Beta Functions
- Matrix equivalence to Smith normal form: new theoretical results for multivariate polynomial matrices
- Spectra of Random Polynomial Matrices: the Petaloid Law
- Spectra of Non-Self-Adjoint Almost Mathieu Matrices and the Scottish Flag Operator
BibTeX
@misc{diab2026spectra,
title = {{Spectra of Multivariate Vandermonde Matrices and Min-max Error Bounds for the High-dimensional Super-resolution Problem}},
author = {Nuha Diab and Dmitry Batenkov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24670},
eprint = {2610.24670},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.24670},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Spectra of Multivariate Vandermonde Matrices and Min-max Error Bounds for the High-dimensional Super-resolution Problem
AU - Nuha Diab
AU - Dmitry Batenkov
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2610.24670
UR - https://arxiv.org/abs/2610.24670
AB - We study multivariate rectangular Vandermonde matrices U_N whose rows are indexed by the grid $G_N=\{-N,\ldots,N\}^d, $ and whose columns correspond to irregularly spaced points on the unit d-dimensional torus. Motivated by the problem of super-resolution (recovery of spike trains from low frequency noisy measurements), we consider configurations in which the points form several clusters, with points within each cluster separated by at most h and distinct clusters are well-separated. We show that the column subspaces associated with different clusters are nearly orthogonal, i.e. for N → ∞, Nh ≪ 1, the minimal principal angle between any such pair is at least $ {π\over 2} - \frac{C_1}{N} - C_2Nh - \frac{C_3}{\sqrt{N}}, $ for some constants C_1,C_2,C_3 independent of N and h. This near-orthogonality enables the spectral analysis of such U_N to be reduced to the analysis of each individual cluster. As a consequence, we derive sharp scaling for all singular values of U_N, revealing how the geometry of clustered points controls the conditioning of the high-dimensional super-resolution problems. Then we establish min-max error bounds for the recovery of clustered point sources, requiring only an upper bound on the largest cluster size and no knowledge of the geometry within the clusters. These bounds coincide with the optimal rates known in the one-dimensional setting. Furthermore, when the clustered points are in generic position (i.e. do not lie on a low-dimensional algebraic variety) our results indicate that super-resolution in high dimensions is more stable than in one dimension.
ER -