On the Computational Intractability of Exact and Approximate Dictionary Learning

Abstract

The efficient sparse coding and reconstruction of signal vectors via linear observations has received a tremendous amount of attention over the last decade. In this context, the automated learning of a suitable basis or overcomplete dictionary from training data sets of certain signal classes for use in sparse representations has turned out to be of particular importance regarding practical signal processing applications. Most popular dictionary learning algorithms involve NP-hard sparse recovery problems in each iteration, which may give some indication about the complexity of dictionary learning but does not constitute an actual proof of computational intractability. In this technical note, we show that learning a dictionary with which a given set of training signals can be represented as sparsely as possible is indeed NP-hard. Moreover, we also establish hardness of approximating the solution to within large factors of the optimal sparsity level. Furthermore, we give NP-hardness and non-approximability results for a recent dictionary learning variation called the sensor permutation problem. Along the way, we also obtain a new non-approximability result for the classical sparse recovery problem from compressed sensing.

arXiv comment5 pages; accepted for publication

References in corpus (2)

• Astronomical Image Denoising Using Dictionary Learning
• Dictionary Learning for Deblurring and Digital Zoom

Cited by in corpus (9)

• DOLPHIn - Dictionary Learning for Phase Retrieval
• Sparse Range-constrained Learning and Its Application for Medical Image Grading
• Learning Fast Sparsifying Transforms
• Fast Orthonormal Sparsifying Transforms Based on Householder Reflectors
• Dictionary Learning with Equiprobable Matching Pursuit
• A Tree-based Dictionary Learning Framework
• Deep learning based dictionary learning and tomographic image reconstruction
• An iterative coordinate descent algorithm to compute sparse low-rank approximations
• Inversion of Magnetic Data using Learned Dictionaries and Scale Space