Sparse Approximation is Provably Hard under Coherent Dictionaries

Ali Çivril

It is well known that sparse approximation problem is \textsf{NP}-hard under general dictionaries. Several algorithms have been devised and analyzed in the past decade under variou…