Reconstructing Sparse Signals via Greedy Monte-Carlo Search
arXiv:2008.03175 · doi:10.7566/JPSJ.89.124802
Abstract
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 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.
arXiv comment15 pages, 4 figures
References in corpus (11)
- High-dimensional graphs and variable selection with the Lasso
- Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
- Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
- A typical reconstruction limit of compressed sensing based on Lp-norm minimization
- Cross validation in LASSO and its acceleration
- Exhaustive search for sparse variable selection in linear regression
- Berkeley Supernova Ia Program III: Spectra Near Maximum Brightness Improve the Accuracy of Derived Distances to Type Ia Supernovae
- Sparse approximation based on a random overcomplete basis
- Variable Selection for Modeling the Absolute Magnitude at Maximum of Type Ia Supernovae
- Statistical mechanical analysis of sparse linear regression as a variable selection problem
- Sparse approximation problem: how rapid simulated annealing succeeds and fails