Robust Covariance and Sparse Robust Estimation — Examples

In ${\mathbb{R}}^2$, let $Z$ take values $\pm \sqrt{4\mathrm{/}3}{e}_1$ with total probability $3\mathrm{/}4$ (each sign has probability $3\mathrm{/}8$), and $\pm \sqrt{2}{e}_2$ with total probability $1\mathrm{/}4$ (each sign has probability $1\mathrm{/}8$). Symmetry gives $\mathbb{E}Z=0$, and finite support gives a finite fourth moment.

Direct summation and [F1] give $\mathrm{\Sigma }=\mathbb{E}[Z{Z}^T]=\mathrm{diag}(1,1\mathrm{/}2)$, hence $\mathrm{tr}(\mathrm{\Sigma })=3\mathrm{/}2$ and $\mathrm{\parallel }\mathrm{\Sigma }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}=1$ by [F4].

The value of $\mathrm{\parallel }Z{\mathrm{\parallel }}_2^2$ is $4\mathrm{/}3$ on the first pair and $2$ on the second, so $\mathbb{E}[\mathrm{\parallel }Z{\mathrm{\parallel }}_2^{2}Z{Z}^T]=\mathrm{diag}\text{\hspace{0.17em}⁣}(\frac{3}{4}{\left(\frac{4}{3}\right)}^2,\frac{1}{4}(2{)}^2)=\mathrm{diag}(4\mathrm{/}3,1)\mathrm{.}$ Its operator norm is $4\mathrm{/}3<3\mathrm{/}2=\mathrm{tr}(\mathrm{\Sigma })\mathrm{\parallel }\mathrm{\Sigma }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$ by [F4]. Thus the statement is false.

By [F1], $P$ is a measure, and its total mass is $\zeta (6{)}^{-1}{\sum }_{k=1}^{\mathrm{\infty }}{k}^{-6}=1$ by [F5]. Thus [F2] makes $P$ a probability measure. The identity map is the real random variable specified by [F3], and $P(X=\pm k)=1\mathrm{/}(2\zeta (6)k^6)$ for each $k\ge 1$.

For $q=2$ and $q=4$, the truncations $Y_N=\mathrm{\mid }X{\mathrm{\mid }}^q{\mathbf{1}}_{\{\mathrm{\mid }X\mathrm{\mid }\le N\}}$ are nonnegative simple functions increasing to $\mathrm{\mid }X{\mathrm{\mid }}^q$. By [F4] and the finite atom masses, $\mathbb{E}\mathrm{\mid }X{\mathrm{\mid }}^q={\lim }_{N\to \mathrm{\infty }}\mathbb{E}{Y}_N=\frac{1}{\zeta (6)}{\sum }_{k=1}^{\mathrm{\infty }}{k}^{q-6}=\frac{\zeta (6-q)}{\zeta (6)}<\mathrm{\infty },$ where convergence is [F5]. In particular $X$ is integrable by [F7], and its symmetric atom masses give $\mathbb{E}X=0$.

By [F6], the covariance is $\mathrm{\Sigma }=\zeta (4)\mathrm{/}\zeta (6)>0$, while the scalar matrix variance is ${\sigma }_0^2=\zeta (2)\mathrm{/}\zeta (6)<\mathrm{\infty }$. Therefore $d=\frac{{\sigma }_0^2}{{\mathrm{\Sigma }}^2}=\frac{\zeta (2)\zeta (6)}{\zeta (4{)}^2}$ is finite and positive.

Fix $t>0$. The simple truncations $W_N=e^{t\mathrm{\mid }X\mathrm{\mid }}{\mathbf{1}}_{\{\mathrm{\mid }X\mathrm{\mid }\le N\}}$ increase to $e^{t\mathrm{\mid }X\mathrm{\mid }}$, so [F4] gives $\mathbb{E}{e}^{t\mathrm{\mid }X\mathrm{\mid }}=\frac{1}{\zeta (6)}{\sum }_{k=1}^{\mathrm{\infty }}{e}^{tk}{k}^{-6}=+\mathrm{\infty }\mathrm{.}$ Indeed the ratio of successive summands is $e^t(k\mathrm{/}(k+1){)}^6\to e^t>1$, so the summands do not tend to zero and the series diverges. The law has polynomially decaying atom masses, finite matrix variance, and no finite positive exponential moment.

The constant zero-matrix estimator is Borel, since the inverse image of any Borel set is either the entire sample space or empty. For every target in the class its squared operator loss is $\mathrm{\parallel }0-\mathrm{\Sigma }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}^2=\mathrm{\parallel }\mathrm{\Sigma }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}^2\le M^2$ by [F1]–[F2], for every possible observation and every contaminant.

