  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.
