Bubacarr Bah
ABSTRACT
Linear sketching and recovery of sparse vectors with randomly constructed sparse matrices has numerous applications in several areas, including compressive sensing, data stream computing, graph sketching, and combinatorial group testing. This paper considers the same problem with the added twist that the sparse coefficients of the unknown vector exhibit further correlations as determined by a known sparsity model. We prove that exploiting model-based sparsity in recovery provably reduces the sketch size without sacrificing recovery quality. In this context, we present the model-expander iterative hard thresholding algorithm for recovering model sparse signals from linear sketches obtained via sparse adjacency matrices of expander graphs with rigorous performance guarantees. The main computational cost of our algorithm depends on the difficulty of projecting onto the model-sparse set. For the tree and group-based sparsity models we describe in this paper, such projections can be obtained in linear time. Finally, we provide numerical experiments to illustrate the theoretical results in action.
Index Terms
- Model-based sketching and recovery with expanders
Recommendations
Image Recovery based on Local and Nonlocal Regularizations
Recently, a nonlocal low-rank regularization based compressive sensing approach (NLR) which exploits structured sparsity of similar patches has shown the state-of-the-art performance in image recovery. However, NLR cannot efficiently preserve local ...
A Non-convex Optimization Model for Signal Recovery
AbstractThe electroencephalogram (EEG) signal is one of the most frequently used biomedical signals. In order to accurately exploit the cosparsity and low-rank property which is nature in multichannel EEG signals, motivated by the fact that weighted ...
RIP-based performance guarantee for low-tubal-rank tensor recovery
AbstractThe essential task of tensor data analysis focuses on the tensor decomposition and the corresponding notion of rank. In this paper, by introducing the notion of tensor Singular Value Decomposition (t-SVD), we establish a Regularized ...
Comments