By [F3], choose an integer $p>M^2\mathrm{/}{C}_M$, and take $n=1$, $ϵ=0$. The proposed threshold is $C_{M}p>M^2$, so the tail event for the zero estimator is empty under every target and contaminant by step 1.1. Its worst-case probability, hence the nonnegative minimax infimum, is zero, contradicting $c_0>0$. Thus an uncapped all-dimension lower rate is false; the bounded loss requires a cap such as $\min \{1,(p\mathrm{/}n)\vee {ϵ}^2\}$ in a valid matching lower statement.

Fix $\beta =10$, so $k=36$, and choose a fixed integer $m$ arbitrarily large with $m\ge 2C\beta$, $b_{\min }=\lfloor m\mathrm{/}k\rfloor \ge 2$, $k(2\mathrm{/}3{)}^{b_{\min }}<1\mathrm{/}100$ and $18\sqrt{2\beta \mathrm{/}m}<1\mathrm{/}2$. For each $p\ge 2$, set ${\lambda }_1=1$, ${\lambda }_j=p^{-1\mathrm{/}2}$ for $j\ge 2$, $S_p={\sum }_j{\lambda }_j^2=2-1\mathrm{/}p$, and $q_j={\lambda }_j^2\mathrm{/}{S}_p$. Let $X$ take $\pm \sqrt{{\lambda }_j\mathrm{/}{q}_j}{e}_j$, each with probability $q_j\mathrm{/}2$. It is centered and finitely supported. Direct summation gives ${\mathrm{\Sigma }}_p=\mathrm{diag}({\lambda }_j)$, $\mathrm{\parallel }{\mathrm{\Sigma }}_p{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}=1$, $E[\mathrm{\parallel }X{\mathrm{\parallel }}^{2}X{X}^{\mathsf{T}}]=S_p{I}_p$ and ${\sigma }_0^2=d=S_p<2$. Thus $m\ge Cd\beta$ for all $p$, but $\mathrm{tr}{\mathrm{\Sigma }}_p\to \mathrm{\infty }$. Tail-axis observations $j\ge 2$ have common squared radius $R_p^2=S_p\sqrt{p}$.

Let $E_p$ be the event that every block contains at least one tail-axis draw and that all sampled tail axes are distinct. A block has no tail draw with probability $(1\mathrm{/}{S}_p{)}^{b_j}$; conditional tail-axis labels are uniform on $p-1$ coordinates. Union bounds give $P(E_p)\ge 1-k(1\mathrm{/}{S}_p{)}^{b_{\min }}-m(m-1)\mathrm{/}(2(p-1))>49\mathrm{/}50$ for large $p$. Every geometric median of finite points lies in their convex hull: if $x$ lies outside that compact hull and $z$ is a closest hull point, differentiating the squared distance along the segment from $z$ to any hull point $q$ gives $⟨x-z,q-z⟩\le 0$. Expanding the square then gives $\mathrm{\parallel }x-q{\mathrm{\parallel }}^2\ge \mathrm{\parallel }x-z{\mathrm{\parallel }}^2+\mathrm{\parallel }z-q{\mathrm{\parallel }}^2>\mathrm{\parallel }z-q{\mathrm{\parallel }}^2$, so replacing $x$ by $z$ strictly reduces every summand, contradicting median minimality. Write therefore $\widehat{\mu }={\sum }_l{w}_l{M}_l$ with $w_l\ge 0$, ${\sum }_l{w}_l=1$. On $E_p$ the tail parts of the block means have disjoint supports and norms at least $R_p\mathrm{/}{b}_{\max }$, where $b_{\max }=\lceil m\mathrm{/}k\rceil$. Thus $\mathrm{\parallel }{\widehat{\mu }}_{\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{l}}{\mathrm{\parallel }}^2\ge R_p^2{\sum }_l{w}_l^2\mathrm{/}{b}_{\max }^{}\ge R_p^2\mathrm{/}(k{b}_{\max }^{})$, and $\mathrm{\mid }{\widehat{\mu }}_1\mathrm{\mid }\le \sqrt{S_p}$.

For an axis-one sample, $\mathrm{\parallel }{X}_i-\widehat{\mu }{\mathrm{\parallel }}^2\ge \mathrm{\parallel }{\widehat{\mu }}_{\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{l}}{\mathrm{\parallel }}^2$. For a tail draw in block $l$, its unique tail coordinate in the pilot is exactly $w_l\mathrm{/}{b}_l$ times its sample coordinate, so the difference has magnitude at least $R_p(1-w_l\mathrm{/}{b}_l)\ge R_p\mathrm{/}2$. Hence uniformly in $i$, $\mathrm{\parallel }{X}_i-\widehat{\mu }{\mathrm{\parallel }}^2\ge c_m{R}_p^2$, with $c_m=\min \{1\mathrm{/}(k{b}_{\max }^{}),1\mathrm{/}4\}>0$, whereas $\mathrm{\mid }(X_i-\widehat{\mu }{)}_1\mathrm{\mid }\le 2\sqrt{S_p}$. Choose the exact scale bracket ${\sigma }_{\min }={\sigma }_{\max }={\sigma }_0=\sqrt{S_p}$. Its grid is $\{0\}$, so adaptive and fixed-scale estimates coincide. With $\theta ={\sigma }_0^{-1}\sqrt{\beta \mathrm{/}m}$, all centered samples are clipped for large $p$, and their rank-one formula gives $e_1^{\mathsf{T}}\widehat{\mathrm{\Sigma }}{e}_1\le 4S_p\mathrm{/}(\theta c_m{R}_p^2)=4\mathrm{/}(\theta c_m\sqrt{p})\to 0$. The true entry is one, so operator error exceeds $1\mathrm{/}2$ on $E_p$ eventually. Both claimed thresholds are below $1\mathrm{/}2$ by step 1.1, whereas their claimed failure budget is $5d{e}^{-10}<10e^{-10}<1\mathrm{/}1000$. This contradicts $P(E_p)>49\mathrm{/}50$. Since $m$ was chosen after an arbitrary proposed $C$, no universal such $C$ exists.

