Recovery of Sparse Signals Using Multiple Orthogonal Least Squares
This work addresses sparse signal recovery, a key problem in compressed sensing and signal processing, by offering an incremental improvement over existing orthogonal least squares methods.
The paper tackles the problem of recovering sparse signals from compressed linear measurements by proposing the multiple orthogonal least squares (MOLS) method, which extends orthogonal least squares to select multiple indices per iteration, resulting in convergence in fewer iterations and improved computational efficiency, with theoretical guarantees for exact recovery under specific restricted isometry property conditions and stable recovery in noisy scenarios.
We study the problem of recovering sparse signals from compressed linear measurements. This problem, often referred to as sparse recovery or sparse reconstruction, has generated a great deal of interest in recent years. To recover the sparse signals, we propose a new method called multiple orthogonal least squares (MOLS), which extends the well-known orthogonal least squares (OLS) algorithm by allowing multiple $L$ indices to be chosen per iteration. Owing to inclusion of multiple support indices in each selection, the MOLS algorithm converges in much fewer iterations and improves the computational efficiency over the conventional OLS algorithm. Theoretical analysis shows that MOLS ($L > 1$) performs exact recovery of all $K$-sparse signals within $K$ iterations if the measurement matrix satisfies the restricted isometry property (RIP) with isometry constant $δ_{LK} < \frac{\sqrt{L}}{\sqrt{K} + 2 \sqrt{L}}.$ The recovery performance of MOLS in the noisy scenario is also studied. It is shown that stable recovery of sparse signals can be achieved with the MOLS algorithm when the signal-to-noise ratio (SNR) scales linearly with the sparsity level of input signals.