Abstract:  Vandermonde matrices arise in many fields of applied mathematics and engineering, e.g., subspace methods---such as MUSIC and ESPRIT---for the estimation of cisoid parameters, super-resolution, line spectral estimation, compressed sensing, interpolation and approximation theory, sampling theory, differential equations, and control theory. In this talk, we establish a systematic connection between Vandermonde matrices and the large sieve, a set of inequalities developed in analytic number theory by Linnik, Rényi, Roth, and Bombieri. Based on this relationship, we present new bounds on the extremal singular values and the condition number of Vandermonde matrices with nodes in the unit disk. We then build on these bounds to develop a deterministic, finite-SNR, finite sample-size performance analysis of MUSIC, ESPRIT, and the matrix pencil method. These results demonstrate that polynomial root finding (e.g., Berlekamp-Massey and Peterson-Gorenstein-Zierler) algorithms over the reals as used widely in the sparse signal recovery literature do not exhibit an intrinsic lack of numerical stability.