Corrupted and missing predictors: Minimax bounds for high-dimensional linear regression

摘要

Missing and corrupted data are ubiquitous in many science and engineering domains. We analyze the information-theoretic limits of recovering sparse vectors under various models of corrupted and missing data. In particular, consider a high-dimensional linear regression model y = X β^∗ + є, where y Є Rⁿ is the response vector, X Є R^nXp is a random design matrix with p ≫ n and rows distributed i.i.d. as Ν(0, Σx), β^∗ є R^p is the unknown regression vector, and є ∼ Ν(0,σ²єΙ) is independent additive noise. Whereas a traditional approach assumes that the covariates X are fully observed, we assume only that a corrupted version Z is observed. Our main contribution is to establish minimax rates of convergence for estimating β^∗ in squared ℓ2-loss, assuming β^∗ is k-sparse. Our upper and lower bounds in both additive noise and missing data cases scale as k log(p/k), with prefactors depending only on the corruption and/or missing pattern of the data.