The Random Matrix Regime of Maronna's M-estimator with elliptically distributed samples

Introduction and problem statement

While classical sample covariance matrices exhibit a rather simple dependence structure (as they are merely the sum of independent or linearly dependent rank-one matrices), robust scatter matrix estimators are usually of a much more complex form which does not allow for standard random matrix analysis. This work specifically considers a widely spread model of robust scatter estimator, proposed in (Maronna, 1976), which contains as special cases the maximum-likelihood estimator of the scatter matrix for elliptically distributed population vectors, and which is well-behaved and mostly understood in the classical regime where $n\to\infty$ while $N$ is fixed. It is in particular shown in (Maronna, 1976) that under some conditions the estimator is well-defined as the unique solution of a fixed-point equation and that the robust estimator converges almost surely (a.s.) to a deterministic matrix (which can be the scatter matrix for elliptical distribution of $x_{i}$ under correct parametrization). In this article, we revisit the study of Maronna’s estimator for elliptically distributed samples using a probabilistic approach (as opposed to the statistical approach used classically in robust estimation theory) under the assumption that $n$ and $N$ are both large and of the same order of magnitude. This work follows after (Couillet et al., 2013) where the simpler case of vector samples $x_{i}$ with independent entries was explored. The intuition for the proof of the main results follows in particular from the proof of the main theorem in (Couillet et al., 2013).

Studying robust scatter estimators in the large random matrix regime, i.e. as $N,n$ grow large at the same speed, has important consequences in understanding many signal processing algorithms exploiting these estimators (Pascal et al., 2008a, b). It also allows one to derive improved methods for source detection and parameter estimation as in (Cardoso et al., 2008; Bianchi et al., 2011; Mestre and Lagunas, 2008; Loubaton and Vallet, 2010; Hachem et al., 2011) for sample covariance matrix-based estimators. Adaptations (and improvements) of these results to robust estimation are currently under investigation.

For each $N$, $c_{N}<1$, $\bar{c}_{N}\geq 1$ and

where $u$ satisfies the following properties:

$u:[0,\infty)\to(0,\infty)$ is nonnegative continuous and non-increasing

$\phi:x\mapsto xu(x)$ is increasing and bounded with $\lim_{x\to\infty}\phi(x)\triangleq\phi_{\infty}>1$

Note that (ii) is stronger than Maronna’s original assumption (Maronna, 1976, Condition (C) p. 53) as $\phi$ cannot be constant on any open interval. The assumption (iii) is also not classical in robust estimation but obviously compliant with the large $n$ assumption made in classical works (for which $c_{+}=0$). The importance of both assumptions will appear clearly in the proof of the main results.

The statistical hypotheses on $x_{1},\ldots,x_{n}$ are detailed below.

The vectors $x_{i}=\sqrt{\tau_{i}}A_{N}y_{i}$, $i\in\{1,\ldots,n\}$, satisfy the following hypotheses:

the (random) empirical measure $\nu_{n}=\frac{1}{n}\sum_{i=1}^{n}{\bm{\delta}}_{\tau_{i}}$ satisfies $\int x\nu_{n}(dx)\overset{\rm a.s.}{\longrightarrow}1$

there exist $\varepsilon<1-\phi_{\infty}^{-1}<1-c_{+}$ and $m>0$ such that, for all large $n$ a.s. $\nu_{n}([0,m))<\varepsilon$

defining $C_{N}\triangleq A_{N}A_{N}^{*}$, $C_{N}\succ 0$ and $\limsup_{N}\|C_{N}\|<\infty$

Item 1 is merely a normalization condition which, along with Item 3, ensures the proper scaling and asymptotic boundedness of the model parameters. Note in particular that Item 1 ensures a.s. tightness of $\{\nu_{n}\}_{n=1}^{\infty}$, i.e. for each $\varepsilon>0$, there exists $M>0$ such that, with probability one, $\nu_{n}([M,\infty))<\varepsilon$ for all $n$. Item 2 mainly ensures that no heavy mass of $\tau_{i}$ concentrates close to zero; this will ensure the existence of a solution to (1) and avoid technical problems when a solution to (1) exists (and is therefore invertible) but has many eigenvalues close to zero.

All these conditions are met in particular if the $\tau_{i}$ are independent and identically distributed (i.i.d.) with common unit mean distribution $\nu$ (in which case $\int x\nu_{n}(dx)\overset{\rm a.s.}{\longrightarrow}1$ by the strong law of large numbers) such that $\nu(\{0\})=0$. If in addition $N=\bar{N}$, then $x_{1},\ldots,x_{n}$ are i.i.d. zero-mean complex (or real) elliptically distributed with full rank (Ollila et al., 2012, Theorem 3). In particular, if $\tau_{1}$ is Rayleigh distributed, $x_{1}$ is complex zero mean Gaussian. If $1/\tau_{1}$ is chi-squared distributed, $x_{1}$ is instead zero mean complex Student distributed, etc. (see (Ollila et al., 2012) for further discussions and recent results on elliptical distributions).

For simplicity of exposition, most of the article, and in particular the proofs of the main results, will assume the case of complex $x_{i}$; the results remain however valid in the case of real random variables.

Assumption 3 controls the relative speed of the tail of $\nu_{n}$ versus the flattening speed of $\phi(x)$ as $x\to\infty$. Practical examples satisfying Assumption 3 are:

There exists $M>0$ such that, for all $n$, $\max_{1\leq i\leq n}\tau_{i}<M$ a.s. In this case, $\nu_{n}((t,\infty))=0$ a.s. for $t>M$ while $\phi(at)-\phi(bt)\neq 0$ since $\phi$ is increasing.

