On bilinear forms based on the resolvent of large random matrices

Introduction

Consider a $N\times n$ random matrix $\Sigma_{n}=(\xi_{ij}^{n})$ given by:

The purpose of this article is to study bilinear forms based on the resolvent $Q_{n}(z)$ of matrix $\Sigma_{n}\Sigma_{n}^{*}$, where $\Sigma_{n}^{*}$ stands for the hermitian adjoint of $\Sigma_{n}$:

as the dimensions $N$ and $n$ grow to infinity at the same pace, that is:

a condition that will be referred to as $N,n\rightarrow\infty$ in the sequel.

Such a result is of constant use in the study of centered random matrices, as it allows to describe the behavior of the Stieltjes transform associated to the spectral measure (empirical distribution of the eigenvalues) of the matrix under investigation, see for instance , , , etc. Indeed, the Stieltjes transform of the spectral measure writes:

In the case where $\Sigma_{n}=n^{-1/2}X_{n}$, the quadratic form that appears in the previous expression can be handled by the aforementioned results. However, if $\Sigma_{n}$ is non-centered and given by (1.1), then the quadratic form writes:

It is the purpose of this article to provide a quantitative description of the limiting behavior of the bilinear form $u_{n}^{*}Q_{n}(z)v_{n}$, where $u_{n}$ and $v_{n}$ are deterministic, as the dimensions of $\Sigma_{n}$ go to infinity as indicated in (1.2).

Assumptions, fundamental equations, deterministic equivalents

Formal assumptions for the model are stated below, where $\|\cdot\|$ either denotes the Euclidean norm of a vector or the spectral norm of a matrix.

The family of deterministic $N\times n$ matrices $(A_{n},n\geq 1)$ is bounded for the spectral norm as $N,n\rightarrow\infty$:

Notice that this assumption implies in particular that the Euclidean norm of any row or column of $\|A_{n}\|$ is uniformly bounded in $N,n$.

Nice constants and nice polynomials

Statement of the main result

where $\Phi_{p}$ and $\Psi_{p}$ are nice polynomials depending on $p$ but not on $(u_{n})$ neither on $(v_{n})$.

Denote by $V\Delta V^{*}$ the spectral decomposition of $AA^{*}$, and by $T_{\Delta}$:

Obviously, $T=VT_{\Delta}V^{*}$ and by Theorem 1.1, $u^{*}Qu-u^{*}VT_{\Delta}V^{*}u\rightarrow 0\ .$ Clearly, the limiting behavior of $u^{*}Qu$ not only depends on the spectrum (matrix $\Delta$) of $AA^{*}$ but also on its eigenvectors (matrix $V$).

Contents

In Section 2, we describe two important motivations from electrical engineering. In Section 3, we set up the notations, state intermediate results among which Lemma 3.6, which is the cornerstone of the paper. Loosely speaking, this lemma whose idea can be found in the work of Girko states that quantities such as

are bounded. This control turns out to be central to take into account Assumption A-2. An intermediate deterministic matrix $R_{n}$ is introduced and the proof of Theorem 1.1 is outlined. Basically, the quantity of interest $u^{*}(Q-T)v$ is split into three parts:

Acknowledgment

This work was partially supported by the Agence Nationale de la Recherche (France), project SESAME n∘ANR-07-MDCO-012-01.

Two applications to electrical engineering

Apart from the technical motivations already mentionned in the introduction, Theorem 1.1 has further applications in electrical engineering. In this section, we present an application to Multiple Input Multiple Output (MIMO) wireless communication systems, and an application to statistical signal processing.

A bi-correlated MIMO wireless Ricean channel is a $N\times n$ random matrix $H_{n}$ given by

In the remainder of this section, we consider the case where $B_{n}\neq 0$ and briefly indicate how Theorem 1.1 comes into play. First remark that for every deterministic matrix $K_{n}$, the random matrix $K_{n}H_{n}$ writes:

where $W_{n}$ is standard Gaussian random matrix (notice that $(K_{n}R_{n}K_{n}^{*})^{-1/2}K_{n}R_{n}^{1/2}$ is unitary).