To obtain a nonvacuous contradiction even with the corrected ambient prefactor, let an integer $b\to \mathrm{\infty }$ satisfy $b\ge C$, and take ${\beta }_b=2^{b\mathrm{/}2}\mathrm{/}100$, $k_b=\lfloor (7\mathrm{/}2){\beta }_b\rfloor +1$, $m_b=k_{b}b$ and $p_b=\lceil e^{{\beta }_b\mathrm{/}2}\rceil$. These satisfy ${\beta }_b>1$ eventually, $m_b>(7\mathrm{/}2)b{\beta }_b\ge Cd{\beta }_b$ and balanced blocks all of size $b$. The no-tail-block error in step 2.1 is at most $(9\mathrm{/}2){\beta }_b(2\mathrm{/}3{)}^b=(9\mathrm{/}200)(2\sqrt{2}\mathrm{/}3{)}^b\to 0$; the collision error is $O({\beta }_b^2{b}^2{e}^{-{\beta }_b\mathrm{/}2})\to 0$. Here $c_{m_b}=1\mathrm{/}(k_b{b}^2)$ eventually and $1\mathrm{/}\theta =\sqrt{S_{p_b}{k}_{b}b\mathrm{/}{\beta }_b}=O(\sqrt{b})$. Thus the upper bound for the estimated leading entry in step 3.1 is $O({\beta }_b{b}^{5\mathrm{/}2}{e}^{-{\beta }_b\mathrm{/}4})\to 0$, whereas its true entry remains one. The larger advertised error radius is at most $18\sqrt{4\mathrm{/}(7b)}\to 0$, while $5p_b{e}^{-{\beta }_b}\le 10e^{-{\beta }_b\mathrm{/}2}\to 0$. Both failures therefore occur with probability tending to one even though the ambient-prefactor bound would require it to tend to zero. Each asserted vanishing follows since ${\beta }_b$ grows exponentially in $b$ and $e^{-c{\beta }_b}$ dominates every fixed power of ${\beta }_b,b$; taking logarithms proves these limits directly. This also disproves the dimension-uniform source-shaped guarantee under only $m\ge Cd\beta$.

The only nonzero off-diagonal entries of $\mathrm{\Sigma }$ are ${\mathrm{\Sigma }}_{12}={\mathrm{\Sigma }}_{21}=1\mathrm{/}4$, both supported in $S=\{1,2\}$. Its eigenvalues are $5\mathrm{/}4,3\mathrm{/}4,1,1$, so $\mathrm{\Sigma }⪰0$ and $\mathrm{\parallel }\mathrm{\Sigma }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}=5\mathrm{/}4\le M$ by [F4]. Since $\mathrm{\Sigma }$ is symmetric, these checks give $\mathrm{\Sigma }\in {\mathcal{F}}_4(2)$ and, with the support check, $\mathrm{\Sigma }\in {\mathcal{F}}_{4,2}(2)$ by [F1].

The contaminant $Q={\delta }_0$ is a probability measure by [F5], and $ϵ\in [0,1]$. The mixture is a well-defined Huber model by [F2] and [F3]. The structure is one correlated block; it does not assert the column-wise weak-${\mathrm{\ell }}_q$ sparsity condition from the separate sparse covariance model.

The eigenvalues of $\mathrm{\Sigma }$ are $5\mathrm{/}4$ and $3\mathrm{/}4$, so $\mathrm{\Sigma }$ is positive definite and $\mathrm{\parallel }\mathrm{\Sigma }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}=5\mathrm{/}4\le 2$ by [F4]. Thus $\mathrm{\Sigma }\in {\mathcal{F}}_2(2)$.

The Dirac law $Q={\delta }_{(2,0)}$ is a probability measure by [F5], and $0<ϵ<1$. By [F1] and [F3], $P_{ϵ,\mathrm{\Sigma },Q}$ is a well-defined Huber sampling law. The target remains the clean Gaussian covariance $\mathrm{\Sigma }$, not the covariance of the mixture.