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 N(0, Σ_x), β* ∈ R^p is the unknown regression vector, and ϵ ~ N(0,σ_ϵ²I) 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 ℓ₂-loss, assuming β* is k-sparse. Our upper and lower bounds in both additive noise and missing data cases scale as k log(p/k)/n, with prefactors depending only on the corruption and/or missing pattern of the data.