Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider a series of random matrices $X_n\in\mathbb{R}^{n\times m}$ consisting of i.i.d. entries, each with zero mean and variance $1/m$, and let $a_n,b_n\in\mathbb{R}^{n\times1}$ be two deterministic (or random and independent on $X$) vectors, say with bounded norm.

I want to find the structure of some "nice"/"simple" "limit" function, $f_n$, of the following term $$ a_n^T\left(X_nX_n^T+I_n\right)^{-1}b_n-f_n\to0 $$ almost surely, as $n,m\to\infty$ with fixed ratio.

EDIT: Due to Ofer's answer and comments I will consider some specific choice of $a_n$: $$ \frac{1}{n}w_n^TX_n^T\left(X_nX_n^T+I_n\right)^{-1}b_n-f_n\to0 $$ Since $w_n^TX_n^T = \sum_{i=1}^mw_{i}x_i^T$ where $x_i$ is $i$th raw of $X_n$, we can write that \begin{align} \frac{1}{n}w_n^TX_n^T\left(X_nX_n^T+I_n\right)^{-1}b_n = \frac{1}{n}\sum_{i=1}^mw_{i}x_i^T\left(X_nX_n^T+I_n\right)^{-1}b_n \end{align} We know that $X_nX_n^T = \sum_{i=1}^mx_ix_i^T$. Let $\left[X_nX_n^T\right]_i = X_nX_n^T-x_ix_i^T$. Thus, \begin{align} \frac{1}{n}w_n^TX_n^T\left(X_nX_n^T+I_n\right)^{-1}b_n &= \frac{1}{n}\sum_{i=1}^mw_{i}x_i^T\left(X_nX_n^T+I_n\right)^{-1}b_n\\ &=\frac{1}{n}\sum_{i=1}^mw_{i}\frac{x_i^T\left(\left[X_nX_n^T\right]_i+I_n\right)^{-1}b_n}{1+x_i^T\left(\left[X_nX_n^T\right]_i+I_n\right)^{-1}x_i} \end{align} Now, since $x_i$ is independent on $\left(\left[X_nX_n^T\right]_i+I_n\right)^{-1}$, we know that (a.s.) $$ x_i^T\left(\left[X_nX_n^T\right]_i+I_n\right)^{-1}x_i-\int (1+x)^{-1} \rho(dx)\to0 $$ where $\rho$ is the limit density of eigenvalues of $XX^T$. The same is true for the numerator. So, the speculation is that $f_n$ behaves like \begin{align} f_n &= \frac{1}{n}\sum_{i=1}^mw_{i}\frac{x_i^Tb_n\int (1+x)^{-1} \rho(dx)}{1+\int (1+x)^{-1} \rho(dx)}\\ &=\frac{\int (1+x)^{-1} \rho(dx)}{1+\int (1+x)^{-1} \rho(dx)}\frac{1}{n}w_n^TX_n^Tb_n \end{align}

Update: Numerical calculations suggests that the above "limit" is not true, although, I can't really say that I completely understand where the rub is.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

For $a_n=b_n$ with $\|a_n\|=\|b_n\|$, the result is standard (and can be found for example in papers of Bai and Silverstein, usually as a technical lemma in the appendix...): let $\rho$ be the limit density of eigenvalues of $XX^T$ (the Pastur-Marchenko law). Then the limit you seek is asymptotically the normalized trace of $(XX^T+I)^{-1}$, i.e., $A:=\int (1+x)^{-1} \rho(dx)$.

If $a_n\neq b_n$ it requires a bit more work, but the answer should be $A\cdot \langle a_n,b_n\rangle$. The reasoning is similar: the expression you have is $\sum \lambda_i \alpha_i \beta_i$ where $\alpha_i$ are the coefficients of $a_n$ in the eigenbase of $XX^T$. This will concentrate near its mean (to prove that, use results on the eigenvectors as in Silverstein's paper from the mid 90's on eigenvectors of covariance matrices; everything is much simpler in the Gaussian case), which will give the expression I wrote.

share|improve this answer
1  
In general of course you do not have a decomposition. However, let's see in your case. Let's take $b_n=\alpha a_n+b_n'$ where $b_n'$ is orthogonal to $a_n$. To make notation simple, assume the norm of $a_n$ and of $b_n'$ to be $1$. You are trying to compute $a_n^T V b_n'$ where $V$ is your matrix of the form $UDU^T$. At least in the Gaussian case, $U$ is Haar distributed and independent of $D$. Let $W$ be the unitary matrix such that $Wa_n=e_1$ and $Wb_n'=e_2$. Then you are trying to compute the (1,2) element of $WUD(WU)^T$. But $WU$ is again Haar distributed, so law is same as –  ofer zeitouni Sep 28 '13 at 11:09
1  
(1,2) element of $UDU^T$, which is $\sum_j U_{1j} U_{2j} D_j$. But this has mean $0$ and is of order $1/\sqrt{n}$. Are you sure about your matlab simulation? –  ofer zeitouni Sep 28 '13 at 11:14
1  
The version with $w^T XX^T$ is trivial: write $w^TXX^T=w^T (XX^T-I)+ w^T$. Now use the previous answer for the second term (first term is trivial). –  ofer zeitouni Sep 28 '13 at 18:47
1  
The Gaussion assumption was to illustrate the point, it is not really needed and the answer will be the same. In any case, what you have is a diagonal matrix (DB) multiplied left and right by vectors that are randomly rotated, in this case by (essentially independent) rotations. This is very similar to the original problem. –  ofer zeitouni Sep 28 '13 at 19:38
1  
I suggest email for further communication. My answers related to the square (n=m) case. In the rectangular case you need to adapt, but D can still be taken diagonal. –  ofer zeitouni Sep 29 '13 at 17:17
show 9 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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