2
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
14
  • 1
    $\begingroup$ 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 $\endgroup$ Sep 28, 2013 at 11:09
  • 1
    $\begingroup$ (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? $\endgroup$ Sep 28, 2013 at 11:14
  • 1
    $\begingroup$ 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). $\endgroup$ Sep 28, 2013 at 18:47
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 28, 2013 at 19:38
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 29, 2013 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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