Covariance Estimation Without Logarithmic Oversampling

Definitions and mathematical statement

Let $n\geq 1$ and let $X$ be an ${\mathbb{R}}^n$-valued random vector with ${\mathbb{E}} X=0$ and ${\mathbb{E}}\|X\|_2^2<\infty$. Define its covariance matrix by \[ \Sigma={\mathbb{E}}[XX^{\mathsf T}]. \] For independent copies $X_1,\ldots,X_N$ of $X$, use the known-mean empirical covariance convention \[ \Sigma_N=\frac{1}{N}\sum_{i=1}^N X_iX_i^{\mathsf T},\qquad N\geq 1. \] For a matrix $A$, write $\|A\|_{\mathrm{op}}=\sup_{\|u\|_2=1}\|Au\|_2$. The source does not explicitly define the matrix norm or specify whether empirical centering is used; the displayed definitions make the operator-norm, known-mean interpretation explicit.

The supplied problem asks for a characterization of distributions for which, at prescribed accuracy $\eta>0$, \[ {\mathbb{E}}\|\Sigma_N-\Sigma\|_{\mathrm{op}} \leq \eta\|\Sigma\|_{\mathrm{op}} \] can be achieved with sample size linear in the dimension, $N=O(n)$, without logarithmic oversampling. The expectation is over the independent sample. If $\Sigma=0$, then $X=0$ almost surely and the displayed criterion holds for every $N\geq1$.

A precise dimension-uniform formulation requires a specified family $\mathcal P=(\mathcal P_n)_{n\geq1}$, where $\mathcal P_n$ consists of mean-zero laws on ${\mathbb{R}}^n$ with finite second moments. One possible explicit formulation of the requested property is \[ \forall\eta>0\ \exists C_{\eta,\mathcal P}\in[1,\infty)\ \forall n\geq1\ \forall P\in\mathcal P_n:\quad {\mathbb{E}}_P\left\|\Sigma_{\lceil C_{\eta,\mathcal P}n\rceil}-\Sigma_P\right\|_{\mathrm{op}} \leq\eta\|\Sigma_P\|_{\mathrm{op}}, \] where $\Sigma_P$ is the covariance of $P$ and the empirical matrix uses independent samples from $P$. This is a formulation template: the supplied record does not specify the family or the permitted dependence of the constant on distributional parameters, so it does not uniquely determine this uniform assertion.

The particular question in the source is whether having $2+\delta$ moments, for some $\delta>0$, suffices for linear sample size. Mere moment finiteness can be expressed, in each fixed dimension, as \[ {\mathbb{E}}\|X\|_2^{2+\delta}<\infty. \] The source does not specify a uniform moment bound, normalization, marginal or projection regularity condition, or whether $\delta$ is fixed across dimensions. These missing qualifications are part of the unresolved formulation. The symbols $\eta$ and $\delta$ distinguish approximation accuracy from excess moment order; the source uses $\varepsilon$ for both without stating whether they are linked.

Short English statement

Characterize mean-zero random-vector distributions whose covariance can be estimated in expected operator norm, to prescribed relative accuracy, using a number of independent samples proportional to the dimension. The source particularly asks whether $2+\delta$ moments suffice. A precise uniform claim requires clarification of the moment assumptions and the allowed dependence of the sample-size constant.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30001779$, source problem code catalogue entry, titled Covariance Estimation Without Logarithmic Oversampling; collection: Oberwolfach Reports Open Problems. The record gives the proposed year as 2011 and names no individual proposer.
• Supplied report citation: Random Matrices, Geometric Functional Analysis and Algorithms (2011), Oberwolfach Reports, pp. 1287--1360, DOI 10.4171/owr/2011/24. Original report link: https://doi.org/10.4171/owr/2011/24. No problem-specific page is supplied.
• Supplied literature source labeled "covariance estimation theorem": https://doi.org/10.1214/12-AOP760. The supplied assessment attributes to Srivastava--Vershynin a linear-sample-size result under uniform $2+\varepsilon$ marginal regularity, describing it as resolving an important regime while leaving an "unrestricted almost-never conjecture" unresolved. The record supplies neither the exact regularity hypothesis nor a definition of that conjecture phrase.
• Literature assessment date: 2026-08-21. The supplied status is partially_solved. This is supplied dated curation, not an independently verified literature assessment; the record itself requests independent verification of time-sensitive status and cited claims.
• The supplied statement status is corrected_verified. Its verification note reports that the official report was checked and that the random-vector setup, empirical covariance criterion, and linear-sample-size question were restored. This draft preserves that supplied provenance claim without claiming an independent source visit or verification.