Provable Guarantees for Sparsity Recovery with Deterministic Missing Data Patterns
This work addresses the challenge of sparsity recovery in datasets with deterministic missing structures, which is more difficult than random missing scenarios, offering theoretical guarantees for applications in statistics and machine learning, though it appears incremental as it builds on existing Lasso methods with a new imputation strategy.
The paper tackles the problem of recovering the sparsity pattern of a regression parameter vector from correlated observations with deterministic missing data patterns using Lasso, proposing an efficient imputation algorithm based on the censorship filter's topology and proving that, under certain conditions, exact recovery is achievable with high probability in polynomial time and logarithmic sample complexity.
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.