Simple, Efficient and Neural Algorithms for Sparse Coding
summary
Proposes a simple online, local, Hebbian algorithm that decodes by multiplying by the current dictionary transpose and hard‑thresholding and then updates via the outer product of the residual with the sign of the code, i.e. a matrix-vector multiply and thresholding front end and an outer product with sign update. Proves geometric columnwise convergence to the true overcomplete incoherent dictionary from a 1/polylog n initializer with polynomial samples and runtime, handles sparsity ~√n in this model and compares to n1/4 and SoS baselines, and frames analysis as approximate gradient descent on an unknown convex objective.
AI-written summary · about
chapters (10)
- 0:00Introduction to sparse coding
- 1:08Sparse coding basics
- 2:34Goals and research outline
- 3:47Optimization and models
- 9:01Main results and framework
- 9:49The update rule explained
- 12:46Analyzing alternating methods
- 15:33Proof outline and analysis
- 18:33Further results and summary
- 20:15Questions and discussion
related talks
43mCoded matrix computation: numerical stability, partial stragglers and sparse input matrices
54mThe Sparse Manifold Transform
51mTwo Concise Representations for High-Dimensional Visual Data
58mTensor Decomposition, Sparse Representations and Applications
32mApproximate coding computing
28mRandomized Constrained Matrix Decompositions
31mStatistical Estimation on Graphs
19mOptimizations and abstractions for sparse machine learning