Reconstructing Sparse Signals via Greedy Monte-Carlo Search

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 ${\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.

15 pages, 4 figures

References in corpus (7)

• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Cross validation in LASSO and its acceleration
• Exhaustive search for sparse variable selection in linear regression
• 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