From this, it appears that ${\mathcal{I}}_{mmse}(K_{n})$ can be approximated by $\overline{{\mathcal{I}}}_{mmse}(K_{n})$ given by:

Although the values taken by function $K_{n}\rightarrow\overline{{\mathcal{I}}}_{mmse}(K_{n})$ are defined through the implicit equations (2.2), the first and second derivatives of $\overline{{\mathcal{I}}}_{mmse}$ are easy to compute, and the minimization of $\overline{{\mathcal{I}}}_{mmse}$ instead of ${\mathcal{I}}_{mmse}$ certainly leads to a computationally attractive algorithm.

A number of important related questions remain to be addressed, e.g. the accuracy of the approximation $\overline{{\mathcal{I}}}_{mmse}(K_{n})$, its impact on the error on the optimum solution, the derivation of a more accurate approximation as in , the development of an efficient algorithm to compute the optimal $K_{n}^{*}$, etc.; however this already underlines promising applications of Theorem 1.1 in the context of wireless communication.

2. Statistical signal processing applications

There are many important applications such as source localization using antenna arrays, communication channel estimation, detection of signals corrupted by additive noise, etc. where the observations are stacked into a matrix $\Sigma_{n}$ given by (1.1) in which $A_{n}$ is a non observable deterministic matrix modelling the information to be retrieved and where $Y_{n}$ is due to an additive noise. It is therefore often relevant to estimate certain functionals of matrix $A_{n}$ from $\Sigma_{n}$. In this section, we show how Theorem 1.1 is valuable and relevant in the context of subspace estimators when $N$ and $n$ are of the same order of magnitude.

If $N$ if fixed while $n\rightarrow+\infty$, it is well known that $\|\Sigma_{n}\Sigma_{n}^{*}-(A_{n}A_{n}^{*}+I)\|\rightarrow 0$. Hence, if $\check{\Pi}_{n}$ represents the orthogonal projection matrix on the eigenspace associated to the $N-r$ smallest eigenvalues of $\Sigma_{n}\Sigma_{n}^{*}$, then $\|\check{\Pi}_{n}-\Pi_{n}\|\rightarrow 0$ and thus

In order to model situations in which $n$ and $N$ are large and of the same order of magnitude, it is relevant to look for estimators consistent in the regime given by (1.2). Unfortunately, (2.3) is no longer valid in this context.

An estimator for large N,n𝑁𝑛N,n

The starting point of the estimator proposed in , inspired by , is based on the observation that $\Pi_{n}$ writes:

where ${\mathcal{C}}^{-}$ is a clockwise oriented contour enclosing but not the non-zero eigenvalues of $A_{n}A_{n}^{*}$. In the white noise case, matrix $T_{n}(z)$ writes:

Hence, $u_{n}^{*}\Pi_{n}u_{n}$ is given by:

and it should be expected that $u_{n}^{*}\hat{\Pi}_{n}u_{n}-u_{n}^{*}\Pi_{n}u_{n}\rightarrow 0$ for $N,n\rightarrow\infty$.

Remaining mathematical issues

The full definition of $\hat{\Pi}_{n}$ requires to prove that none of the poles of the integrand of the r.h.s. of (2.5) can be equal to $x_{-}$ or $x_{+}$. Otherwise, the mere definition of $\hat{\Pi}_{n}$ does not make sense. This problem has been solved in the Gaussian case in . In the non Gaussian case, partial results concerning “no eigenvalue separation for the signal plus noise model” together with Theorem 1.1 tend to indicate that the estimator $u_{n}^{*}\hat{\Pi}_{n}u_{n}$ is also consistent.

Notations, preliminary results and sketch of proof

2. Classical and useful results

We remind here classical identities of constant use in the sequel. The first one expresses the diagonal elements of the co-resolvent; the other ones are based on low-rank perturbations of inverses (see for instance [16, Sec. 0.7.4]).

The following lemma describes the behavior of quadratic forms based on random vectors (see for instance [4, Lemma 2.7]).

