Computational Intractability of Dictionary Learning for Sparse Representation

Meisam Razaviyayn, Hung-Wei Tseng, Zhi-Quan Luo

In this paper we consider the dictionary learning problem for sparse representation. We first show that this problem is NP-hard by polynomial time reduction of the densest cut prob…