Smallest eigenvalue of a tricky random matrix

2010-11-13T22:06:05Z

While experimenting with positive-definite functions, I was led to the following:

Let $n$ be a positive integer, and let $x_1,\ldots,x_n$ be sampled from a zero-mean, unit variance gaussian. Consider the (positive-definite) matrix $$M_{ij}=\frac{1}{1+|x_i-x_j|}.$$ Now I wish to know:

How do I obtain an estimate for the smallest eigenvalue $\lambda_n$ of $M$?

Preliminary experiments (see plot; x-axis: $n$, y-axis: $\lambda_n$) suggest that $\lambda_n \approx 1/n^2$, but how do I prove that or perhaps a more accurate result?

Answer by Terry Tao for Smallest eigenvalue of a tricky random matrix

2010-11-14T21:12:08Z

I think I can get an upper bound of $O(1/n^2)$ by exhibiting a vector $v$ of magnitude comparable to $1$ which gets mapped to a vector of magnitude $O(1/n^2)$. The basic idea is to exploit the birthday paradox to find (with high probability) two indices $i \neq i'$ such that $x_i-x_{i'} = O(1/n^2)$. It should also be possible to then find another additional index $i''$ such that $x_{i''} = x_i + O(1/n)$.

Now look at the $i^{th}$ and $(i')^{th}$ rows, which have components $1/(1+|x_i-x_j|)$ and $1/(1+|x_{i'}-x_j|)$. These rows differ by $O(n^{-2})$ in each coefficient. This already gives an upper bound of $O(n^{-3/2})$ for the smallest eigenvalue, but one can do better by using Taylor expansion to note that the difference between the two components is $(x_i-x_{i'}) \hbox{sgn}( x_i-x_j ) / (1 + |x_i-x_j|)^2 + O(n^{-4})$ except when $x_j$ is very close to $x_i$, at which point we only have the crude bound of $O(n^{-2})$. Similarly, the difference between the $i''$ and $i$ rows is something like $(x_i-x_{i''}) \hbox{sgn}( x_i-x_j ) / (1 + |x_i-x_j|)^2 + O(n^{-4})$ except when $x_j$ is too close to $x_i$. So we can use a multiple of the second difference to mostly cancel off the first difference, and end up with a linear combination of three rows in which most entries have size $O(n^{-4})$ and only about $O(1)$ entries have size $O(n^{-2})$. This seems to give an upper bound of $O(n^{-2})$ for the least eigenvalue (or least singular value), though I have not fully checked the details.

To get a matching lower bound is trickier. One may have to move to a Fourier representation of the matrix as this would more readily capture the positive definiteness of the matrix (as suggested by Bochner's theorem).

Smallest eigenvalue of a tricky random matrix - MathOverflow

Smallest eigenvalue of a tricky random matrix

Answer by Terry Tao for Smallest eigenvalue of a tricky random matrix