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.
Code (0)
등록된 구현이 없습니다.
Tasks
ImputationSimilar Papers 제목 키워드 기반
DAEs for Linear Inverse Problems: Improved Recovery with Provable Guarantees
Generative priors have been shown to provide improved results over sparsity priors in linear inverse problems. However, current state of the art methods suffer from one or more of the following drawbacks: (a) speed of re…
Compressive SensingDenoisingSuper-ResolutionRe-embedding data to strengthen recovery guarantees of clustering
We propose a clustering method that involves chaining four known techniques into a pipeline yielding an algorithm with stronger recovery guarantees than any of the four components separately. Given $n$ points in $\mathbb…
ClusteringCrossCert: A Cross-Checking Detection Approach to Patch Robustness Certification for Deep Learning Models
Patch robustness certification is an emerging kind of defense technique against adversarial patch attacks with provable guarantees. There are two research lines: certified recovery and certified detection. They aim to la…
Taming Polysemanticity in LLMs: Provable Feature Recovery via Sparse Autoencoders
We study the challenge of achieving theoretically grounded feature recovery using Sparse Autoencoders (SAEs) for the interpretation of Large Language Models. Existing SAE training algorithms often lack rigorous mathemati…
i-SpaSP: Structured Neural Pruning via Sparse Signal Recovery
We propose a novel, structured pruning algorithm for neural networks -- the iterative, Sparse Structured Pruning algorithm, dubbed as i-SpaSP. Inspired by ideas from sparse signal recovery, i-SpaSP operates by iterativel…