  The approximation of a high-dimensional vector by a small combination of
column vectors selected from a fixed matrix has been actively debated in
several different disciplines. In this paper, a sampling approach based on the
Monte Carlo method is presented as an efficient solver for such problems.
Especially, the use of simulated annealing (SA), a metaheuristic optimization
algorithm, for determining degrees of freedom (the number of used columns) by
cross validation is focused on and tested. Test on a synthetic model indicates
that our SA-based approach can find a nearly optimal solution for the
approximation problem and, when combined with the CV framework, it can optimize
the generalization ability. Its utility is also confirmed by application to a
real-world supernova data set.
