2016/01/31 by Tomoyuki Obuchi, Yoshiyuki Kabashima · 1 citation
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Algorithm #Artificial intelligence #Basis (linear algebra) #Computer science #Curse of dimensionality #Image and Signal Denoising Methods #Mathematical optimization #Mathematics #Metaheuristic #Relaxation (psychology) #Simulated annealing #Sparse and Compressive Sensing Techniques #Sparse approximation #Structural Health Monitoring Techniques #cond-mat.dis-nn #cond-mat.stat-mech #cs.IT #math.IT
paper · pdf · doi:10.1088/1742-6596/699/1/012017
12 pages, 7 figures, a proceedings of HD^3-2015
openalex publication_date 2016/03/01 · arxiv created 2016/03/04 · arxiv updated 2016/05/04 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/06
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 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 G-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.