Skip to main content
added 19 characters in body; edited title
Source Link
Michael Hardy
  • 1
  • 12
  • 85
  • 126

Dimension free-free sample complexity for the inverse of Gaussian sample covariance?

Suppose I have $m$ samples drawn from a Gaussian in $\mathbb{R}^n$, and need the inverse of the sample covariance $\Sigma_m^{-1}$ to be $\epsilon$$\varepsilon$-close to true inverse covariance $\Sigma^{-1}$ (in expectation or (preferably) with high probability):

$$||\Sigma^{-1}_m-\Sigma^{-1}|| \le \epsilon ||\Sigma^{-1}||$$$$\|\Sigma^{-1}_m-\Sigma^{-1}\| \le \varepsilon \|\Sigma^{-1}\|$$

For the sample covariance it is known that $$||\Sigma_m-\Sigma|| \le \epsilon ||\Sigma||$$$$\|\Sigma_m-\Sigma\| \le \varepsilon \|\Sigma\|$$ can be achieved with $r=\text{tr}\ \Sigma/||\Sigma||$$r=\operatorname{tr} \Sigma/\|\Sigma\|$ (the intrinsic dimension) $$m \approx \epsilon^{-2} r$$$$m \approx \varepsilon^{-2} r$$

I wonder if there is anything similar for the inverse covariance?

Dimension free sample complexity for the inverse of Gaussian sample covariance?

Suppose I have $m$ samples drawn from a Gaussian in $\mathbb{R}^n$, and need the inverse of the sample covariance $\Sigma_m^{-1}$ to be $\epsilon$-close to true inverse covariance $\Sigma^{-1}$ (in expectation or (preferably) with high probability):

$$||\Sigma^{-1}_m-\Sigma^{-1}|| \le \epsilon ||\Sigma^{-1}||$$

For the sample covariance it is known that $$||\Sigma_m-\Sigma|| \le \epsilon ||\Sigma||$$ can be achieved with $r=\text{tr}\ \Sigma/||\Sigma||$ (the intrinsic dimension) $$m \approx \epsilon^{-2} r$$

I wonder if there is anything similar for the inverse covariance?

Dimension-free sample complexity for the inverse of Gaussian sample covariance?

Suppose I have $m$ samples drawn from a Gaussian in $\mathbb{R}^n$, and need the inverse of the sample covariance $\Sigma_m^{-1}$ to be $\varepsilon$-close to true inverse covariance $\Sigma^{-1}$ (in expectation or (preferably) with high probability):

$$\|\Sigma^{-1}_m-\Sigma^{-1}\| \le \varepsilon \|\Sigma^{-1}\|$$

For the sample covariance it is known that $$\|\Sigma_m-\Sigma\| \le \varepsilon \|\Sigma\|$$ can be achieved with $r=\operatorname{tr} \Sigma/\|\Sigma\|$ (the intrinsic dimension) $$m \approx \varepsilon^{-2} r$$

I wonder if there is anything similar for the inverse covariance?

Source Link
axk
  • 517
  • 2
  • 8

Dimension free sample complexity for the inverse of Gaussian sample covariance?

Suppose I have $m$ samples drawn from a Gaussian in $\mathbb{R}^n$, and need the inverse of the sample covariance $\Sigma_m^{-1}$ to be $\epsilon$-close to true inverse covariance $\Sigma^{-1}$ (in expectation or (preferably) with high probability):

$$||\Sigma^{-1}_m-\Sigma^{-1}|| \le \epsilon ||\Sigma^{-1}||$$

For the sample covariance it is known that $$||\Sigma_m-\Sigma|| \le \epsilon ||\Sigma||$$ can be achieved with $r=\text{tr}\ \Sigma/||\Sigma||$ (the intrinsic dimension) $$m \approx \epsilon^{-2} r$$

I wonder if there is anything similar for the inverse covariance?