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

By Karin Schnass. 2013

66 citations recorded by the source corpus.

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 Φ ∈ R d × K can be recovered as local minimum of the minimisation criterion underlying K-SVD from a set of N training signals y n = Φ 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 − K d ) there is a local minimum of the K-SVD criterion within distance O ( K N − 1 / 4 ) to the generating dictionary.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Representation & Self-Supervised Learning, Statistical Learning Theory, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Representation & Self-Supervised Learning

In Statistical Learning Theory

In Signal Processing

Citations in the corpus

Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization (2013, methodology): “A similar local analysis is carried out by Schnass [29] for the K-SVD algorithm.”