The spectral properties of Vandermonde matrices with clustered nodes

Abstract

We study rectangular Vandermonde matrices $\mathbf{V}$ with $N+1$ rows and $s$ irregularly spaced nodes on the unit circle, in cases where some of the nodes are "clustered" together -- the elements inside each cluster being separated by at most $h\lesssim \frac{1}{N}$, and the clusters being separated from each other by at least $\theta \gtrsim \frac{1}{N}$. We show that any pair of column subspaces corresponding to two different clusters are nearly orthogonal: the minimal principal angle between them is at most $$\frac{\pi }{2}-\frac{c_1}{N\theta }-c_{2}Nh,$$ for some constants $c_1,c_2$ depending only on the multiplicities of theclusters. As a result, spectral analysis of ${\mathbf{V}}_N$ is significantly simplified by reducing the problem to the analysis of each cluster individually. Consequently we derive accurate estimates for 1) all the singular values of $\mathbf{V}$, and 2) componentwise condition numbers for the linear least squares problem. Importantly, these estimates are exponential only in the local cluster multiplicities, while changing at most linearly with $s$.