5
$\begingroup$

Hello,

I'm interested in the distribution of the trace of an inverse-Wishart matrix $W_n^{-1}(I,n)$, where $I$ is $n\times n$ identity matrix. More precisely, I seek for an asymptotic estimate (when $n\to\infty$) for a function $f(n)$ such that $Pr[Tr(W)< f(n)]>2/3$, say.

What I've learned so far:

  1. I know the pdf of the eigenvalues of $W$, thus, I could use it to find the bound, but it could be tedious.

  2. A formula for the expectation of $W_n^{-1}(I,m)$ is known, but it does not work for $n=m$ (the expectation is infinite in this case).

This question seems pretty basic, so I expect it should have been considered before, but my google search hasn't revealed any reference on it so far. Could you help me with any?

Thank you,

Alexander.

Improve this question
$\endgroup$
3
  • $\begingroup$ I'm not familiar with your notation. Do you mean $W_n(I,n) = G_n G_n^T = G_nIG_n^T$, where $G_n$ is an $n\times n$ matrix with i.i.d. standard normal entries (or maybe some different normalization)? $\endgroup$
    – Mark Meckes
    Commented Feb 16, 2011 at 14:10
  • $\begingroup$ Yes, Mark, you are right. I mean exactly this matrix. $\endgroup$
    – Alexander Belov
    Commented Feb 16, 2011 at 15:14
  • $\begingroup$ More precisely, I denote by $W$ the inverse of a matrix from $W_n(I,n)$. $\endgroup$
    – Alexander Belov
    Commented Feb 16, 2011 at 15:21

3 Answers 3

Reset to default
2
$\begingroup$

Assuming I'm interpreting your notation correctly, with high probability it is known that $\lambda_{\min}(W_n) \ge c/n$ for some absolute constant $c$ (see Edelman, "Eigenvalues and condition numbers of random matrices", or this paper by Rudelson and Vershynin for a quick summary of some more general results.

From this it follows that $Tr(W_n^{-1}) = \sum_{i=1}^n \lambda_i(W_n)^{-1} \le n^2/c$ with high probability. Probably the $n^2$ can be improved somewhat. See Szarek, "Condition numbers of random matrices" for estimates on nonextreme eigenvalues which may be good enough to do better here.

Added: here's a heuristic to get an $O(n)$ bound, which as the OP notes in his answer, is best possible. Putting the eigenvalues of $W_n$ in increasing order, we have typically $\lambda_k(W_n) \approx \frac{k^2}{n}$, from which it follows that $$ Tr(W_n^{-1}) \lesssim \sum_{k=1}^n \frac{n}{k^2} \le n \sum_{k=1}^\infty \frac{1}{k^2} = C n. $$ I haven't checked the details, but the results in the paper of Szarek mentioned above are probably strong enough to make this rigorous.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I see from a comment of yours that you're already familiar with Edelman's thesis, so probably this answer doesn't tell you anything you don't already know. $\endgroup$
    – Mark Meckes
    Commented Feb 16, 2011 at 15:28
  • $\begingroup$ Thank you, Mark. You are right, I was aware of $O(n^2)$ estimate. I should have stated that concisely in my question, my fault. My aim is to improve it down to $O(n)$ in a less painful way. Now, I think I've done it. See my answer. $\endgroup$
    – Alexander Belov
    Commented Feb 17, 2011 at 10:27
  • $\begingroup$ Can you provide some more detail? Which results of Szarek should I look at to formalize this O(n) bound? $\endgroup$
    – Thomas Steinke
    Commented May 13, 2022 at 17:06
  • $\begingroup$ OK. I think I figured it out. Theorem 1.2 in Szarek "Condition numbers of random matrices" 1991: sciencedirect.com/science/article/pii/0885064X9190002F This gives $$\mathbb{P}[\mathrm{trace}(W_n^{-1}) \le O(n/\alpha^2) ] \ge 1-\alpha$$ for all $\alpha \in (0,0.9]$. $\endgroup$
    – Thomas Steinke
    Commented May 13, 2022 at 17:23
1
$\begingroup$

I guess, I've done it.

My idea is to detach two eigenvalues, use the smallest eigenvalue estimation for them and then apply the known result for the expectation of the rest of the matrix.

