Randomized Preconditioned Hard Thresholding Pursuit for Sparse Approximation

ABSTRACT

Sparsity models with ‐norm constraint are widely used in image processing, statistical regression, wireless communications, and other fields, where numerous thresholding‐based methods are employed. However, when the acquisition of linear measurement is time‐consuming or the measurement matrix is too large to store in memory, many thresholding‐based methods that require the whole measurement matrix become impractical. To address this issue, we propose a randomized preconditioned hard thresholding pursuit algorithm for finding a sparse solution to a linear system of equations with ‐norm constraint. The proposed method is also applicable to general settings. It is well‐known that Gaussian random matrices satisfy the restricted isometry property (RIP) with high probability, where the RIP of the measurement matrix is crucial for a thresholding‐based algorithm to recover a true sparse solution effectively. Taking Gaussian measurement matrices as an illustrative example, we quantitatively analyze how the preconditioner affects the RIP of the measurement submatrix chosen uniformly at random. The linear convergence of the proposed method is also established under some assumptions. Finally, numerical examples based on synthetic and real‐world data demonstrate the efficiency of the proposed method.