Random Vandermonde Matrices-Part I: Fundamental results

In this first part, analytical methods for finding moments of random Vandermonde matrices are developed. Vandermonde Matrices play an important role in signal processing and communication applications such as direction of arrival estimation, precoding or sparse sampling theory for example. Within this framework, we extend classical freeness results on random matrices with i.i.d entries and show that Vandermonde structured matrices can be treated in the same vein with different tools. We focus on various types of Vandermonde matrices, namely Vandermonde matrices with or without uniformly distributed phases, as well as generalized Vandermonde matrices (with non-uniform distribution of powers). In each case, we provide explicit expressions of the moments of the associated Gram matrix, as well as more advanced models involving the Vandermonde matrix. Comparisons with classical i.i.d. random matrix theory are provided and free deconvolution results are also discussed.