Sparse approximation approximation is provably hard under coherent dictionaries
Yazarlar (1)
Prof. Dr. Ali ÇİVRİL Antalya Bilim University, Türkiye
| Makale Türü |
Özgün Makale
(SSCI, AHCI, SCI, SCI-Exp dergilerinde yayınlanan tam makale)
|
||
| Dergi Adı | Journal of Computer and System Sciences (Q1) | ||
| Dergi ISSN | 0022-0000 Dergi Bilgileri (2017) | ||
| Dergi Tarandığı Indeksler | SCI | ||
| Makale Dili | İngilizce | Basım Tarihi | 03-2017 |
| Cilt / Sayı / Sayfa | 84 / 1 / 32–43 | DOI | 10.1016/j.jcss.2016.07.001 |
| Makale Linki | https://linkinghub.elsevier.com/retrieve/pii/S0022000016300587 | ||
| UAK Araştırma Alanları |
Algoritmalar ve Hesaplama Kuramı
|
||
| Özet |
| It is well known that sparse approximation problem is NP-hard under general dictionaries. Several algorithms have been devised and analyzed in the past decade under various assumptions on the coherence μ of the dictionary represented by an M× N matrix from which a subset of k column vectors is selected. All these results assume μ= O (k− 1). This article is an attempt to bridge the big gap between the negative result of NP-hardness under general dictionaries and the positive results under this restrictive assumption. In particular, it suggests that the aforementioned assumption might be asymptotically the best one can make to arrive at any efficient algorithmic result under well-known conjectures of complexity theory. In establishing the results, we make use of a new simple multilayered PCP which is tailored to give a matrix with small coherence combined with our reduction. |
| Anahtar Kelimeler |
| Complexity | PCP | Sparse approximation | Unique games |
Science Direct
Sparse approximation approximation is provably hard under coherent dictionaries
BM Sürdürülebilir Kalkınma Amaçları
| Atıf Sayıları | |
| Google Scholar | 2 |