6
$\begingroup$

(also asked on math.se, with no answers)

Suppose I have $m$ samples drawn from a Gaussian in $\mathbb{R}^n$, and need sample covariance $\Sigma_m$ to be $\epsilon$-close to true covariance $\Sigma$:

$$E\|\Sigma_m-\Sigma\| \le \epsilon \|\Sigma\|$$

Vershynin (High-Dimensional Probability Remark 5.6.3) gives the following sample requirement for arbitrary distribution in terms of intrinsic dimension $r=\text{tr}\ \Sigma/\|\Sigma\|$ $$m \approx \epsilon^{-2} r \log n$$

Is there a tighter bound for the Gaussian case? In particular, I'm wondering if $\log n$ term can be dropped

A simulation is here, it seems if we keep intrinsic dimensionality fixed, and sample size fixed, the error doesn't grow with dimensions.

enter image description here

notebook

Improve this question
$\endgroup$
7
  • $\begingroup$ If you want a bound that is as tight as possible, you certainly need to use the peculiarities of the Gaussian case. Did you have a look into the Wishart distribution and how it concentrates around its mean ? I do not believe that you can get rid of the dimension. $\endgroup$
    – Gilles Mordant
    Commented Jun 14, 2021 at 12:06
  • $\begingroup$ For a Gaussian with covariance a multiple of identity, you can drop the $\log n$ part, so the sample complexity becomes dependent only on the intrinsic dimension $r$ and not on the ambient dimension $n$ $\endgroup$
    – Yaroslav Bulatov
    Commented Jun 14, 2021 at 16:55
  • $\begingroup$ Sure. For your question to be clearer, it might be better to state that dimension-free in your question refers to the ambient space and not the intrinsic dimension. Note also that the case you are referring to is extremely restrictive. What set of matrices $\Sigma$ do you want to consider ? $\endgroup$
    – Gilles Mordant
    Commented Jun 15, 2021 at 14:04
  • $\begingroup$ I agree terminology could be ambiguous. I first saw "dimension-free" used in this way in Nick Harvey's notes cs.ubc.ca/~nickhar/W12/Lecture15Notes.pdf . Without context perhaps a better way would have been to say "depending on effective dimension, independent of ambient dimension". $\endgroup$
    – Yaroslav Bulatov
    Commented Jun 15, 2021 at 20:59
  • 2
    $\begingroup$ Unless I'm missing something, doesn't Vershynin's Theorem 9.2.4 address this? $\endgroup$
    – Jason Gaitonde
    Commented Aug 4, 2022 at 3:28

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .