Statistical mechanical analysis of sparse linear regression as a variable selection problem

Abstract

An algorithmic limit of compressed sensing or related variable-selection problems is analytically evaluated when a design matrix is given by an overcomplete random matrix. The replica method from statistical mechanics is employed to derive the result. The analysis is conducted through evaluation of the entropy, an exponential rate of the number of combinations of variables giving a specific value of fit error to given data which is assumed to be generated from a linear process using the design matrix. This yields the typical achievable limit of the fit error when solving a representative ${\ell }_0$ problem and includes the presence of unfavourable phase transitions preventing local search algorithms from reaching the minimum-error configuration. The associated phase diagrams are presented. A noteworthy outcome of the phase diagrams is that there exists a wide parameter region where any phase transition is absent from the high temperature to the lowest temperature at which the minimum-error configuration or the ground state is reached. This implies that certain local search algorithms can find the ground state with moderate computational costs in that region. Another noteworthy result is the presence of the random first-order transition in the strong noise case. The theoretical evaluation of the entropy is confirmed by extensive numerical methods using the exchange Monte Carlo and the multi-histogram methods. Another numerical test based on a metaheuristic optimisation algorithm called simulated annealing is conducted, which well supports the theoretical predictions on the local search algorithms. In the successful region with no phase transition, the computational cost of the simulated annealing to reach the ground state is estimated as the third order polynomial of the model dimensionality.

arXiv comment39 pages, 14 figures

References in corpus (25)

• An efficient, multiple range random walk algorithm to calculate the density of states
• Message Passing Algorithms for Compressed Sensing
• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform so well over the BEC
• On the Out of Equilibrium Relaxation of the Sherrington - Kirkpatrick model
• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Full dynamical solution for a spherical spin-glass model
• Statistical physics-based reconstruction in compressed sensing
• A typical reconstruction limit of compressed sensing based on Lp-norm minimization
• Typical Performance of Gallager-type Error-Correcting Codes
• On the cooling-schedule dependence of the dynamics of mean-field glasses
• Analysis of CDMA systems that are characterized by eigenvalue spectrum
• Generalized Approximate Message Passing for Estimation with Random Linear Mixing
• Cryptographical Properties of Ising Spin Systems
• Performance of simulated annealing in p-spin glasses
• Sparse approximation based on a random overcomplete basis
• Weight space structure and analysis using a finite replica number in the Ising perceptron
• Replica symmetry breaking, complexity and spin representation in the generalized random energy model
• The out of equilibrium dynamics of the Sherrington-Kirkpatrick model
• Sparse approximation problem: how rapid simulated annealing succeeds and fails
• High-Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition
• Public key cryptography and error correcting codes as Ising models

Cited by in corpus (7)

• Effective implementation of $l_0$-Regularised Compressed Sensing with Chaotic-Amplitude-Controlled Coherent Ising Machines
• Statistical Mechanics of Dynamical System Identification
• Compressed sensing with l0-norm: statistical physics analysis and algorithms for signal recovery
• Large Deviations of Semi-supervised Learning in the Stochastic Block Model
• The phase diagram of compressed sensing with ${\ell }_0$-norm regularization
• Reconstructing Sparse Signals via Greedy Monte-Carlo Search
• Effect of global shrinkage parameter of horseshoe prior in compressed sensing