Recovery Conditions of Sparse Signals Using Orthogonal Least Squares-Type Algorithms
arXiv:2201.04914 · doi:10.1109/TSP.2022.3208439
Abstract
Orthogonal least squares (OLS)-type algorithms are efficient in reconstructing sparse signals, which include the well-known OLS, multiple OLS (MOLS) and block OLS (BOLS). In this paper, we first investigate the noiseless exact recovery conditions of these algorithms. Specifically, based on mutual incoherence property (MIP), we provide theoretical analysis of OLS and MOLS to ensure that the correct nonzero support can be selected during the iterative procedure. Nevertheless, theoretical analysis for BOLS utilizes the block-MIP to deal with the block sparsity. Furthermore, the noiseless MIP-based analyses are extended to the noisy scenario. Our results indicate that for K-sparse signals, when MIP or SNR satisfies certain conditions, OLS and MOLS obtain reliable reconstruction in at most K iterations, while BOLS succeeds in at most (K/d) iterations where d is the block length. It is shown that our derived theoretical results improve the existing ones, which are verified by simulation tests.
arXiv comment13 pages, 11 figures, published in IEEE Transactions on Signal Processing
References in corpus (9)
- Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
- Extension of SBL Algorithms for the Recovery of Block Sparse Signals with Intra-Block Correlation
- Nearly Optimal Bounds for Orthogonal Least Squares
- Block-Sparsity-Induced Adaptive Filter for Multi-Clustering System Identification
- Joint k-step analysis of Orthogonal Matching Pursuit and Orthogonal Least Squares
- Uncertainty Relations for Shift-Invariant Analog Signals
- Signal-Dependent Performance Analysis of Orthogonal Matching Pursuit for Exact Sparse Recovery
- Sparse Recovery and Dictionary Learning from Nonlinear Compressive Measurements
- Exploiting Prior Information in Block Sparse Signals