For $u(t)=(1+\alpha)/(\alpha+t)$ for some $\alpha>0$, it is easily seen that it is sufficient that $\limsup_{n}\nu_{n}((t,\infty))=o(1/t)$ a.s. for Assumption 3 to hold. In particular, if the $\tau_{i}$ are i.i.d. with distribution $\nu$, $\limsup_{n}\nu_{n}((t,\infty))=\nu((t,\infty))$ a.s. and, by Markov inequality, it suffices that $\int x^{1+\varepsilon}\nu(dx)<\infty$ for some $\varepsilon>0$.

As for the large dimensional behavior of $\hat{C}_{N}$, in the fixed $N$ large $n$ regime and for i.i.d. $\tau_{i}$, it is of the form $\hat{C}_{N}\overset{\rm a.s.}{\longrightarrow}V_{N}$ where $V_{N}$ is the unique solution to $V_{N}={\rm E}[u(\frac{1}{N}x_{1}^{*}V_{N}^{-1}x_{1})x_{1}x_{1}^{*}]$ (Maronna, 1976, Theorem 5). When the $x_{i}$ are i.i.d. elliptically distributed and $u$ is such that $\hat{C}_{N}$ is the maximum-likelihood estimator for $C_{N}$, then $V_{N}=C_{N}$, leading to a consistent estimator for $C_{N}$. In the random matrix regime of interest here, we show that $\hat{C}_{N}$ does not converge in any classical sense to a deterministic matrix but satisfies $\|\hat{C}_{n}-\hat{S}_{N}\|\overset{\rm a.s.}{\longrightarrow}0$ in spectral norm, where $\hat{S}_{N}$ follows a random matrix model studied in (Zhang, 2006; Paul and Silverstein, 2009; Couillet and Hachem, 2013). As such, the spectral behavior of $\hat{C}_{N}$ is easily analyzed from that of $\hat{S}_{N}$ for $N,n$ large.

In the next section, we introduce some new notations that simplify the analysis of $\hat{C}_{N}$ and provide an insight on the derivation of our main result, Theorem 2.

Preliminaries

First note from the expression of $\hat{C}_{N}$ as a (hypothetical) solution to (1) that we can assume $C_{N}=I_{N}$ by studying $C_{N}^{-\frac{1}{2}}\hat{C}_{N}C_{N}^{-\frac{1}{2}}$ in place of $\hat{C}_{N}$. Therefore, here and in all the major proofs in the article, without generality restriction, we place ourselves under the assumption $C_{N}=A_{N}A_{N}^{*}=I_{N}$.

Our objective is to prove that $\hat{C}_{N}$ is a well behaved solution of (1) (for all large $n$ a.s.) and to study the spectral properties of $\hat{C}_{N}$ as $N,n$ grow large. However, the structure of dependence between the rank-one matrices $u(\frac{1}{N}x_{i}^{*}\hat{C}_{N}^{-1}x_{i})x_{i}x_{i}^{*}$, $i=1,\ldots,n$, makes the large dimensional analysis of $\hat{C}_{N}$ via standard random matrix methods impossible (see e.g. (Pastur and Ŝerbina, 2011; Bai and Silverstein, 2009; Anderson et al., 2010)) as these methods fundamentally rely on the independence (or simple dependence) of the structuring rank-one matrices. We propose here to show that, in the large $N,n$ regime, $\hat{C}_{N}$ behaves similar to a matrix $\hat{S}_{N}$ whose structure is more standard and easily analyzed through classical random matrix results. For this we first need to rewrite the fundamental equation (1) in order to exhibit a sufficiently “weak” dependence structure in the expression of $\hat{C}_{N}$. This rewriting is performed in Section 2.1 below. This being done, we then prove that some weakly dependent terms can be well approximated by independent ones in the large $N,n$ regime. Since the final result does not take an insightful form, we provide below in Section 2.2 a hint on how to obtain it intuitively.

We need to introduce some new notations that will simplify the coming considerations. Write $x_{i}=\sqrt{\tau_{i}}A_{N}y_{i}\triangleq\sqrt{\tau_{i}}z_{i}$ and recall that $C_{N}=I_{N}$ for the moment (in particular, $\|z_{i}\|$ is of order $\sqrt{N}$ for most $z_{i}$). If $\hat{C}_{N}$ is well-defined, we denote $\hat{C}_{(i)}\triangleq\hat{C}_{N}-\frac{1}{n}u(\frac{1}{N}x_{i}^{*}\hat{C}_{N}^{-1}x_{i})x_{i}x_{i}^{*}$.

Remark that $\hat{C}_{(i)}$ depends on $x_{i}$ only through the terms $u(\frac{1}{N}x_{j}^{*}\hat{C}_{N}^{-1}x_{j})$, $j\neq i$, in which the term $\hat{C}_{N}$ is built on $x_{i}$. But since $x_{i}$ is only one among a growing number $n$ of $x_{j}$ vectors, this dependence structure looks intuitively “weak”. This informal weak dependence between $x_{i}$ and $\hat{C}_{(i)}$, along with classical random matrix theory considerations, suggests that the quadratic forms $\frac{1}{N}z_{i}^{*}\hat{C}_{(i)}^{-1}z_{i}$, $i=1,\ldots,n$, are all well approximated by $\frac{1}{N}\operatorname{tr}\hat{C}_{N}^{-1}$ (more precisely, this would roughly be a consequence of Lemma 5 and Lemma 4 in the Appendix if $z_{i}$ and $\hat{C}_{(i)}$ were truly independent).

Using Assumption 1 and $\phi_{\infty}<c_{+}^{-1}$, taking $n$ large enough to have $\phi(x)\leq\phi_{\infty}<1/c_{N}$, this can be rewritten

