论文标题
可证明的稀疏恢复的保证，并确定性丢失数据模式
Provable Guarantees for Sparsity Recovery with Deterministic Missing Data Patterns
论文作者
论文摘要
我们研究了从确定性缺失数据模式使用lasso控制的相关观测值中始终如一地恢复回归参数矢量的稀疏模式的问题。我们考虑观察到的数据集受确定性，不均匀过滤器进行审查的情况。通过确定性缺失结构恢复数据集中的稀疏模式可以说，比在统一的方案中恢复更具挑战性。在本文中，我们通过利用审查过滤器的拓扑特性，提出了一种有效的算法来插值的算法。然后，我们提供了新的理论结果，以使用拟议的插补策略来精确恢复稀疏模式。我们的分析表明，在某些统计和拓扑条件下，可以在多项式时间和对数样品复杂性中恢复隐藏的稀疏模式。
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.
