Convergence radius and sample complexity of ITKM algorithms for dictionary learning

DOI10.1016/J.ACHA.2016.08.002MaRDI QIDQ1748252zbMATH OpenOpenAlexFDO

Authors Karin Schnass

Publication date 9 May 2018

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

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

zbMATH Keywords

alternating optimisationconvergence radiusdictionary learningK-meanssample complexitysparse codingsparse component analysisthresholding

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Source coding (94A29)

Abstract: In this work we show that iterative thresholding and K-means (ITKM) algorithms can recover a generating dictionary with K atoms from noisy $S$ sparse signals up to an error $ildevarepsilon$ as long as the initialisation is within a convergence radius, that is up to a $logK$ factor inversely proportional to the dynamic range of the signals, and the sample size is proportional to $KlogKildevarepsilo{n}^{-2}$. The results are valid for arbitrary target errors if the sparsity level is of the order of the square root of the signal dimension $d$ and for target errors down to $K^{-ell}$ if $S$ scales as $Sleqd/(elllogK)$.

Recommendations

• Compressed dictionary learning
• Local identification of overcomplete dictionaries
• The sample complexity of dictionary learning
• Dictionary-sparse recovery via thresholding-based algorithms
• Learning sparsely used overcomplete dictionaries via alternating minimization

Cites work

• K-Dimensional Coding Schemes in Hilbert Spaces
• rm K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
• An introduction to frames and Riesz bases
• Blind source separation by sparse decomposition in a signal dictionary
• Dictionary Identification—Sparse Matrix-Factorization via \ell₁-Minimization
• Dictionary Learning Algorithms for Sparse Representation
• Dictionary learning and tensor decomposition via the sum-of-squares method
• Dictionary Learning for L1-Exact Sparse Coding
• Dictionary Learning for Sparse Approximations With the Majorization Method
• Hard thresholding pursuit: an algorithm for compressive sensing
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• Iterative hard thresholding for compressed sensing
• Iterative thresholding for sparse approximations
• Local identification of overcomplete dictionaries
• On the conditioning of random subdictionaries
• On the identifiability of overcomplete dictionaries via the minimisation principle underlying K-SVD
• Online learning for matrix factorization and sparse coding
• Probability Inequalities for the Sum of Independent Random Variables
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Recursive Least Squares Dictionary Learning Algorithm
• RIPless compressed sensing from anisotropic measurements
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Sample Complexity of Dictionary Learning and Other Matrix Factorizations
• Sparse and Spurious: Dictionary Learning With Noise and Outliers
• Stable recovery of sparse overcomplete representations in the presence of noise
• The sample complexity of dictionary learning

Cited in

(11)

• Applied harmonic analysis and data processing. Abstracts from the workshop held March 25--31, 2018
• Learning semidefinite regularizers
• A convex variational model for learning convolutional image atoms from incomplete data
• Compressed dictionary learning
• Generalization Error in Deep Learning
• On the Purity and Entropy of Mixed Gaussian States
• Local identification of overcomplete dictionaries
• Cardinality minimization, constraints, and regularization: a survey
• Convergence regions of alternating minimization algorithms for dictionary learning
• Simple alternating minimization provably solves complete dictionary learning
• Optimal regularization for a data source

This page was built for publication: Convergence radius and sample complexity of ITKM algorithms for dictionary learning

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