  Information processing techniques based on sparseness have been actively
studied in several disciplines. Among them, a mathematical framework to
approximately express a given dataset by a combination of a small number of
basis vectors of an overcomplete basis is termed the {\em sparse
approximation}. In this paper, we apply simulated annealing, a metaheuristic
algorithm for general optimization problems, to sparse approximation in the
situation where the given data have a planted sparse representation and noise
is present. The result in the noiseless case shows that our simulated annealing
works well in a reasonable parameter region: the planted solution is found
fairly rapidly. This is true even in the case where a common relaxation of the
sparse approximation problem, the $\ell_1$-relaxation, is ineffective. On the
other hand, when the dimensionality of the data is close to the number of
non-zero components, another metastable state emerges, and our algorithm fails
to find the planted solution. This phenomenon is associated with a first-order
phase transition. In the case of very strong noise, it is no longer meaningful
to search for the planted solution. In this situation, our algorithm determines
a solution with close-to-minimum distortion fairly quickly.