Now, since $\phi$ is increasing, $g:[0,\infty)\to[0,\infty)$, $x\mapsto x/(1-c_{N}\phi(x))$ is increasing, nonnegative, and maps $[0,\infty)$ onto $[0,\infty)$. Thus, $g$ is invertible with inverse denoted $g^{-1}$. In particular, from (2),

Call now $v:[0,\infty)\to[0,\infty)$, $x\mapsto u\circ g^{-1}$. Since $g$ is increasing and nonnegative and $u$ is non-increasing, $v$ is non-increasing and positive. Moreover, $\psi:x\mapsto xv(x)$ satisfies:

which is increasing, nonnegative, and has limit $\psi^{N}_{\infty}\triangleq\phi_{\infty}/(1-c_{N}\phi_{\infty})$ as $x\to\infty$. Hence, $v$ and $\psi$ keep the same properties as $u$ and $\phi$, respectively.

With these notations, to prove the existence and uniqueness of a solution to (1), it is equivalent to prove that the equation in $Z$

has a unique positive definite solution. But for this, it is sufficient to prove the uniqueness of $d_{1},\ldots,d_{n}\geq 0$ satisfying the $n$ equations:

Indeed, if these $d_{i}$ are uniquely defined, then so is the matrix

with $d_{i}=\frac{1}{N}z_{i}^{*}\hat{C}_{(i)}^{-1}z_{i}$, $\hat{C}_{(i)}=\hat{C}_{N}-\frac{1}{n}u(\frac{1}{N}x_{i}^{*}\hat{C}_{N}^{-1}x_{i})x_{i}x_{i}^{*}$ (the existence follows from taking the $d_{i}$ solution to (3) and write $\hat{C}_{N}$ as in (4), while uniqueness follows from the fact that (4) cannot be written with a different set of $d_{i}$ from the uniqueness of the solution to (3)).

This is the approach that is pursued to prove Theorem 1, based on the results from Yates (1995). Equation (4), which is equivalent to (1) (with $\hat{C}_{N}$ in place of $Z$), will be preferably used in the remainder of the article.

2 Hint on the main result

Assume here that the $d_{i}$ above are indeed unique for all large $n$ so that $\hat{C}_{N}$ is well defined. We provide some intuition on the main result.

From the discussion in Section 2.1, we may expect the terms $d_{i}$ to be all close to $\frac{1}{N}\operatorname{tr}\hat{C}_{N}^{-1}$ for $N,n$ large enough. We may also expect $\frac{1}{N}\operatorname{tr}\hat{C}_{N}^{-1}$ to have a deterministic equivalent $\gamma_{N}$, i.e. there should exist a deterministic sequence $\{\gamma_{N}\}_{N=1}^{\infty}$ such that $|\frac{1}{N}\operatorname{tr}\hat{C}_{N}^{-1}-\gamma_{N}|\overset{\rm a.s.}{\longrightarrow}0$. Let us say that all this is true. Since $\frac{1}{N}\operatorname{tr}\hat{C}_{N}^{-1}$ is the Stieltjes transform $\frac{1}{N}\operatorname{tr}(\hat{C}_{N}-zI_{N})^{-1}$ of the empirical spectral distribution of $\hat{C}_{N}$ at point $z=0$, and since $\hat{C}_{N}$ is expected to be close to $\frac{1}{n}\sum_{i}\tau_{i}v(\tau_{i}\gamma_{N})z_{i}z_{i}^{*}$ with now $v(\tau_{i}\gamma_{N})$ independent of $z_{1},\ldots,z_{n}$, from classical random matrix works, e.g. (Silverstein and Bai, 1995), we would expect that one such $\gamma_{N}$ be given by (recall that $C_{N}=I_{N}$)

if this fixed-point equation makes sense at all. This can be equivalently written as

We in fact prove in Section 3 that such a positive $\gamma_{N}$ is well defined, unique, and satisfies $\max_{1\leq i\leq n}|d_{i}-\gamma_{N}|\overset{\rm a.s.}{\longrightarrow}0$ (under correct assumptions). Proving this result is the main difficulty of the article.

This convergence, along with (4), will then ensure that for all large $n$ a.s.

with $\gamma_{N}$ the unique positive solution to (5). It is then immediate under Assumption 2–3 to see that the result holds true also for $C_{N}\neq I_{N}$.

The major interest of this convergence in spectral norm is that $\hat{S}_{N}$ is a known and easily manipulable object, as opposed to $\hat{C}_{N}$. The result therefore conveys a lot of information about $\hat{C}_{N}$ among which the fact that its largest and smallest eigenvalues are almost surely bounded and bounded away from zero for all large $n$ (which is not in general the case of $\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{*}$ for $\tau_{i}$ with unbounded support).

Main results

We now make the statements of Section 2.2 rigorous. The first result ensures the existence and uniqueness of a solution $\hat{C}_{N}$ to (1) for $n$ large enough.

Let Assumptions 1 and 2 hold, with $\limsup_{N}\|C_{N}\|$ non necessarily bounded. Then, for all large $n$ a.s., (1) has a unique solution $\hat{C}_{N}$ given by

Having defined $\hat{C}_{N}$, the main result of the article provides a random matrix equivalent to $\hat{C}_{N}$, much easier to study than $\hat{C}_{N}$ itself.

Let Assumptions 1–3 hold, and let $\hat{C}_{N}$ be given by Theorem 1 when uniquely defined as the solution of (1) or chosen arbitrarily if not. Then

and $\gamma_{N}$ is the unique positive solution of the equation in $\gamma$

