3
$\begingroup$

Let $(X_1, X_2, \dots, X_n)$ be i.i.d. ${\cal N}(0,1)$. We construct a random circulant matrix $M$:

$$M = \frac{1}{\sqrt n}\begin{pmatrix}X_1 &X_2 &X_3 \dots &X_n\\ X_n &X_1 & X_2 \dots &X_{n-1}\\ \vdots &\vdots &\vdots &\vdots\\X_2 &X_3 &X_4 \dots &X_1\end{pmatrix}.$$

My questions are the following:

  1. Is $M$ "almost orthonormal" in a precise probabilistic sense?

  2. Related to above, is it possible to upper-bound the largest possible dot product between any two rows of $M$ by a suitably small $\epsilon_n$?

Note that this says that $MM^T$ is close to the identity matrix $I_{n \times n}$, as we are bounding the off-diagonal entries of $MM^T$ by $\epsilon_n$, while the diagonal entries are close to $1$.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "upper-bound the largest possible dot product"? All of the $X_i$ could be equal to $10^{10^{10}}.$ You can upper bound it with high probability, but that's the best you can do. $\endgroup$ – Igor Rivin Oct 14 '17 at 0:05
  • $\begingroup$ If $D$ is the absolute value of the largest dot product, one could seek a bound of the sort $\mathbb P(D > \epsilon_n) < \epsilon_n$ for a suitable choice of $\epsilon_n \to 0$. $\endgroup$ – VSJ Oct 14 '17 at 2:25
  • 1
    $\begingroup$ Yes, that follows from Marcel's answer, using, e.g., Markoff's inequality. $\endgroup$ – Igor Rivin Oct 14 '17 at 3:24
7
$\begingroup$

The diagonal elements of $P=\frac{1}{N}MM^T$, like $$P_{11}=\frac{1}{N}\sum_{i=1}^NX_i^2,$$ satisfy $ \langle P_{11}\rangle=1$ and $ \langle P_{11}^2\rangle=1+2/N$ (variance decreases like $N^{-1}$).

On the other hand, off-diagonal elements like $$P_{12}=\frac{1}{N}\sum_{i=1}^{N}X_iX_{i+1} $$ satisfy $ \langle P_{12}\rangle=0$ and $ \langle P_{12}^2\rangle=1/N$ (variance also decreases like $N^{-1}$).

In this sense I would say $P$ is close to the identity.

$\endgroup$
3
$\begingroup$

Marcel's solution provides a good approach for understanding the marginal statistics. Here are a few supplementary comments that might give a little insight into the joint distribution.

Let $D$ be the discrete Fourier transform matrix, i.e. the $j,k$-th entry is: $$D_{j,k}=e^{-2\pi i jk/N}/\sqrt{N}$$ Consider the discrete Fourier transform of the first row of $M$, i.e. $$(G_1,...,G_N)=(1/\sqrt{N})(X_1,...,X_N)D$$ Let $G$ be a diagonal matrix with diagonal entries $G_1,...,G_N$. Then $D$ diagonalizes $M$ (see, e.g., this description), that is: $$M = D G D^{-1}$$

If we took the $X_i$ to be complex-valued Gaussian variables, then we would be essentially done at this point: since $D$ is unitary, and the Gaussian is spherically symmetric, then the $G_i$ would be i.i.d. (complex) Gaussian random variables with mean 0 and variance $1/n$. (That is, if we sampled the $G_i$ as i.i.d complex $\mathcal{N}(0,1/n)$, then $DGD^{-1}$ has the same distribution as samples from the original circulant matrix.) It follows that $$MM^*=(DGD^{-1})(DG^*D^{-1})=DGG^{-1}D^*$$ It then follows that the eigenvalues of $MM^{*}$ (or, if you prefer, the squared singular values of $M$) are distributed like $n$ i.i.d draws from a rescaled $\chi^2$ distribution with 2 degrees of freedom (which happens to simplify to an exponential distribution), where we rescale by dividing by $n$. From an eigenvalue perspective, this is a complete characterization of the "orthonormality" of $M$.

However, your $X_i$ are probably real-valued. This causes a small book-keeping headache, but doesn't really change much. In brief: since the $X_i$ are real-valued, the $G_i$ will be symmetric. We can convert our $n\times n$ complex-valued matrices into corresponding $2n \times 2n$ real-valued matrices (say, $D'$ and $G'$). Then observe that there are only $n$ of the $2n$ diagonal elements in $G$ are free, and only $n$ of the $2n$ inputs to $D'$ are non-zero (namely, the ones corresponding to the real values of the inputs in $D$). Noting that the resulting decimated matrices are still unitary, we then reduce to the previous case, except with $\chi^2/n$ distributions with only 1 degree of freedom.

$\endgroup$
  • $\begingroup$ I'm confused about one part: Marcel's answer indicates that $MM^*$ is close to identity. Thus it should have eigenvalues close to 1? But your argument says eigenvalues are iid from a chi square distribution so they aren't all close to 1. How to reconcile these? $\endgroup$ – VSJ Nov 2 '17 at 4:04
  • $\begingroup$ Ah, @VSJ , that is my mistake: I forgot to pass through the prefactor of $1/\sqrt(n)$ in the original definition of $M$. I will fix that now, at which point I think Marcel's answer is consistent with mine. $\endgroup$ – Bill Bradley Nov 3 '17 at 13:31
  • $\begingroup$ Hi Bill, I'm not sure that is a mistake. Because even then, the eigenvalues will converge to 0 and not 1. Perhaps it is the case that the matrix is tending "pointwise" to identity, but it is not tending fast enough, and therefore the eigenvalues don't converge? $\endgroup$ – VSJ Nov 3 '17 at 17:52

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.