LemmaStatement: AI-adaptedProof: AI-generatedPipeline-generated

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.

Expected squared operator error of thresholded sparse covariance

Statement

Fix $τ > 0$ , $0 \leq q < 1$ and $β > 1$ . Let $n \geq 1$ , $p \geq 2$ , $p \geq n^{β}$ and $a = \log (p) / n \leq 1$ . For iid observations from $P_{q} (τ, c)$ of Weak-lq covariance class with directional sub-Gaussian tails, use Entrywise-thresholded sample covariance with $λ = 8192 τ \sqrt{a}$ . There is $C = C (q, τ) < \infty$ such that $\sup_{P \in P_{q} (τ, c)} E_{P^{\otimes n}} ∥ \hat{Σ} - Σ (P) ∥_{o p}^{2} \leq C {c^{2} a^{1 - q} + a} .$ The estimator uses sample centering and divisor $n$ , including unknown means; no independence between coordinates is assumed. This is the unmodified threshold estimator, not a clipped version.

Facts & Assumptions

Given: The sample, class, dimension and threshold hypotheses in the statement.

[F1]

The directional tail is $P (∣ v^{T} (X - E X) ∣ > t) \leq e^{- t^{2} / (2 τ)}$ . Weak-lq covariance class with directional sub-Gaussian tails.

[F2]

Under the n-fold sample law $P^{\otimes n}$ , for every $u > 0$ the centered sample covariance entrywise error is at most $192 τ (\sqrt{u / n} + u / n)$ except with probability $2 p e^{- u} + 2 p^{2} e^{- 2 u}$ . Entrywise deviation for sample-centered covariance under directional Gaussian tails.

[F3]

On entrywise error at most $λ / 2$ , thresholding has operator error at most $C_{q} (c λ^{1 - q} + λ)$ . Weak-lq thresholding error from an entrywise deviation event.

[F4]

Nonnegative moments can be integrated from their tails. Layer-cake formulas for random variables.

[F5]

The algorithm uses the sample-centered covariance with divisor $n$ , keeps the diagonal and never increases the absolute value of an entry. Sample covariance estimators and squared operator loss Entrywise-thresholded sample covariance.

[F6]

Cauchy–Schwarz for square-integrable random variables gives $∣ E U V ∣ \leq (E U^{2})^{1 / 2} (E V^{2})^{1 / 2}$ , including covariance entries and an indicator of a bad event. Cauchy-Schwarz for random variables.

[F7]

Finite-sum Cauchy–Schwarz gives $∣ \sum_{j} a_{j} b_{j} ∣^{2} \leq (\sum_{j} a_{j}^{2}) (\sum_{j} b_{j}^{2})$ . The Cauchy-Schwarz inequality for finite sums.

[F8]

Finite-sum Hölder with conjugate exponents $4$ and $4 / 3$ gives $(n^{- 1} \sum_{i} y_{i})^{4} \leq n^{- 1} \sum_{i} y_{i}^{4}$ for nonnegative $y_{i}$ . Hölder's inequality for finite sums (rational exponents).

Proof

1.1givenF2F3algebra

Put $u = \log (8 p^{10}) \leq 13 \log p$ . Since $a \leq 1$ , $192 τ (\sqrt{u / n} + u / n) \leq 192 τ (\sqrt{13} + 13) \sqrt{a} < 4096 τ \sqrt{a} = λ / 2$ . The failure bound in [F2] is $1 / (4 p^{9}) + 1 / (32 p^{18}) \leq p^{- 8}$ . Thus an event $G$ has $P^{\otimes n}$ -probability at least $1 - p^{- 8}$ , and on it [F3] bounds squared loss by $C (q, τ) (c^{2} a^{1 - q} + a)$ .

1.2givenF1F4F6F7F8algebra

Write $U_{i j} = X_{i j} - E X_{i j}$ . By [F1] and [F4], $E_{P^{\otimes n}} ∣ U_{i j} ∣^{8} \leq (2 τ)^{4} 4! = 384 τ^{4}$ . Also, for unit $v$ , $v^{T} Σ v \leq \int_{0}^{\infty} e^{- t / (2 τ)} d t = 2 τ$ ; applying [F6] to centered coordinates gives $∣ σ_{j k} ∣ \leq 2 τ$ . The sample-centered diagonal obeys $0 \leq {\hat{σ}}_{j j}^{*} \leq n^{- 1} \sum_{i} U_{i j}^{2}$ . Applying [F7] to the two centered coordinate sample vectors gives $∣ {\hat{σ}}_{j k}^{*} ∣^{2} \leq {\hat{σ}}_{j j}^{*} {\hat{σ}}_{k k}^{*}$ . Therefore $E_{P^{\otimes n}} ∣ {\hat{σ}}_{j k}^{*} ∣^{4} \leq \frac{1}{2} E_{P^{\otimes n}} [({\hat{σ}}_{j j}^{*})^{4} + ({\hat{σ}}_{k k}^{*})^{4}] \leq 384 τ^{4},$ where the final inequality uses [F8] with $y_{i} = U_{i j}^{2}$ (and likewise for $k$ ). These bounds are independent of the unknown means.

2.1givenF5F6F7step 1.1step 1.2algebra∎

By [F5], $E_{P^{\otimes n}} ∣ {\hat{σ}}_{j k} - σ_{j k} ∣^{4} \leq 8 E_{P^{\otimes n}} (∣ {\hat{σ}}_{j k}^{*} ∣^{4} + ∣ σ_{j k} ∣^{4}) \leq C τ^{4}$ . For any matrix $A$ , [F7] gives $∥ A ∥_{o p}^{2} \leq \sum_{j k} ∣ A_{j k} ∣^{2}$ by applying finite Cauchy–Schwarz to each row against a unit vector; [F7] also gives $(\sum_{j k} ∣ A_{j k} ∣^{2})^{2} \leq p^{2} \sum_{j k} ∣ A_{j k} ∣^{4}$ . Thus $E_{P^{\otimes n}} ∥ \hat{Σ} - Σ ∥_{o p}^{4} \leq C τ^{4} p^{4}$ . Applying [F6] to $∥ \hat{Σ} - Σ ∥_{o p}^{2}$ and $1_{G^{c}}$ and using step 1.1 gives $E_{P^{\otimes n}} [∥ \hat{Σ} - Σ ∥_{o p}^{2}; G^{c}] \leq C τ^{2} p^{2} p^{- 4} = C τ^{2} p^{- 2} .$ Since $p \geq n^{β}$ implies $n \leq p^{1 / β} \leq p$ and $1 / p \leq \log p$ , we have $p^{- 2} \leq \log p / n = a$ . Adding the good-event bound proves the claim uniformly over the class.

Depends on

Used by

Capped thresholded minimax rate for weak-lq sparse covariance Theorem

Dependency tree · two levels

57 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

Cai and Zhou, Optimal Rates of Convergence for Sparse Covariance Matrix Estimation (standard reference, not scraped)