2016年
Sparse approximation problem: how rapid simulated annealing succeeds and fails
INTERNATIONAL MEETING ON HIGH-DIMENSIONAL DATA-DRIVEN SCIENCE (HD3-2015)
- ,
- 巻
- 699
- 号
- No.
- 開始ページ
- pp. 012017(1
- 終了ページ
- 12)
- 記述言語
- 英語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- DOI
- 10.1088/1742-6596/699/1/012017
- 出版者・発行元
- IOP PUBLISHING LTD
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 Li-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.
- リンク情報
- ID情報
-
- DOI : 10.1088/1742-6596/699/1/012017
- ISSN : 1742-6588
- ORCIDのPut Code : 51566669
- Web of Science ID : WOS:000376066400017
- ORCIDで取得されたその他外部ID : a:1:{i:0;a:1:{s:14:"source-work-id";s:12:"CTT100704974";}}