The fact that $\hat{C}_{N}$ is well approximated by $\hat{S}_{N}$, which follows a random matrix model studied extensively in (Paul and Silverstein, 2009; Couillet and Hachem, 2013), has important consequences. From a purely mathematical standpoint, this provides a full characterization of the spectral behavior of $\hat{C}_{N}$ for large $N,n$ (see in particular Corollary 1 below). For application purposes, this first enables the performance analysis in the large $N,n$ horizon of standard signal processing methods already relying on $\hat{C}_{N}$ (these methods were so far analyzed solely in the fixed $N$ large $n$ regime). A second, more important, consequence for signal processing application is the possibility to fully exploit the structure of $\hat{C}_{N}$ for large $N,n$ to improve existing robust schemes. Deriving such improved methods is not the subject of the current article but should be directly accessible from Theorem 2, while performance analysis of these methods may demand supplementary treatment, such as central limit theorems for functionals of $\hat{C}_{N}$.

Equation (6) is obtained from the results of (Zhang, 2006) with notations similar to (Couillet and Hachem, 2013). The characterization of $\mu_{N}$ follows from (Couillet and Hachem, 2013), where more information can be found. The uniform boundedness of the support is a consequence of the boundedness of $\psi$ and $\gamma_{N}$, Lemma 1 in Section 4. Finally, the results (7) and (8) are an application of (Paul and Silverstein, 2009) along with $\limsup_{N}\|\hat{S}_{N}\|\leq v(0)\limsup_{N}\|C_{N}\|\limsup_{N}\|\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{*}\|<\infty$ by Assumption 2–3 and (Bai and Silverstein, 1998).

A consequence of Theorem 2 and Corollary 1 in the i.i.d. elliptical case is as follows.

Let Assumptions 1–3 hold and in addition, let $\tau_{i}$ be i.i.d. with law $\nu$ and let $c_{N}\to c$. Then

where $\gamma^{\infty}$ is the unique positive solution to the equation in $\gamma$

with $\psi_{c}=\lim_{c_{N}\to c}\psi$. Moreover, if $\frac{1}{n}\sum_{i=1}^{n}{\bm{\delta}}_{\lambda_{i}(C_{N})}\to\nu^{C}$ weakly, then

We use the fact that $\gamma_{N}\overset{\rm a.s.}{\longrightarrow}\gamma^{\infty}$ ($\gamma_{N}$ defined in Theorem 2) which is a consequence of $\psi/(1+c_{N}\psi)$ being monotonous and $\gamma_{N}$ uniformly bounded, Lemma 1. The rest unfolds from classical random matrix techniques.

Figures 1 and 2 depict the empirical histogram of the eigenvalues of $\hat{C}_{N}$ and $\hat{S}_{N}$, for $N=500$ and $n=2500$ with $u(t)=(1+\alpha)/(t+\alpha)$, $\alpha=0.1$, $C_{N}=\operatorname{diag}(I_{125},3I_{125},10I_{250})$, and $\tau_{1},\ldots,\tau_{n}$ i.i.d. with $\Gamma(.5,2)$ distribution. In thick line is also depicted the density of $\mu_{N}$ in Corollary 1 which shows an accurate match to the empirical spectrum as predicted by (6). As a comparison, Figure 3 shows the empirical histogram of the eigenvalues of the sample covariance matrix $\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{*}$ under the same parametrization against the deterministic equivalent density for this model in thick line (Zhang, 2006). This graph presents a seemingly unbounded eigenvalue spectrum support (in fact bounded for each $N$ but growing with $N$) which is expected since $\tau_{1}$ has unbounded support. Also note the gain of separability in the spectrum of $\hat{C}_{N}$ which exhibits clearly three compacts subsets of eigenvalues, reminiscent of the three masses in the eigenvalue distribution of $C_{N}$, while $\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{*}$ exhibits a single compact set of eigenvalues. This has important consequences from detection and estimation purposes in signal processing application of robust estimation.

In the next section, we present the proofs of Theorem 1 and Theorem 2.

Proof of the main results

For the sake of definition, we take all variables to be complex here although the arguments are also valid for real random variables.

As mentioned in Section 2, we can assume without generality restriction that $C_{N}=I_{N}$. Indeed, if $\hat{C}_{N}$ is the unique solution to (1) assuming $C_{N}=I_{N}$, then, for any other choice of $C_{N}\succ 0$, $C_{N}^{\frac{1}{2}}\hat{C}_{N}C_{N}^{\frac{1}{2}}$ is the unique solution to the corresponding model in (1). Hence, we only need to prove the result for $C_{N}=I_{N}$.

As shown in Section 2.1, in order to show that $\hat{C}_{N}$ is uniquely defined, it suffices to show that there exists a unique $q_{1},\ldots,q_{n}$ such that for each $j$, $q_{j}=h_{j}(q_{1},\ldots,q_{n})$. For this, we show first that $h$ satisfies the following properties with probability one:

Nonnegativity: For each $q_{1},\ldots,q_{n}\geq 0$ and each $i$, $h_{i}(q_{1},\ldots,q_{n})>0$

Monotonicity: For each $q_{1}\geq q_{1}^{\prime},\ldots,q_{n}\geq q_{n}^{\prime}$ and each $i$, $h_{i}(q_{1},\ldots,q_{n})\geq h_{i}(q_{1}^{\prime},\ldots,q_{n}^{\prime})$

Scalability: For each $\alpha>1$ and each $i$, $\alpha h_{i}(q_{1},\ldots,q_{n})>h_{i}(\alpha q_{1},\ldots,\alpha q_{n})$.

