Local identification of overcomplete dictionaries

zbMATH Open1351.68232arXiv1401.6354MaRDI QIDQ5744800FDOQ5744800

Authors: Karin Schnass 

Publication date: 19 February 2016

Abstract: This paper presents the first theoretical results showing that stable identification of overcomplete $mu$-coherent dictionaries $Phiinmathbb{R}^{dimesK}$ is locally possible from training signals with sparsity levels $S$ up to the order $O(m{u}^{-2})$ and signal to noise ratios up to $O(sqrtd)$. In particular the dictionary is recoverable as the local maximum of a new maximisation criterion that generalises the K-means criterion. For this maximisation criterion results for asymptotic exact recovery for sparsity levels up to $O(m{u}^{-1})$ and stable recovery for sparsity levels up to $O(m{u}^{-2})$ as well as signal to noise ratios up to $O(sqrtd)$ 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(K^{3}dSildevarepsilo{n}^{-2})$, where the recovery precision $ildevarepsilon$ 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.

Full work available at URL: https://arxiv.org/abs/1401.6354

Recommendations

• Local identifiability of \(\ell_1\)-minimization dictionary learning: a sufficient and almost necessary condition
• On the identifiability of overcomplete dictionaries via the minimisation principle underlying K-SVD
• Convergence radius and sample complexity of ITKM algorithms for dictionary learning
• Learning sparsely used overcomplete dictionaries via alternating minimization
• Compressed dictionary learning

zbMATH Keywords

sparse representation\(K\)-meansdictionary learningvector quantizationsparse codingsparse component analysissample complexitydictionary identificationfinite sample sizemaximization criterion

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Learning and adaptive systems in artificial intelligence (68T05) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (7)

• Convergence radius and sample complexity of ITKM algorithms for dictionary learning
• Compressed dictionary learning
• On the identifiability of overcomplete dictionaries via the minimisation principle underlying K-SVD
• Unique sharp local minimum in \(\ell_1\)-minimization complete dictionary learning
• Customized dictionary learning for subdatasets with fine granularity
• Local identifiability of \(\ell_1\)-minimization dictionary learning: a sufficient and almost necessary condition
• Identifiability of complete dictionary learning

This page was built for publication: Local identification of overcomplete dictionaries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5744800)