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

DOI10.1016/J.ACHA.2014.01.005MaRDI QIDQ741264zbMATH OpenOpenAlexFDO

Authors Karin Schnass

Publication date 11 September 2014

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

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

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)

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.

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

Cites work

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

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
• Learning sparsely used overcomplete dictionaries via alternating minimization
• Local identification of overcomplete dictionaries
• 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

Describes a project that uses

Uses Software

• CoSaMP
• PDCO

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)