Item (a) is obvious since the matrix inverse is well defined for all $n$ large and $z_{i}\neq 0$ almost surely. Item (b) follows from the fact that, for two Hermitian matrices $A\succeq B\succ 0$, $B^{-1}\succeq A^{-1}\succ 0$ ((Horn and Johnson, 1985, Corollary 7.7.4)), and from $v$ being non-increasing, entailing $h_{i}$ to be a non-decreasing function of each $q_{j}$. As for Item (c), it follows also from the previous matrix inverse relation and from $\psi$ being increasing, entailing in particular that, for $\alpha>1$, $\psi(\alpha q_{i})>\psi(q_{i})$ if $q_{i}\neq 0$ so that $v(\alpha q_{i})>v(q_{i})/\alpha$ for $q_{i}\geq 0$.

According to Yates (Yates, 1995, Theorem 2), $h$ is then a standard interference function and, if there exists $q_{1},\ldots,q_{n}$ such that for each $i$, $q_{i}>h_{i}(q_{1},\ldots,q_{n})$ (feasibility condition), then there is a unique $\{q_{1},\ldots,q_{n}\}$ satisfying $q_{i}=h_{i}(q_{1},\ldots,q_{n})$ for each $i$, which is given by $q_{i}=\lim_{t\to\infty}q_{i}^{(t)}$ with $q^{(0)}_{i}\geq 0$ arbitrary and, for $t\geq 0$, $q_{i}^{(t+1)}=h_{i}(q_{1}^{(t)},\ldots,q_{n}^{(t)})$ (which would then conclude the proof). To obtain the feasibility condition, note that the function $q\mapsto\frac{1}{N}z_{j}^{*}\left(\frac{1}{n}\sum_{i\neq j}\psi(\tau_{i}q)z_{i}z_{i}^{*}\right)^{-1}z_{j}$ is decreasing and, as $q\to\infty$, has limit $\frac{1-c_{N}\phi_{\infty}}{\phi_{\infty}}\frac{1}{N}z_{j}^{*}\left(\frac{1}{n}\sum_{i\neq j,\tau_{i}\neq 0}z_{i}z_{i}^{*}\right)^{-1}z_{j}$. As $\{\tau_{i}\}_{i=1}^{n}$ and $\{z_{i}\}_{i=1}^{n}$ are independent and $\limsup_{n}N/|\{\tau_{i}\neq 0\}|=\limsup c_{N}/(1-\nu_{n}(\{0\}))<1$ a.s. (Assumption 2 and Assumption 1), for all large $n$ a.s., we fall within the hypotheses of Lemma 6 in the Appendix and we can then write,To be more exact, since $|\{\tau_{i}\neq 0\}|$ is random with probability space $\mathcal{T}$ producing the $\tau_{i}$’s, Lemma 6 applies only on a subset of probability one of $\mathcal{T}$. It then suffices to apply Tonelli’s theorem (Billingsley, 1995) to ensure that Lemma 6 can be extended and still holds with probability one on the product space producing the $(\tau_{i},z_{i})$.

Assume first that $\tau_{j}\neq 0$. Then, using the relation

and the fact that for all large $n$ a.s. $1-\nu_{n}(\{0\})>c_{+}$, we have

Therefore, using the fact that $\nu_{N}(\{0\})<1-\phi_{\infty}^{-1}$ for all $n$ large a.s. (Assumption 2–2), we have that for all $j$ with $\tau_{j}\neq 0$

and we find also the inequality (9) for all large $n$ a.s. and for all $j$ with $\tau_{j}=0$, using once more $\nu_{N}(\{0\})<1-\phi_{\infty}^{-1}$. As such, (9) is valid for all $j\in\{1,\ldots,n\}$.

We can then choose $n$ large enough so that (9) holds for all $j$, after what, taking $q$ sufficiently large,

for all $j$, i.e. $h_{j}(q,\ldots,q)<q$. This ensures feasibility for all large $n$ a.s. and concludes the proof.

2 Proof of Theorem 2

Similar to the proof of Theorem 1, we can restrict ourselves to the assumption that $C_{N}=I_{N}$. The generalization to $C_{N}$ satisfying Assumption 2-3) will follow straightforwardly. We therefore take $C_{N}=I_{N}$ in what follows.

We start the proof by introducing the following fundamental lemmas (note that these lemmas in fact hold true irrespective of $C_{N}\succ 0$).

Let Assumption 1 hold and let $h:[0,\infty)\to[0,\infty)$ be given by

Then, for all large $n$ a.s., there exists a unique $\gamma_{N}>0$ satisfying $\gamma_{N}=h(\gamma_{N})$, given by

with $\gamma_{N}^{(0)}\geq 0$ arbitrary and, for $t\geq 0$, $\gamma_{N}^{(t+1)}=h(\gamma_{N}^{(t)})$. Moreover, with probability one,

for some $\gamma_{-},\gamma_{+}>0$ finite.

As in the proof of Theorem 1, we show that $h$ (scalar-valued this time) is a standard interference function. We show easily positivity, monotonicity and scalability of $h$. Indeed, for $\gamma\geq 0$, $h(\gamma)>0$. For $\gamma\geq\gamma^{\prime}\geq 0$,

which follows from $v$ being nonnegative decreasing. Finally, for $\alpha>1$, $\alpha h(0)>h(0)$ and for $\gamma\neq 0$,

which follows from $\gamma\mapsto\psi(\tau_{i}\gamma)(1+c_{N}\psi(\tau_{i}\gamma))^{-1}$ being increasing as long as $\tau_{i}\neq 0$. It remains to prove the existence of a $\gamma$ such that $\gamma>h(\gamma)$, inducing by (Yates, 1995, Theorem 2) the uniqueness of the fixed-point $\gamma_{N}$ given by $\gamma_{N}=\lim_{t\to\infty}\gamma_{N}^{(t)}$ as stated in the theorem. For this, we use again the fact that $\gamma\mapsto\psi(\tau_{i}\gamma)(1+c_{N}\psi(\tau_{i}\gamma))^{-1}$ is increasing and that (Assumption 2–2), for all large $n$ a.s.

