Learning sparsely used overcomplete dictionaries via alternating minimization
From MaRDI portal
Abstract: We consider the problem of sparse coding, where each sample consists of a sparse linear combination of a set of dictionary atoms, and the task is to learn both the dictionary elements and the mixing coefficients. Alternating minimization is a popular heuristic for sparse coding, where the dictionary and the coefficients are estimated in alternate steps, keeping the other fixed. Typically, the coefficients are estimated via minimization, keeping the dictionary fixed, and the dictionary is estimated through least squares, keeping the coefficients fixed. In this paper, we establish local linear convergence for this variant of alternating minimization and establish that the basin of attraction for the global optimum (corresponding to the true dictionary and the coefficients) is , where is the sparsity level in each sample and the dictionary satisfies RIP. Combined with the recent results of approximate dictionary estimation, this yields provable guarantees for exact recovery of both the dictionary elements and the coefficients, when the dictionary elements are incoherent.
Recommendations
- Analysis of fast structured dictionary learning
- Fast overcomplete dictionary construction with probabilistic guarantees
- Unique sharp local minimum in \(\ell_1\)-minimization complete dictionary learning
- A fast algorithm for learning overcomplete dictionary for sparse representation based on proximal operators
- Proximal alternating method for dictionary learning
Cites work
- rm K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
- A Clustering Approach to Learning Sparsely Used Overcomplete Dictionaries
- A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers
- Dictionary Identification—Sparse Matrix-Factorization via \ell₁-Minimization
- Image Super-Resolution Via Sparse Representation
- Information Theory and Statistics: A Tutorial
- Low-rank matrix completion using alternating minimization
- On the identifiability of overcomplete dictionaries via the minimisation principle underlying K-SVD
- Parametric Dictionary Design for Sparse Coding
- Proximal methods for hierarchical sparse coding
- Restricted eigenvalue properties for correlated Gaussian designs
- Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
- Smooth sparse coding via marginal regression for learning sparse representations
- Sparse and Spurious: Dictionary Learning With Noise and Outliers
- The benefit of multitask representation learning
- The restricted isometry property and its implications for compressed sensing
- The sample complexity of dictionary learning
Cited in
(34)- Learning semidefinite regularizers
- Combinatorial rigidity of incidence systems and application to dictionary learning
- Convergence radius and sample complexity of ITKM algorithms for dictionary learning
- A geometric analysis of phase retrieval
- Structured overcomplete sparsifying transform learning with convergence guarantees and applications
- Role of sparsity and structure in the optimization landscape of non-convex matrix sensing
- Fast overcomplete dictionary construction with probabilistic guarantees
- Compressed dictionary learning
- Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods
- Efficient matrix sensing using rank-1 Gaussian measurements
- Local identifiability of \(\ell_1\)-minimization dictionary learning: a sufficient and almost necessary condition
- rm K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
- Accelerated Alternating Projections for Robust Principal Component Analysis
- Unique sharp local minimum in \(\ell_1\)-minimization complete dictionary learning
- Analysis of fast structured dictionary learning
- Identifiability of complete dictionary learning
- (L_r,L_r,1)-decompositions, sparse component analysis, and the blind separation of sums of exponentials
- Global optimality in separable dictionary learning with applications to the analysis of diffusion MRI
- Complete dictionary learning via ^4-norm maximization over the orthogonal group
- Provably accurate double-sparse coding
- A fast algorithm for learning overcomplete dictionary for sparse representation based on proximal operators
- Alternating proximal regularized dictionary learning
- The alternating descent conditional gradient method for sparse inverse problems
- Local identification of overcomplete dictionaries
- Proximal alternating method for dictionary learning
- Sharp global convergence guarantees for iterative nonconvex optimization with random data
- A new complexity metric for nonconvex rank-one generalized matrix completion
- Convergence regions of alternating minimization algorithms for dictionary learning
- Simple alternating minimization provably solves complete dictionary learning
- The effect of SGD batch size on autoencoder learning: sparsity, sharpness, and feature learning
- Data-driven methods for quantitative imaging
- Dictionary learning for the almost-linear sparsity regime
- Optimal regularization for a data source
- On the identifiability of overcomplete dictionaries via the minimisation principle underlying K-SVD
This page was built for publication: Learning sparsely used overcomplete dictionaries via alternating minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3179269)
