Efficient Statistics, in High Dimensions, from Truncated Samples

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 N(mu, Sigma) means a samples is only revealed if it falls in some subset S of the d-dimensional Euclidean space; otherwise the samples are hidden and their count in proportion to the revealed samples is also hidden. We show that the mean mu and covariance matrix Sigma 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.

Authors

• Constantinos Daskalakis
• Themis Gouleakis
• Christos Tzamos
• Manolis Zampetakis

Keywords

• Estimation
• Gaussian distribution
• Covariance matrices
• Atmospheric measurements
• Particle measurements
• Current measurement
• Insurance
• Normal Distribution
• Covariance Matrix
• Efficient Algorithm
• Variate
• Unknown Distribution
• Arbitrary Accuracy
• Parameter Estimates
• Probability Density Function
• Proof Of Theorem
• Stochastic Gradient Descent
• Likelihood Function
• Population Model
• Fraction Of Samples
• Conditional Mean
• Statistical Estimation
• Convex Set
• Positive Semidefinite
• Subset Of Space
• Negative Log-likelihood
• Truncated Normal
• Strongly Convex
• Total Variation Distance
• Gaussian Measurement
• Drawing Samples
• Conditional Covariance
• True Parameter
• Sum Of Squares
• Frobenius Norm
• Running Time
• efficient statistics
• truncated samples
• high dimensions