Sparse approximation problem: how rapid simulated annealing succeeds and fails

Abstract

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.

12 pages, 7 figures, a proceedings of HD^3-2015

References in corpus (2)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices

Cited by in corpus (2)

• Statistical mechanical analysis of sparse linear regression as a variable selection problem
• Reconstructing Sparse Signals via Greedy Monte-Carlo Search