Therefore, there exists $\gamma_{0}$ (a priori dependent on the set $\{\tau_{1},\ldots,\tau_{n}\}$) such that, for all $\gamma>\gamma_{0}$, $h(\gamma)<\gamma$.

To prove uniform boundedness of $\gamma_{N}$, let $\varepsilon>0$ and $m>0$ be such that $(1-\varepsilon)\phi_{\infty}>1$ and $\nu_{n}((m,\infty))>1-\varepsilon$ for all $n$ large a.s. (always possible from Assumption 2–2). Then, for all $n$ large a.s.

as $\gamma\to\infty$. Similar to $\gamma_{0}$ above, we can therefore choose $\gamma_{+}$ large enough, now independent of $n$ large, such that, a.s. $\gamma\geq\gamma_{+}\Rightarrow\gamma>h(\gamma)$, implying $\gamma_{N}<\gamma_{+}$ for these $n$ large since $\gamma_{N}=h(\gamma_{N})$. Also, $h(0)>1/(2v(0))$ for all large $n$ a.s. since $\frac{1}{n}\sum_{i=1}^{n}\tau_{i}\overset{\rm a.s.}{\longrightarrow}1$ by Assumption 2. Hence, by the continuous growth of $h$, we can take $\gamma_{-}=1/(2v(0))>0$ which is such that $\gamma\leq\gamma_{-}\Rightarrow h(\gamma)\geq h(0)>\gamma$ for all large $n$ a.s. This implies $\gamma_{N}>\gamma_{-}$ for all large $n$ a.s., which concludes the proof.

For further use, note that Lemma 1 can be refined as follows. Let $(\eta,M_{\eta})$ be couples indexed by $\eta$ with $0<\eta<1$ and $M_{\eta}>0$ such that $\nu_{n}((M_{\eta},\infty))<\eta$ for all large $n$ a.s. (possible by tightness of $\nu_{n}$). Then, for sufficiently small $\eta$, the equation in $\gamma$

has a unique solution $\gamma_{N}^{\eta}$ for all large $n$ a.s. and there exists $\gamma_{-},\gamma_{+}>0$ such that, for all $\eta<\eta_{0}$ small, $\gamma_{-}<\gamma_{N}^{\eta}<\gamma_{+}$ for all large $n$ a.s.

The uniqueness is clear as long as $(1-\eta_{0})(1-\limsup_{n}\nu_{n}(\{0\}))\phi_{\infty}>1$ since then, exploiting the fact that $\lim_{n}\frac{|\{\tau_{i}\leq M_{\eta}\}|}{n}>1-\eta_{0}$ a.s.,

for all $n$ large a.s. and the proof follows from the proof of Lemma 1. For uniform boundedness, taking $M_{\eta_{0}}<M_{\eta}$ large enough (or equivalently $\eta_{0}>\eta$ small enough) such that $\liminf_{n}\frac{|\{m<\tau_{i}\leq M_{\eta}\}|}{n}>\liminf_{n}\frac{|\{m<\tau_{i}\leq M_{\eta_{0}}\}|}{n}>1-\varepsilon$ a.s. in the proof of Lemma 1 leads to the same upper bound result for all small $\eta<\eta_{0}$. As for the lower bound, we still have $h(0)>1/(2v(0))$ for all large $n$ a.s. independently of $\eta$ so the result is maintained.

Let Assumption 1 hold and define $\gamma_{N}$ as in Lemma 1. Then, as $n\to\infty$,

We first show that there exists $\eta>0$ such that, for all large $n$ a.s.

(recall that $\lambda_{1}$ stands for the smallest eigenvalue). For this, take $0<\varepsilon<1-c_{+}$ and $m>0$ be such that $\nu_{n}((m,\infty))>1-\varepsilon$ for all $n$ large a.s. (Assumption 2–2). Using the fact that $xv(x)=\psi(x)$ is non-decreasing and that any subtraction of a nonnegative definite matrix cannot increase the smallest eigenvalue, we have

Since $\nu_{n}((m,\infty))>1-\varepsilon$ for all $n$ large a.s.,

From Lemma 6 in the Appendix (see footnote in the proof of Theorem 1 for details), we can then write

for some $\eta^{\prime}>0$ which, along with the almost sure boundedness of $\gamma_{N}$ (Lemma 1) proves (10).

This bound being irrespective of all $z_{i}$ and $\tau_{i}$, $i\neq j$, we can take the expectation with respect to all $y_{i}$, $i\neq j$, and all $\tau_{i}$ to obtain

Taking $p>4$ and applying the union bound, Markov inequality, and Borel Cantelli lemma finally shows that

With the same arguments on $\kappa_{j}$ and with the same $p$ as above, now remark that

since $\bar{N}\geq N$. Therefore, by the union bound, Markov inequality, and Borel Cantelli lemma,

Combining (12) and (13) along with the fact that $\min_{1\leq j\leq n}\kappa_{j}\overset{\rm a.s.}{\longrightarrow}1$ (from (10)) finally gives

By (10), $A_{(j)}=(A_{(j)}-\frac{\eta}{2}I_{N})+\frac{\eta}{2}I_{N}$ with $\liminf_{n}\lambda_{1}(A_{(j)}-\frac{\eta}{2}I_{N})>0$ a.s., so we are in the conditions of Lemma 4 and we have

It remains to find a deterministic equivalent for $\frac{1}{N}\operatorname{tr}A^{-1}$. Similar to above, note first that, for all large $n$ a.s.

where $m_{N}(0)$ is the unique nonnegative solution to the equation in $m$ (as long as at least one $\tau_{i}$ is non-zero)

