Simple, Efficient, and Neural Algorithms for Sparse Coding

Abstract

Sparse coding is a basic task in many fields including signal processing, neuroscience and machine learning where the goal is to learn a basis that enables a sparse representation of a given set of data, if one exists. Its standard formulation is as a non-convex optimization problem which is solved in practice by heuristics based on alternating minimization. Re- cent work has resulted in several algorithms for sparse coding with provable guarantees, but somewhat surprisingly these are outperformed by the simple alternating minimization heuristics. Here we give a general framework for understanding alternating minimization which we leverage to analyze existing heuristics and to design new ones also with provable guarantees. Some of these algorithms seem implementable on simple neural architectures, which was the original motivation of Olshausen and Field (1997a) in introducing sparse coding. We also give the first efficient algorithm for sparse coding that works almost up to the information theoretic limit for sparse recovery on incoherent dictionaries. All previous algorithms that approached or surpassed this limit run in time exponential in some natural parameter. Finally, our algorithms improve upon the sample complexity of existing approaches. We believe that our analysis framework will have applications in other settings where simple iterative algorithms are used.

37 pages, 1 figure

References in corpus (3)

• Decoding by Linear Programming
• Statistical guarantees for the EM algorithm: From population to sample-based analysis
• A Clustering Approach to Learn Sparsely-Used Overcomplete Dictionaries

Cited by in corpus (23)

• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• When Are Nonconvex Problems Not Scary?
• A Theoretical Perspective on Hyperdimensional Computing
• Why do similarity matching objectives lead to Hebbian/anti-Hebbian networks?
• Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
• Subgradient Descent Learns Orthogonal Dictionaries
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• Convolutional Phase Retrieval via Gradient Descent
• Recovery Guarantee of Non-negative Matrix Factorization via Alternating Updates
• Dictionary Learning from Incomplete Data
• Dictionary Learning with BLOTLESS Update
• On some provably correct cases of variational inference for topic models
• Complete Dictionary Learning via ${\ell }^4$-Norm Maximization over the Orthogonal Group
• Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo
• Learning Sparse Representations in Reinforcement Learning with Sparse Coding
• Recovery and Generalization in Over-Realized Dictionary Learning
• Tensor Graphical Model: Non-convex Optimization and Statistical Inference
• Unique Sharp Local Minimum in ${\ell }_1$-minimization Complete Dictionary Learning
• The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems
• Cross-Node Federated Graph Neural Network for Spatio-Temporal Data Modeling
• Conditions for Exact Convex Relaxation and No Spurious Local Optima
• Continuous-time Models for Stochastic Optimization Algorithms
• High Dimensional Multivariate Regression and Precision Matrix Estimation via Nonconvex Optimization