Let $(X_{k})$ be a complex martingale difference sequence with respect to the filtration $({\mathcal{F}}_{k})$. For every $p\geq 1$, there exists $K_{p}$ such that:

A result on holomorphic functions:

Let $f$ be an holomorphic function on the open unit disc $U$ such that $f(0)=0$ and $\sup_{z\in U}|f(z)|\leq 1$. Then $|f(z)|\leq|z|$ for every $z\in U$.

Rules about nice polynomials and nice constants

Some very simple rules of calculus related to nice polynomials will be particularly helpful in the sequel:

If $(\Phi_{k},1\leq k\leq K)$ and $(\Psi_{k},1\leq k\leq K)$ are nice polynomials, then there exist nice polynomials $\Phi$ and $\Psi$ such that:

Take for instance $\Phi(x)=\sum_{k=1}^{K}\Phi_{k}(x)$ and $\Psi(x)=\sum_{k=1}^{K}\Psi_{k}(x)$.

If $\Phi_{1}$ and $\Psi_{1}$ are nice polynomials, then there exist nice polynomials $\Phi$ and $\Psi$ such that:

Take for instance $\Phi=2^{-1}(1+\Phi_{1})$ and $\Psi=(1+\Psi_{1})$ and note that:

The values of nice constants or nice polynomials may change from line to line within the proofs, the constant or the polynomial remaining nice.

3. Important estimates

Proof of Lemma 3.5 is postponed to Appendix A.

Proof of Lemma 3.6 is postponed to Appendix A.

A slight modification of the proof of [15, Proposition 5.1-(3)] yields the following estimates:

4. Main steps of the proof

In order to prove Theorem 1.1, we split the quantity of interest $u^{*}(Q-T)u$ into three parts:

and handle each term separately in the following propositions:

where $\Phi_{p}$ and $\Psi_{p}$ are nice polynomials depending on $p$ but not on $(u_{n})$ nor on $(v_{n})$.

Assume that the setting of Theorem 1.1 holds true.

where $\Phi$ and $\Psi$ are nice polynomials, not depending on $(u_{n})$ nor on $(v_{n})$.

where $\Phi$ and $\Psi$ are nice polynomials, not depending on $M_{n}$.

Proposition 3.8-(i) is proved in Section 5; proof of Proposition 3.8-(ii) is very similar and thus omitted.

Assume that the setting of Theorem 1.1 holds true. Let $(u_{n})$ and $(v_{n})$ be sequences of $N\times 1$ deterministic vectors.

where $\Phi$ and $\Psi$ are nice polynomials, not depending on $(u_{n})$ nor on $(v_{n})$.

Theorem 1.1 is then easily proved using these three propositions together with inequality $|x+y+z|^{2p}\leq K_{p}(|x|^{2p}+|y|^{2p}+|z|^{2p})$ and (3.7).

Proof of Proposition 3.7

In this section, we establish the estimate:

2. Martingale difference sequence and Burkholder inequality

In the following proposition, we establish relevant estimates.

Assume that the setting of Theorem 1.1 holds true. There exist nice polynomials $(\Phi_{i},1\leq i\leq 4)$ and $(\Psi_{i},1\leq i\leq 4)$ such that the following estimates hold true:

It is now clear that the proof of Proposition 3.7 directly follows from Burkholder’s inequality together with the estimates of Proposition 4.1. The rest of the section is devoted to the proof of Proposition 4.1.

3. Proof of Proposition 4.1: Estimates (4.5) and (4.6)

We split $\Gamma_{1j}$ as $\Gamma_{1j}=\chi_{1j}+\chi_{2j}+\chi_{3j}$, where:

where $(a)$ follows from Jensen’s inequality, $(b)$ from estimate (3.6), and $(c)$ from Lemma 3.1. Thus

We now turn to the contribution of $\chi_{2j}$. Arguments similar as previously yield:

Now, using Eq. (3.12) in Lemma 3.6 yields:

Hence, gathering (4.11) and (4.13) yields estimate (4.5).

