Sparse approximation is provably hard under coherent dictionaries

作者：

Highlights：

• Sparse approximation is hard even under reasonably coherent dictionaries.

• Previously, only NP-hardness was known in the general case.

• Two hardness assumptions used: P≠NP, Unique Games Conjecture.

• A new simple multilayered PCP is used.

摘要

•Sparse approximation is hard even under reasonably coherent dictionaries.•Previously, only NP-hardness was known in the general case.•Two hardness assumptions used: P≠NP, Unique Games Conjecture.•A new simple multilayered PCP is used.

论文关键词：Sparse approximation,Complexity,PCP,Unique games

论文评审过程：Received 20 October 2014, Revised 4 May 2016, Accepted 17 July 2016, Available online 1 August 2016, Version of Record 14 November 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.07.001