Reconstructing Sparse Signals via Greedy Monte-Carlo Search
This work addresses sparse signal reconstruction for applications like compressed sensing, but it is incremental as it builds on existing Monte-Carlo methods with modest improvements.
The authors tackled the problem of reconstructing sparse signals in high-dimensional settings by proposing a greedy Monte-Carlo search algorithm, which achieved perfect reconstruction in noiseless cases and outperformed ℓ1 relaxation but did not reach the theoretical algorithmic limit of Monte-Carlo methods.
We propose a Monte-Carlo-based method for reconstructing sparse signals in the formulation of sparse linear regression in a high-dimensional setting. The basic idea of this algorithm is to explicitly select variables or covariates to represent a given data vector or responses and accept randomly generated updates of that selection if and only if the energy or cost function decreases. This algorithm is called the greedy Monte-Carlo (GMC) search algorithm. Its performance is examined via numerical experiments, which suggests that in the noiseless case, GMC can achieve perfect reconstruction in undersampling situations of a reasonable level: it can outperform the $\ell_1$ relaxation but does not reach the algorithmic limit of MC-based methods theoretically clarified by an earlier analysis. The necessary computational time is also examined and compared with that of an algorithm using simulated annealing. Additionally, experiments on the noisy case are conducted on synthetic datasets and on a real-world dataset, supporting the practicality of GMC.