Performance Limits of Dictionary Learning for Sparse Coding
We consider the problem of dictionary learning under the assumption that the observed signals can be represented as sparse linear combinations of the columns of a single large dictionary matrix. In particular, we analyze the minimax risk of the dictionary learning problem which governs the mean squared error (MSE) performance of any learning scheme, regardless of its computational complexity. By following an established information-theoretic method based on Fanos inequality, we derive a lower bound on the minimax risk for a given dictionary learning problem. This lower bound yields a characterization of the sample-complexity, i.e., a lower bound on the required number of observations such that consistent dictionary learning schemes exist. Our bounds may be compared with the performance of a given learning scheme, allowing to characterize how far the method is from optimal performance.
Code (0)
등록된 구현이 없습니다.
Tasks
Dictionary LearningSimilar Papers 제목 키워드 기반
NOODL: Provable Online Dictionary Learning and Sparse Coding
We consider the dictionary learning problem, where the aim is to model the given data as a linear combination of a few columns of a matrix known as a dictionary, where the sparse weights forming the linear combination ar…
Dictionary LearningDictionary learning for fast classification based on soft-thresholding
Classifiers based on sparse representations have recently been shown to provide excellent results in many visual recognition and classification tasks. However, the high cost of computing sparse representations at test ti…
ClassificationDictionary LearningGeneral ClassificationEfficient Sparse Coding using Hierarchical Riemannian Pursuit
Sparse coding is a class of unsupervised methods for learning a sparse representation of the input data in the form of a linear combination of a dictionary and a sparse code. This learning framework has led to state-of-t…
Data CompressionIneffectiveness of Dictionary Coding to Infer Predictability Limits of Human Mobility
Recently, a series of models have been proposed to predict future movements of people. Meanwhile, dictionary coding algorithms are used to estimate the predictability limit of human mobility. Although dictionary coding i…
Dictionary Learning with Convex Update (ROMD)
Dictionary learning aims to find a dictionary under which the training data can be sparsely represented, and it is usually achieved by iteratively applying two stages: sparse coding and dictionary update. Typical methods…
Dictionary Learning