Now, by definition, $\gamma_{N}$ coincides with such a solution. By uniqueness of $m_{N}(0)$, one must then have $m_{N}(0)=\gamma_{N}$ so that, gathering all results together,

Similar to Remark 1, note that Lemma 2 can be further extended to

for some $\eta$ small enough, with $M_{\eta}$ and $\gamma_{N}^{\eta}$ defined in Remark 1.

One shows boundedness of $\lambda_{1}(\frac{1}{n}\sum_{\tau_{i}\leq M_{\eta},i\neq j}\tau_{i}v(\tau_{i}\gamma^{\eta}_{N})z_{i}z_{i}^{*})$ simply by taking $\eta$ for which $\nu_{n}((m,M_{\eta}))>1-\varepsilon$ for all large $n$ a.s. in the proof of Lemma 2. Then it suffices to adapt all derivations by substituting $\tau_{i}$ by zero if $\tau_{i}>M_{\eta}$. The result follows straightforwardly.

The two lemmas above are standard random matrix results on $x_{1},\ldots,x_{n}$, independent of the structure of $\hat{C}_{N}$. The next lemma introduces a first result on the matrix $\hat{C}_{N}$ which will be fundamental in what follows. Recall that we denoted $d_{i}=\frac{1}{N}z_{i}^{*}\hat{C}_{(i)}^{-1}z_{i}$, with $\hat{C}_{(i)}=\hat{C}_{N}-\frac{1}{n}v(\tau_{i}d_{i})\tau_{i}z_{i}z_{i}^{*}$.

There exist $d_{+}>d_{-}>0$ such that, for all large $n$ a.s.,

Let us denote $d_{\max}=\max_{1\leq i\leq n}d_{i}$ and $d_{\min}=\min_{1\leq i\leq n}d_{i}$. Take $j\in\{1,\ldots,n\}$ arbitrary and, for $0<\varepsilon<1-\phi_{\infty}^{-1}<1-c_{+}$, take $m>0$ such that for all large $n$ a.s. $\nu_{n}([m,\infty))>1-\varepsilon$ (Assumption 2–2). Then, using the fact that $v$ is non-increasing while $\psi$ is non-decreasing,

The right-hand side matrix is invertible for $n$ large since $|\{\tau_{i}\geq m\}|>nc_{+}>N$ for all large $n$ a.s. Therefore, choosing $j$ to be such that $d_{\max}=\frac{1}{N}z_{j}^{*}\hat{C}_{(j)}^{-1}z_{j}$, and using $A\succeq B\succ 0\Rightarrow B^{-1}\succeq A^{-1}$ for Hermitian $A,B$ matrices,

which can be rewritten, from the definition of $\psi$,

From Lemma 6 in the Appendix, we then have for all large $n$ a.s.

Now, since $t\mapsto t/(1+c_{N}t)$ is increasing, for all large $n$ a.s.

As $\varepsilon<1-\phi_{\infty}^{-1}$, $(1-\varepsilon)^{-1}<\phi_{\infty}$ so that, from the inequality above, we can apply $\phi^{-1}$ on both sides of (15) to obtain, for all large $n$ a.s.

from which $d_{\max}$ is uniformly bounded for all large $n$ a.s. Reverting all inequalities, we can proceed similarly with $d_{\min}$ by choosing $\varepsilon>0$ small and $M<\infty$ such that $\nu_{n}([0,M))>1-\varepsilon$ for all large $n$ a.s. (which holds from the tightness of $\nu_{n}$). This shows that $d_{\min}$ is uniformly bounded away from zero and this completes the proof.

Equipped with Lemmas 1, 2, and 3, we are now in position to develop the core of the proof. For readability, we divide the proof in two parts. In the first part, we will assume that $\tau_{1},\ldots,\tau_{n}$ have a uniformly bounded support. This will greatly simplify the calculus and will allow for a better understanding of the main arguments; in particular, the technical Assumption 3 will be irrelevant in this part. Then in a second part, we relax the boundedness assumption and fully exploit Assumption 3 in a more technical proof.

First assume $\tau_{1},\ldots,\tau_{n}\leq M$ a.s. for some $M>0$. We follow here a similar path as in (Couillet et al., 2013) but slightly more involved. Define

with $\gamma_{N}$ any value given by Lemma 1 and with $d_{i}$ still defined as $d_{i}=\frac{1}{N}z_{i}^{*}\hat{C}_{(i)}^{-1}z_{i}$. Up to labeling change, we reorder the $e_{i}$’s as $e_{1}\leq\ldots\leq e_{n}$. Our goal is to show that $e_{1}\overset{\rm a.s.}{\longrightarrow}1$ and $e_{n}\overset{\rm a.s.}{\longrightarrow}1$ (hence $\max_{1\leq i\leq n}|e_{i}-1|\overset{\rm a.s.}{\longrightarrow}0$), which we will prove by a contradiction argument.

where the inequality arises from $v$ being non-increasing and from (Horn and Johnson, 1985, Corollary 7.7.4). Similarly, for each $j$,

From Lemma 2, let now $0<\varepsilon_{n}<\gamma_{N}$, $\varepsilon_{n}\downarrow 0$, be such that, for all large $n$ a.s. and for all $j\leq n$,

In particular, since $v$ is non-increasing, taking $j=n$ in (18) and applying the left-hand inequality,

By the definition of $\psi$, this can be further rewritten

We must then have $\liminf_{n}\tau_{n}>\tau_{-}$ for some $\tau_{-}>0$ along with $\tau_{n}\leq M$ a.s. for some $M>0$ (bounded $\tau_{i}$ assumption). Then, since $\gamma_{N}$ is bounded and bounded away from zero for all large $n$ a.s., so is $\tau_{n}\gamma_{N}$. Considering a further subsequence over which $\tau_{n}\gamma_{N}\to x>0$ and $c_{N}\to c$, we then have, with $\psi_{c}(x)=\lim_{c_{N}\to c}\psi(x)$ (recall that $\psi$ depends on $c_{N}$ through $g$),

