Efficient Statistics, in High Dimensions, from Truncated Samples
This solves a long-standing statistical problem with applications in fields like censored data analysis, but it is incremental as it builds on prior work by Galton, Pearson, and Fisher.
The paper tackles the classical problem of estimating parameters of a multivariate normal distribution from truncated samples, where samples are only revealed if they fall in a subset S, and shows that the mean and covariance matrix can be estimated with arbitrary accuracy in polynomial-time given oracle access to S, but estimation is impossible without such access.
We provide an efficient algorithm for the classical problem, going back to Galton, Pearson, and Fisher, of estimating, with arbitrary accuracy the parameters of a multivariate normal distribution from truncated samples. Truncated samples from a $d$-variate normal ${\cal N}(\mathbfμ,\mathbfΣ)$ means a samples is only revealed if it falls in some subset $S \subseteq \mathbb{R}^d$; otherwise the samples are hidden and their count in proportion to the revealed samples is also hidden. We show that the mean $\mathbfμ$ and covariance matrix $\mathbfΣ$ can be estimated with arbitrary accuracy in polynomial-time, as long as we have oracle access to $S$, and $S$ has non-trivial measure under the unknown $d$-variate normal distribution. Additionally we show that without oracle access to $S$, any non-trivial estimation is impossible.