We now establish estimate (4.6). As previously, consider identity (4.9); take it this time to the power $p$. Using the same arguments as for (4.10), we obtain:

Similarly, using the same arguments as in (4.12), together with elementary manipulations, we obtain:

Due to the rough estimate (A.1), we obtain

which after summation, and the estimate obtained in Lemma 3.6, yields:

where $\Phi^{\prime}$ and $\Psi^{\prime}$ are nice polynomials. Gathering (4.14) and (4.15) yields estimate (4.6).

4. Proof of Proposition 4.1: Estimates (4.7) and (4.8)

We split $\Gamma_{2j}$ as $\Gamma_{2j}=\chi_{1j}+\chi_{2j}+\chi_{3j}$, where:

where $(a)$ follows from (3.6), $(b)$ from the fact that $|u^{*}Q_{j}a_{j}a_{j}^{*}Q_{j}u|\leq K\boldsymbol{\delta}_{z}^{-2}$ and $|u^{*}Q_{j}a_{j}a_{j}^{*}Q_{j}^{*}u|\leq K\boldsymbol{\delta}_{z}^{-2}$, and $(c)$ from Lemma 3.1. From this and Lemma 3.6, we deduce that:

where $(a)$ follows from the triangle and Jensen’s inequality, $(b)$ from (3.6) and $(c)$ from Cauchy-Schwarz inequality, Lemma 3.1 and Corollary 3.2. Hence,

Gathering the previous results yields the bound:

We now evaluate the second part of Burkholder’s inequality (and may re-use notations $\Phi$ and $\Psi$ for different polynomials).

where $(a)$ follows from Corollary 3.2 and the last estimate, from Lemma 3.6. Similar computations yield:

Proof of Proposition 3.8

In this section, we establish the estimate:

As usual, we now write $\eta_{j}=y_{j}+a_{j}$, group the terms that compensate one another and split $Z_{j}$ accordingly:

Summing over $j$ yields the estimate $\sum_{j}|\chi_{1j}|={\mathcal{O}}\left(|z|^{2}n^{-1/2}\boldsymbol{\delta}_{z}^{-5}\right)$.

Let us now handle the term $\chi_{3j}$. Using the decomposition of $Q_{j}-Q$, Schwarz inequality and the fact that $\sqrt{ab}\leq 2^{-1}(a+b)$ yields

it remains to sum over $j$ and to apply Lemma 3.6 to get the estimate $\sum_{j}|\chi_{3j}|=n^{-1}\Phi(|z|)\Psi(\boldsymbol{\delta}_{z}^{-1})$. Gathering the partial estimates yields:

where $(a)$ follows from (3.6). In order to estimate the remaining square root, we decompose the difference as:

where the $\Phi$’s are nice polynomials with argument $|z|$ and the $\Psi$’s are nice polynomials with argument $|\boldsymbol{\delta}_{z}^{-1}|$, and where $(a)$ follows from (3.7) and $(b)$ from (3.8). It remains to plug this estimate into (5.4), to sum over $j$ and to use Assumption 2 together with Lemma 3.6 to obtain:

where $(a)$ follows from (3.6), and $(b)$ from Lemma 3.1. Hence,

Plugging this into (5.7) yields the estimate

5. End of proof

It remains to gather estimates (5.3), (5.5), (5.6) and (5.8) to get the desired estimate:

Proof of Proposition 3.9

As mentioned in Section 4.1, it is sufficient to establish the estimate:

The following bounds are straightforward:

where $\Phi$ and $\Psi$ are nice polynomials. Then, plugging (6.3) into (6.2) immediately yields the desired result (6.1).

The rest of the section is devoted to establish (6.3).

Notice that it is not proved yet that the right hand side of the previous inequality is nonnegative.

In order to handle estimate (6.9), we shall rely on the following proposition.

Consider the nonnegative real numbers $x_{i},y_{i},s_{i},t_{i}$ ($i=1,2$). Assume that:

If $a\geq c\ (\,\geq 0)$ and $b\geq d\ (\,\geq 0)$, then:

