On the Identifiability of Overcomplete Dictionaries via the Minimisation Principle Underlying K-SVD

Abstract

This article gives theoretical insights into the performance of K-SVD, a dictionary learning algorithm that has gained significant popularity in practical applications. The particular question studied here is when a dictionary $\Phi \in {\mathbb{R}}^{d\times K}$ can be recovered as local minimum of the minimisation criterion underlying K-SVD from a set of $N$ training signals $y_n=\Phi x_n$. A theoretical analysis of the problem leads to two types of identifiability results assuming the training signals are generated from a tight frame with coefficients drawn from a random symmetric distribution. First, asymptotic results showing, that in expectation the generating dictionary can be recovered exactly as a local minimum of the K-SVD criterion if the coefficient distribution exhibits sufficient decay. Second, based on the asymptotic results it is demonstrated that given a finite number of training samples $N$, such that $N/\log N=O(K^{3}d)$, except with probability $O(N^{-Kd})$ there is a local minimum of the K-SVD criterion within distance $O(K{N}^{-1/4})$ to the generating dictionary.

36 pages (double spaced), 3 figures, equivalent to final accepted version

References in corpus (7)

• Exact Recovery of Sparsely-Used Dictionaries
• New Algorithms for Learning Incoherent and Overcomplete Dictionaries
• On the Identifiability of Overcomplete Dictionaries via the Minimisation Principle Underlying K-SVD
• Local stability and robustness of sparse dictionary learning in the presence of noise
• A Clustering Approach to Learn Sparsely-Used Overcomplete Dictionaries
• On the Sample Complexity of Predictive Sparse Coding
• Sample Complexity of Dictionary Learning and other Matrix Factorizations

Cited by in corpus (16)

• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• On the Identifiability of Overcomplete Dictionaries via the Minimisation Principle Underlying K-SVD
• Noisy Matrix Completion under Sparse Factor Models
• Minimax Lower Bounds on Dictionary Learning for Tensor Data
• Structured Dictionary Learning for Classification
• Local Identification of Overcomplete Dictionaries
• Learning Mixtures of Separable Dictionaries for Tensor Data: Analysis and Algorithms
• Identifiability of Kronecker-structured Dictionaries for Tensor Data
• Dictionary Learning from Incomplete Data
• Minimax Lower Bounds for Kronecker-Structured Dictionary Learning
• Dictionary Learning with BLOTLESS Update
• Performance Limits of Dictionary Learning for Sparse Coding
• Dictionary learning of sound speed profiles
• Sparse and spurious: dictionary learning with noise and outliers
• Recovery and Generalization in Over-Realized Dictionary Learning
• Learning Semidefinite Regularizers