Exhaustive search for sparse variable selection in linear regression

Abstract

We propose a K-sparse exhaustive search (ES-K) method and a K-sparse approximate exhaustive search method (AES-K) for selecting variables in linear regression. With these methods, K-sparse combinations of variables are tested exhaustively assuming that the optimal combination of explanatory variables is K-sparse. By collecting the results of exhaustively computing ES-K, various approximate methods for selecting sparse variables can be summarized as density of states. With this density of states, we can compare different methods for selecting sparse variables such as relaxation and sampling. For large problems where the combinatorial explosion of explanatory variables is crucial, the AES-K method enables density of states to be effectively reconstructed by using the replica-exchange Monte Carlo method and the multiple histogram method. Applying the ES-K and AES-K methods to type Ia supernova data, we confirmed the conventional understanding in astronomy when an appropriate K is given beforehand. However, we found the difficulty to determine K from the data. Using virtual measurement and analysis, we argue that this is caused by data shortage.

arXiv comment19pages, 3 figures

References in corpus (14)

• Rejoinder to "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• 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

Cited by in corpus (4)

• Cross validation in sparse linear regression with piecewise continuous nonconvex penalties and its acceleration
• Feature Selection for Classification of Blazars Based on Optical Photometric and Polarimetric Time-Series Data
• Replica Analysis for Ensemble Techniques in Variable Selection
• Reconstructing Sparse Signals via Greedy Monte-Carlo Search