Local Identification of Overcomplete Dictionaries
Karin Schnass.
Year: 2015, Volume: 16, Issue: 35, Pages: 1211−1242
Abstract
This paper presents the first theoretical results showing that stable identification of overcomplete μ-coherent dictionaries Φ∈Rd×K is locally possible from training signals with sparsity levels S up to the order O(μ−2) and signal to noise ratios up to O(√d). In particular the dictionary is recoverable as the local maximum of a new maximization criterion that generalizes the K-means criterion. For this maximization criterion results for asymptotic exact recovery for sparsity levels up to O(μ−1) and stable recovery for sparsity levels up to O(μ−2) as well as signal to noise ratios up to O(√d) are provided. These asymptotic results translate to finite sample size recovery results with high probability as long as the sample size N scales as O(K3dS˜ϵ−2), where the recovery precision ˜ϵ can go down to the asymptotically achievable precision. Further, to actually find the local maxima of the new criterion, a very simple Iterative Thresholding and K (signed) Means algorithm (ITKM), which has complexity O(dKN) in each iteration, is presented and its local efficiency is demonstrated in several experiments.