Let $G$ be $n\times n$ matrix with entries being pairwise independent standard Gaussians. Then let $W=G^TG$ and I am interested in $Tr(W^{-1})$. I use that mine multivariate Gaussian distributions are invariant under application of (real) orthogonal matrices. Thus, the distribution does not change if I assume that $e_1$ and $e_2$ (elements of the standard basis) are eigenvectors of $W$. This means, merely, that first two columns of $G$ are orthogonal to all other columns and orthogonal to each another. Again, as orthogonal transformations does not change the distribution on $G$, this assumption does not change the distribution on the rest of the columns of $G$. Let $\lambda_1$ and $\lambda_2$ be the eigenvalues of $e_1$ and $e_2$, respectively, and let $W'$ be $W$ with first two rows and columns removed. Then $Tr(W^{-1}) = 1/\lambda_1 + 1/\lambda_2 + Tr(W'^{-1})$. I can use the estimation on the smallest eigenvalue of $W$ to bound the first two terms. Now note that $W'$ is, in fact, $W_{n-2}(I,n)$, and it is known that expectation of $W'^{-1}$ is $I$. Hence, the expectation of the trace is $n-2$. Using Markov for the third term, I get that, with high enough probability, $Tr(W^{-1})$ is $O(n)$. This cannot be improved because of the smallest eigenvalue.

I hope that's correct.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think that looks good. The dimension reduction trick is nice. I'm adding to my answer a heuristic for another proof. $\endgroup$
    – Mark Meckes
    Commented Feb 17, 2011 at 16:46
  • $\begingroup$ I am very skeptical now about the legitimacy of my orthogonal transformations, but the same idea goes through nicely if one uses the Bartlett decomposition for $W$ and the block decomposition to calculate $W^{-1}$. $\endgroup$
    – Alexander Belov
    Commented Feb 22, 2011 at 14:51
  • $\begingroup$ I have the exact same question and found this answer via Google. This answer does give good intuition, but it isn't quite a proof. The columns of G will be nearly orthogonal, but not exactly orthogonal, so the claim that we can assume the standard basis vectors are eigenvectors is not quite true. Do you think this can be fleshed out into a formal proof somehow? $\endgroup$
    – Thomas Steinke
    Commented May 13, 2022 at 16:22
0
$\begingroup$

You have $W_n(I,n)= XX^{T}$ where $X$ is $n \times n$ with the rows of $X$ iid from $N(0,I_{n})$, so then it seems to me that as $n \rightarrow \infty$, $W_{n} \rightarrow nI_{n}$ almost surely? This is because $X$ is almost surely an orthogonal matrix, and the entries along the trace will converge to their expectation by the strong law for iid RVs which is $E[\chi^{2}_{n}] = n$ by construction.

Edit: As noted below this answer is incorrect, but possibly the discussion below is interesting so I'll keep this post up until it starts getting downvoted.

Improve this answer
$\endgroup$
8
  • $\begingroup$ $X$ is almost surely not orthogonal. The limiting spectral distribution of $\frac{1}{n}W_n$ is known (it's called the Marchenko-Pastur distribution), and it is quite different from the spectral distribution of the identity matrix. $\endgroup$
    – Mark Meckes
    Commented Feb 16, 2011 at 15:13
  • $\begingroup$ Well, I guess you are not right. E.g., almost surely, the smallest eigenvalue of $XX^T$ will be of order $1/n$ (see, for example, the PhD thesis of Alan Edelman). Thank you for the answer, anyway! $\endgroup$
    – Alexander Belov
    Commented Feb 16, 2011 at 15:19
  • $\begingroup$ @Mark Okay, I'm confused. The rows of X are iid zero-mean random vectors so for $i \neq j$, $E[x_{i}^{T}x_{j}] = E[\sum_{k=1}^{n}x_{ik}x_{jk}] = \sum_{k}^{n}E[x_{ik}]E[x_{jk}] = 0$. On the other hand $E[x_{i}^{T}x_{i}] = n \times Var(x_{ik}) = n$. Then the strong law for iid variables says that as $n \rightarrow \infty$, $\frac{1}{n} \sum_{k=1}^{d} x_{ik}x_{jk} \rightarrow E[x_{ik}x_{jk}]$. Okay, $X$ isn't orthogonal quite as the rows weren't normalised, but it seems its rows should be orthogonal to each other a.s. Where's the bug? $\endgroup$
    – Bob Durrant
    Commented Feb 16, 2011 at 17:59
  • $\begingroup$ Sorry - should be k=1 to n in the last summation, not d. $\endgroup$
    – Bob Durrant
    Commented Feb 16, 2011 at 18:02
  • $\begingroup$ First of all, I guess you meant "asymptotically almost surely" and not "almost surely". What you have is an argument that for fixed $i$ and $j$, the $i$th and $j$th rows are a.a.s. orthogonal. But the question here depends on the relationships among *all* the rows. Here's a related point to consider: for fixed $n$, given the first $n-1$ rows of an orthogonal matrix, you know precisely what the last row is up to sign. But the $n$th row of $X$ is independent of its first $n-1$ rows. $\endgroup$
    – Mark Meckes
    Commented Feb 16, 2011 at 18:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .