Spectra reveal cluster structure key to high-dimensional super-resolution
Spectra of Multivariate Vandermonde Matrices and Min-max Error Bounds for the High-dimensional Super-resolution Problem
Information Theory
Summary
Super-resolution means finding very close points from blurry, noisy signals. The authors study mathematical structures called multivariate Vandermonde matrices that arise when signals come from points grouped in clusters. They show that clusters are almost independent in a certain sense when the number of measurements grows, which simplifies analysis. This leads to precise error bounds for recovering clustered points even in many dimensions, sometimes better than in one dimension.
What this means in practice
- •For signal processing engineers: Improve algorithms for recovering clustered high-dimensional signals from noisy low-frequency data using new error bounds and spectral insights.
- •For medical imaging developers: Enhance stability in reconstructing closely spaced sources in high-dimensional imaging modalities like MRI or CT scans by applying insights on clustered point recovery.
A theory result. No direct application yet.
Authors
Nuha Diab, Dmitry Batenkov
Abstract
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 \rightarrow \infty, Nh \ll 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.