On the identifiability of overcomplete dictionaries via the minimisation principle underlying K-SVD

DOI10.1016/J.ACHA.2014.01.005zbMATH Open1297.94018arXiv1301.3375OpenAlexW2034683677MaRDI QIDQ741264FDOQ741264

Authors: Karin Schnass 

Publication date: 11 September 2014

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

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 $Phiinmathbb{R}^{dimesK}$ 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/logN=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.

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

Recommendations

• $rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
• Identifiability of complete dictionary learning
• Dictionary Identification—Sparse Matrix-Factorization via $\ell_1$-Minimization
• Local identifiability of \(\ell_1\)-minimization dictionary learning: a sufficient and almost necessary condition
• On the Minimal Overcompleteness Allowing Universal Sparse Representation
• Local identification of overcomplete dictionaries
• Fast overcomplete dictionary construction with probabilistic guarantees
• Learning sparsely used overcomplete dictionaries via alternating minimization
• A complete characterization of optimal dictionaries for least squares representation
• On classification of signals represented with data-dependent overcomplete dictionaries

zbMATH Keywords

sparse representationdictionary learningsparse codingsparse component analysissampling complexityK-SVDdictionary identificationfinite sample sizeminimisation criterion

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Factorization of matrices (15A23) Source coding (94A29) Sampling theory in information and communication theory (94A20)

Cites Work

• $rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
• Title not available (Why is that?)
• Ten Lectures on Wavelets
• Stable recovery of sparse overcomplete representations in the presence of noise
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Compressed sensing
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Greed is Good: Algorithmic Results for Sparse Approximation
• Adaptive greedy approximations
• Online learning for matrix factorization and sparse coding
• Iteratively reweighted least squares minimization for sparse recovery
• An introduction to frames and Riesz bases
• Iterative thresholding for sparse approximations
• The sample complexity of dictionary learning
• Dictionary Learning Algorithms for Sparse Representation
• Recursive Least Squares Dictionary Learning Algorithm
• $K$-Dimensional Coding Schemes in Hilbert Spaces
• Fast Discrete Curvelet Transforms
• On the conditioning of random subdictionaries
• On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them
• Blind source separation by sparse decomposition in a signal dictionary
• Dictionary Identification—Sparse Matrix-Factorization via $\ell_1$-Minimization
• Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms
• Dictionary Learning for L1-Exact Sparse Coding
• Dictionary Learning for Sparse Approximations With the Majorization Method
• On the identifiability of overcomplete dictionaries via the minimisation principle underlying K-SVD

Cited In (16)

• On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them
• Convergence radius and sample complexity of ITKM algorithms for dictionary learning
• Learning semidefinite regularizers
• Compressed dictionary learning
• Multilinear compressive sensing and an application to convolutional linear networks
• On the identifiability of overcomplete dictionaries via the minimisation principle underlying K-SVD
• $rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
• Unique sharp local minimum in \(\ell_1\)-minimization complete dictionary learning
• Customized dictionary learning for subdatasets with fine granularity
• An efficient algorithm for overcomplete sparsifying transform learning with signal denoising
• Local identification of overcomplete dictionaries
• Learning sparsely used overcomplete dictionaries via alternating minimization
• Local identifiability of \(\ell_1\)-minimization dictionary learning: a sufficient and almost necessary condition
• Identifiability of complete dictionary learning
• Compressive sensing and neural networks from a statistical learning perspective
• Fast overcomplete dictionary construction with probabilistic guarantees

Uses Software

• PDCO
• CoSaMP

This page was built for publication: On the identifiability of overcomplete dictionaries via the minimisation principle underlying K-SVD

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