19
$\begingroup$

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?

enter image description here

$\endgroup$
4
  • $\begingroup$ Do you mean $M_{ij}=\frac{1}{1+|x_i-x_j|}$? Because $M$ as you've defined doesn't seem to be a matrix. $\endgroup$
    – Gilead
    Nov 13, 2010 at 23:00
  • 1
    $\begingroup$ Here's a link: mathoverflow.net/questions/24287/… $\endgroup$
    – Gilead
    Nov 13, 2010 at 23:02
  • $\begingroup$ @Gilead: Thanks for catching the typo; also, i am not looking for a numerical method, but rather a "closed-form" bound or approximation. $\endgroup$
    – Suvrit
    Nov 14, 2010 at 9:09
  • $\begingroup$ I have a similar question, could someone help me? mathoverflow.net/questions/366339/… $\endgroup$ Jul 23, 2020 at 9:11

1 Answer 1

19
$\begingroup$

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).

$\endgroup$
2
  • 13
    $\begingroup$ It's even easier than that: once you've found a pair of indices giving distance order $1/n^2$, they define a $2 \times 2$ matrix with an eigenvalue of order $1/n^2$, and then by interlacing of eigenvalues for Hermitian (or real symmetric) matrices the entire matrix has an eigenvalue no larger than that. $\endgroup$
    – Tracy Hall
    Nov 15, 2010 at 4:32
  • $\begingroup$ @Terry: thanks for the nice argument for an upper bound (and @Tracy, good point of invoking Cauchy's interlacing theorem to argue about the upper bound on the eigenvalues). As for the Fourier connection, indeed this matrix is generated by the posdef function $f(x)=1/(1+|x|)$. In fact, perhaps even more can be proved, because actually the said matrix is infinitely divisible. $\endgroup$
    – Suvrit
    Nov 16, 2010 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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