The Benefits of Acting Locally: Reconstruction Algorithms for Sparse in Levels Signals With Stable and Robust Recovery Guarantees

作     者：Adcock, Ben Brugiapaglia, Simone King-Roskamp, Matthew 

作者机构：Simon Fraser Univ Dept Math Burnaby BC V5A 1S6 Canada Concordia Univ Dept Math & Stat Montreal PQ H3G 1M8 Canada 

出 版 物：《IEEE TRANSACTIONS ON SIGNAL PROCESSING》 (IEEE Trans Signal Process)

年 卷 期：2021年第69卷

页      面：3160-3175页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 

基　　金：PIMS CRG "High-dimensional Data Analysis," SFU's Big Data Initiative "Next Big Question" Fund NSERC [RGPIN-2020-06766, R611675] Faculty of Arts and Science of Concordia University 

主　　题：Compressed sensing reconstruction algorithms iterative algorithms greedy algorithms 

摘      要：The sparsity in levels model recently inspired a new generation of effective acquisition and reconstruction modalities for compressive imaging. Moreover, it naturally arises in various areas of signal processing such as parallel acquisition, radar, and the sparse corruptions problem. Reconstruction strategies for sparse in levels signals usually rely on a suitable convex optimization program. Notably, although iterative and greedy algorithms can outperform convex optimization in terms of computational efficiency and have been studied extensively in the case of standard sparsity, little is known about their generalizations to the sparse in levels setting. In this paper, we bridge this gap by showing new stable and robust uniform recovery guarantees for sparse in level variants of the iterative hard thresholding and the CoSaMP algorithms. Our theoretical analysis generalizes recovery guarantees currently available in the case of standard sparsity and favorably compare to sparse in levels guarantees for weighted l(1) minimization. In addition, we also propose and numerically test an extension of the orthogonal matching pursuit algorithm for sparse in levels signals.