Symmetrically, we obtain that, for some $\varepsilon_{n}\downarrow 0$ and for all large $n$ a.s.

or, by uniform boundedness of the $\tau_{i}$ and $\gamma_{N}$,

Therefore, since $\gamma_{N}>\gamma_{-}$ and $\left\|\frac{1}{n}\sum_{i=1}^{n}z_{i}z_{i}^{*}\right\|<(1+\sqrt{c_{+}})^{2}$ for all large $n$ a.s. (Bai and Silverstein, 1998),

If $C_{N}\neq I_{N}$ is positive definite, remark simply that neither $d_{i}$ nor $\gamma_{N}$ are affected in their values, so that the effect of $C_{N}$ first appears in (23) with $z_{i}$ having $C_{N}\neq I_{N}$ as covariance matrix. But then, in this case, since $\|\frac{1}{n}\sum_{i=1}^{n}z_{i}z_{i}^{*}\|<(1+\sqrt{c_{+}})^{2}\limsup_{N}\|C_{N}\|<\infty$ (Assumption 2), the last arguments still hold true and the result is also proved for these $C_{N}$.

Note the importance of the assumption on $\phi$ being increasing and not simply non-decreasing (as in (Maronna, 1976)) to ensure that (22) is a strict inequality. If this were to be replaced by “$\geq 1$”, no contradiction with (21) could be evoked. There does not seem to be any easy way to work this limitation around. Similar reasons explain why Tyler robust estimator discussed in Section 5 cannot be analyzed in the same way as Maronna estimator. All the same, when $\tau_{1},\ldots,\tau_{n}$ have unbounded support with growing $n$, the left-hand side of (22) may equal one provided $\limsup_{n}\tau_{n}=\infty$, which is not excluded. For this reason, a specific treatment is necessary where the set of $\{\tau_{i}\}_{i=1}^{n}$ is split into a large bounded set of $\tau_{i}$ and a small set of large $\tau_{i}$. This is the approach followed in the second part of the proof below.

We now relax the boundedness assumption on the support of the distribution of $\tau_{1}$ and use Assumption 3 instead.

Since $\{\nu_{n}\}_{n=1}^{\infty}$ is tight, we can exhibit pairs $(\eta,M_{\eta})$ with $\eta\downarrow 0$ as $M_{\eta}\uparrow\infty$ such that, for all large $n$ a.s. $\nu_{n}((M_{\eta},\infty))<\eta$. Let us fix such a pair $(\eta,M_{\eta})$ with $\eta$ small and restrict ourselves to a subsequence where $\nu_{n}((M_{\eta},\infty))<\eta$ for all $n$. Denote $\mathcal{C}_{\eta}=\{i,\tau_{i}\leq M_{\eta}\}$ with cardinality $|\mathcal{C}_{\eta}|/n=1-\nu_{n}((M_{\eta},\infty))$.

We follow the same steps as in the previous proof but differentiating between indexes in $\mathcal{C}_{\eta}$ and indexes in $\mathcal{C}_{\eta}^{c}$. Also we denote

where $\gamma_{N}^{\eta}$ is the unique positive solution to the equation in $\gamma$

Recall first from Remark 1 that the conclusions of Lemma 1 are still valid and importantly in what follows, that $\gamma_{-}<\gamma_{N}^{\eta}<\gamma_{+}$ for some $\gamma_{-},\gamma_{+}>0$, for all large $N$ irrespective of $\eta<\eta_{0}$ for some $\eta_{0}$ small. This uniform control of $\gamma_{N}^{\eta}$ with respect to $\eta$ plays a key role here. For the moment, we do not make explicit the sufficiently small value of $\eta_{0}$ that is needed in the following; all what will matter if that we can always choose $\eta$ arbitrarily small from here.

Let $j\in\mathcal{C}_{\eta}$ and denote $\psi_{\infty}$ any upper bound on $\psi^{N}_{\infty}$ for all $N$. Then, similar to (17), with $e^{\eta}_{\bar{1}}=\min_{i\in\mathcal{C}_{\eta}}\{e^{\eta}_{i}\}$ and $e^{\eta}_{\bar{n}}=\max_{i\in\mathcal{C}_{\eta}}\{e^{\eta}_{i}\}$,

where the first inequality uses $d_{i}>d_{-}$ for all large $n$ a.s (Lemma 3). Since $e^{\eta}_{\bar{n}}=\frac{v(\tau_{\bar{n}}d_{\bar{n}})}{v(\tau_{\bar{n}}\gamma_{N}^{\eta})}=\frac{\psi(\tau_{\bar{n}}d_{\bar{n}})}{\psi(\tau_{\bar{n}}\gamma^{\eta}_{N})}\frac{\gamma^{\eta}_{N}}{d_{\bar{n}}}$, with the bounds derived previously (Remark 1 and Lemma 3), $e^{\eta}_{\bar{n}}$ is almost surely bounded and bounded away from zero for all large $n$ a.s., irrespective of $\eta$ small enough (if $\liminf_{n}\tau_{\bar{n}}=0$, the first equality ensures $\liminf_{n}e^{\eta}_{\bar{n}}>0$ while if $\limsup_{n}\tau_{\bar{n}}=\infty$, the second equality ensures $\limsup_{n}e^{\eta}_{\bar{n}}<\infty$). Thus, in particular, $e^{\eta}_{\bar{n}}>e_{-}$ for some $e_{-}>0$ for all large $n$ a.s. From this observation, for all large $n$ a.s.