LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Operator error bound for the Gaussian Huber matrix-depth estimator

Statement

Let $X_{1}, \dots, X_{n}$ be independent with common law $P_{ϵ, Σ, Q}$ from Gaussian Huber contamination model for covariance estimation, where $Σ \in F_{p} (M)$ , $0 \leq ϵ < 1 / 5$ , $Q$ is arbitrary, and $M > 0$ is fixed. Let $\hat{Γ}$ be a Borel measurable positive semidefinite symmetric matrix-valued statistic satisfying $D_{U} (\hat{Γ}, P_{n}) \geq D_{U} (β Σ, P_{n})$ for every sample. This includes every measurable global maximizer and every measurable maximizer over a compact search class containing $β Σ$ . For a direction family $U = ⋃_{j = 1}^{m} V_{S_{j}}$ with $m \geq 1$ , nonempty $S_{j} \subseteq [p]$ , integer $r \geq 1$ , and $∣ S_{j} ∣ \leq r$ , assume $0 < δ < 1 / 2$ and $C_{1} (r + \log (m / δ)) / n < 1$ for a sufficiently large universal $C_{1}$ . Then, uniformly over $Q$ and $Σ$ , $\sup_{u \in U} ∣ u^{T} (\hat{Γ} / β - Σ) u ∣ \leq C_{M} (ϵ + \sqrt{\frac{r + \log (m / δ)}{n}})$ with probability at least $1 - 2 δ$ . Here $C_{M}$ depends only on the fixed spectrum bound $M$ .

This is a comparison bound. Existence of selectors is separate from this argument; the dense and block-sparse global and bounded-class selectors are proved in the local selection lemma.

Facts & Assumptions

Given: The Gaussian Huber model, a Borel measurable positive semidefinite statistic satisfying the displayed empirical-depth comparison, and the sample-size and confidence conditions in the Statement.

[F1]

Matrix depth and covariance estimators: empirical depth uses both weak tails. The displayed comparison premise applies in particular to a global maximizer or to a maximizer over a class containing $β Σ$ .

[F2]

The scaled Gaussian covariance has matrix depth at least one half: $D_{U} (β Σ, N_{p} (0, Σ)) \geq 1 / 2$ , including singular directions.

[F3]

Uniform deviation for squared-projection slabs: for $N$ clean independent observations, both squared-projection tail classes over $m$ supports of size at most $r$ have uniform empirical error at most $C [\sqrt{(r + 1) / N} + \sqrt{\log (m / δ) / N}]$ with probability at least $1 - δ$ .

[F4]

Standard normal and normal laws and The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ : the standard-normal density is positive and continuous, so its inverse CDF is locally Lipschitz on compact subintervals of $(0, 1)$ .

[F5]

Multivariate normal law, including singular covariance: if $u^{T} Σ u = 0$ , then the clean Gaussian projection $u^{T} X$ has law $N (0, 0) = δ_{0}$ .

[F6]

Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis and The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||: for symmetric $B$ , the map $B \mapsto \sup_{u \in U} ∣ u^{T} B u ∣$ is 1-Lipschitz in operator norm for every nonempty $U$ of unit vectors.

[F7]

A measurable function between measurable spaces and Composition with a Borel measurable outer map preserves measurability: composing a Borel selector with a continuous real-valued function gives a Borel random variable.

Proof

1.1givenalgebra

