Efficient Statistics for Sparse Graphical Models from Truncated Samples

In this paper, we study high-dimensional estimation from truncated samples. We focus on two fundamental and classical problems: (i) inference of sparse Gaussian graphical models and (ii) support recovery of sparse linear models. (i) For Gaussian graphical models, suppose d-dimensional samples bf x are generated from a Gaussian N(μ,Sigma) and observed only if they belong to a subset S subseteq ℝd. We show that μ and Sigma can be estimated with error ε in the Frobenius norm, using tildeOleft(fractextrmnz(Sigma-1)ε2right) samples from a truncated N(μ,Sigma) and having access to a membership oracle for S. The set S is assumed to have non-trivial measure under the unknown distribution but is otherwise arbitrary. (ii) For sparse linear regression, suppose samples (bf x,y) are generated where y = bf x^topOmega^* + N(0,1) and (bf x, y) is seen only if y belongs to a truncation set S subseteq ℝ. We consider the case that Omega^* is sparse with a support set of size k. Our main result is to establish precise conditions on the problem dimension d, the support size k, the number of observations n, and properties of the samples and the truncation that are sufficient to recover the support of Omega^*. Specifically, we show that under some mild assumptions, only O(k2 log d) samples are needed to estimate Omega^* in the ℓ_∞-norm up to a bounded error. For both problems, our estimator minimizes the sum of the finite population negative log-likelihood function and an ℓ1-regularization term.