Provable Guarantees for Sparsity Recovery with Deterministic Missing Data Patterns
We study the problem of consistently recovering the sparsity pattern of a
regression parameter vector from correlated observations governed by
deterministic missing data patterns using Lasso. We consider the case in which
the observed dataset is censored by a deterministic, non-uniform filter.
Recovering the sparsity pattern in datasets with deterministic missing
structure can be arguably more challenging than recovering in a
uniformly-at-random scenario. In this paper, we propose an efficient algorithm
for missing value imputation by utilizing the topological property of the
censorship filter. We then provide novel theoretical results for exact recovery
of the sparsity pattern using the proposed imputation strategy. Our analysis
shows that, under certain statistical and topological conditions, the hidden
sparsity pattern can be recovered consistently with high probability in
polynomial time and logarithmic sample complexity.