Expand the finite product mixture law using independent contamination labels. The contaminated count $n_{2}$ is binomial. For a Bernoulli variable $B$ with mean $ϵ$ , the centered log-mgf $g (λ) = \log E e^{λ (B - ϵ)}$ satisfies $g (0) = g^{'} (0) = 0$ and $g^{''} (λ)$ is a variance of a tilted Bernoulli law, hence at most $1 / 4$ . Integrating twice gives $g (λ) \leq λ^{2} / 8$ ; Chernoff optimization gives $n_{2} / n \leq ϵ + \sqrt{\log (1 / δ) / (2 n)}$ except on an event of probability $δ$ . Put $q = r + \log (m / δ)$ . Since $C_{1} q / n < 1$ and $C_{1} \geq 200$ , the square-root term is at most $1 / 20$ . Thus $n_{2} / n < 1 / 4$ and $n_{1} = n - n_{2} > 3 n / 4$ .

1.2givenF3

Conditional on the label pattern and clean count $n_{1}$ , the clean observations $Y_{1}, \dots, Y_{n_{1}}$ are independent with law $N_{p} (0, Σ)$ . Apply [F3] with confidence $δ$ . Except on a conditional event of probability $δ$ , every clean empirical tail differs from its Gaussian probability by at most $e = C [\sqrt{(r + 1) / n_{1}} + \sqrt{\log (m / δ) / n_{1}}]$ .

2.1F1step 1.2algebra

For fixed $Γ$ and $u$ , each full-sample tail count lies between the corresponding clean count and that count plus $n_{2}$ . Taking the minimum of the two tails and then the infimum over $u$ yields $n D_{U} (Γ, P_{n}) \leq n_{1} D_{U} (Γ, P_{n_{1}}^{Y}) + n_{2}, n D_{U} (Γ, P_{n}) \geq n_{1} D_{U} (Γ, P_{n_{1}}^{Y}) .$ Since $D_{U} (\hat{Γ}, P_{n}) \geq D_{U} (β Σ, P_{n})$ by the comparison premise, these inequalities imply $D_{U} (\hat{Γ}, P_{n_{1}}^{Y}) \geq D_{U} (β Σ, P_{n_{1}}^{Y}) - n_{2} / n_{1}$ .

3.1F2step 1.1step 1.2step 2.1algebra

On the deviation event in step 1.2, replacing clean empirical depth by population depth costs at most $e$ at each matrix. [F2] and the comparison in step 2.1 therefore imply $D_{U} (\hat{Γ}, N_{p} (0, Σ)) \geq 1 / 2 - n_{2} / n_{1} - 2 e$ . Since $r \geq 1$ , $r + 1 \leq 2 q$ and $\log (m / δ) \leq q$ , we have $e \leq C (\sqrt{2} + 1) \sqrt{q / n_{1}} \leq C (\sqrt{2} + 1) \sqrt{4 / (3 C_{1})}$ . Choose $C_{1}$ large enough that $e \leq 1 / 24$ . Step 1.1 gives $n_{2} / n_{1} \leq 1 / 3$ . Retain the actual deficit $ρ : = n_{2} / n_{1} + 2 e \leq 5 / 12 < 1 / 2$ . Also $n_{1} > 3 n / 4$ and step 1.1 give $n_{2} / n_{1} \leq (4 / 3) (ϵ + \sqrt{\log (1 / δ) / (2 n)})$ , while $e \leq C \sqrt{q / n}$ ; hence $ρ \leq C (ϵ + \sqrt{q / n})$ .

4.1F1F2F4step 3.1algebra

Fix $u \in U$ and put $v = u^{T} Σ u$ . If $v > 0$ , let $z = u^{T} \hat{Γ} u / v \geq 0$ . The Gaussian tails at threshold $u^{T} \hat{Γ} u$ are $2 Φ (\sqrt{z}) - 1$ and $2 - 2 Φ (\sqrt{z})$ ; their minimum is $1 / 2 - 2 ∣ Φ (\sqrt{z}) - 3 / 4 ∣$ . Step 3.1 therefore gives $∣ Φ (\sqrt{z}) - Φ (\sqrt{β}) ∣ \leq ρ / 2$ . The bound $ρ \leq 5 / 12$ places both Gaussian probabilities in the fixed compact interval $[13 / 24, 23 / 24] \subset (0, 1)$ . On this interval [F4] gives $∣ \sqrt{z} - \sqrt{β} ∣ \leq C ρ$ and then $∣ z - β ∣ \leq C ρ$ . Since $u^{T} (\hat{Γ} / β - Σ) u = (v / β) (z - β)$ and $v \leq M$ , this implies $∣ u^{T} (\hat{Γ} / β - Σ) u ∣ \leq C_{M} ρ \leq C_{M} (ϵ + \sqrt{q / n})$ .

5.1F1F5F6F7step 1.1step 1.2step 3.1algebra∎

If $v = 0$ , [F5] gives $u^{T} X = 0$ almost surely. If $u^{T} \hat{Γ} u > 0$ , the upper weak tail is zero, contradicting the positive depth lower bound in step 3.1. Hence $u^{T} \hat{Γ} u = 0$ and the quadratic error is zero. Taking the supremum over $U$ is a Borel function of the Borel selector by [F6, F7]; its Lipschitz bound follows by applying the operator-norm inequality to the difference of two candidate matrices. Intersecting the events from steps 1.1–1.2 gives probability at least $1 - 2 δ$ and the stated bound.

Depends on

Used by

Dependency tree · two levels

78 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Mengjie Chen, Chao Gao and Zhao Ren, Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model, Theorem 7.1 and proofs of Theorems 3.1 and 3.6 (standard reference, not scraped)