To prove this, simply take the difference of the squares. Applying once this inequality yields $1-\sqrt{x_{1}x_{2}}\geq\sqrt{(1-x_{1})(1-x_{2})}$, hence:

Applying again the first inequality yields then the desired result. ∎

There exist nice polynomials $\Phi$ and $\Psi$ and a set

Proof of Proposition 6.2 is postponed to Appendix B.

We are now in position to establish the following estimate:

where $K,\eta$ are nice constants. Solving now the system (6.4), we obtain:

Appendix A Remaining proofs for Section 3

Note that it is sufficient to establish the result for a vector $u$ with norm one (which is assumed in the sequel). The general result follows by considering $u/\|u\|$.

We proceed by induction over $p$. Let $p=1$ and consider:

As $\|Q\|\leq\boldsymbol{\delta}_{z}^{-1}$, we obtain the desired bound.

It remains to plug the induction assumption to conclude. Hence (3.9) is established.

In order to establish (3.10), one may use the same arguments as previously together with the identity $Q\Sigma\Sigma^{*}=I+zQ$, which yields the factor $|z|^{p}$ in estimate (3.10).

Proof of Lemma 3.6

We prove the lemma in the case where $\|u\|=1$, the general result readily follows by considering $u/\|u\|$.

Write $u^{*}Q_{j}a_{j}a_{j}^{*}Q_{j}^{*}u=\chi_{1j}+\chi_{2j}+\chi_{3j}+\chi_{4j}$ with:

Note that using the facts that $a_{j}a_{j}^{*}\leq AA^{*}$ and $\eta_{j}\eta_{j}^{*}\leq\Sigma\Sigma^{*}$ together with the identity $Q\Sigma\Sigma^{*}=I+zQ$ yield the rough but useful estimates:

where $(a)$ follows from (A.3) and (A.1) and $(b)$, from Corollary 3.2.

It remains to gather the contributions of $\chi_{1j},\chi_{2j},\chi_{3j}$ and $\chi_{4j}$ to get:

where $(a)$ follows from (3.7). Eq. (3.11) is proved.

In order to prove (3.12), first note that:

Hence, it remains to evaluate the contributions of each term. Using decomposition (A.4) together with the estimate (A.5), we obtain:

Combining standard inequalities (Cauchy-Schwarz, $|\sum_{j}a_{j}b_{j}|\leq(\sum_{j}a_{j}^{2})^{1/2}(\sum_{j}b_{j}^{2})^{1/2}$, and Cauchy-Schwarz again), we obtain:

where $(a)$ follows from (A.1), Corollary 3.2 and (3.10). Finally,

Gathering (A.7), (A.8), (A.9) and (A.10), we end up with (3.12), and Lemma 3.6 is proved.

Appendix B Remaining proofs for Section 6

Developing the previous identities, we end up with the system:

Furthermore, when $\operatorname*{Re}(z)<0$, we have

We can now find a lower bound to $w_{1}$:

where $K$ is a nice constant. The same bound holds for $z\in(-\infty,0)$ by continuity of $\det(I-C_{1}(z))$ at any point of the open real negative axis.

Proof of Proposition 6.2-(ii)

There exists nice polynomials $\Phi$ and $\Psi$ such that:

As $\Phi(x)$ is increasing and $\Psi(1/x)$ is decreasing in $x>0$, we obtain:

The function ${\boldsymbol{\varepsilon}}$ is holomorphic on ${\mathcal{D}}_{z}$. Consider the function: Applying Lemma 3.4 with

Let $\zeta=\mathbf{i}2\operatorname*{Im}(z)/\operatorname*{Re}(z)$, apply Lemma 3.4, and use (B.5). This yields:

where $\Phi$ and $\Psi$ are nice polynomials. As $\operatorname*{Im}({\boldsymbol{\varepsilon}}(\operatorname*{Re}(z)))=0$, we obtain

This proves the first inequality. The second one can be proved similarly. ∎

Finally, we can state that there exist nice polynomials $\Phi$ and $\Psi$ such that:

References