2012
COLT
COLT 2012
Exact Recovery of Sparsely-Used Dictionaries
Abstract
We consider the problem of learning sparsely used dictionaries with an arbitrary square dictionary and a random, sparse coefficient matrix. We prove that \emphO(n log \emphn) samples are sufficient to uniquely determine the coefficient matrix. Based on this proof, we design a polynomial-time algorithm, called Exact Recovery of Sparsely-Used Dictionaries (ER-SpUD), and prove that it probably recovers the dictionary and coefficient matrix when the coefficient matrix is sufficiently sparse. Simulation results show that ER-SpUD reveals the true dictionary as well as the coefficients with probability higher than many state-of-the-art algorithms.
🌉
Interdisciplinary Bridge
— Machine Learning and Mathematics & Optimization
🐝
Cross-Pollinator
— Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Speech & Audio
📈
Trend Setter
— Feature Learning
🧭
Keyword Pioneer
— sparse coefficient
🐣
Hot Topic Early Bird
— dictionary learning
Authors
Topics
Machine Learning > Core Methods > Representation Learning
Machine Learning > Learning Types > Unsupervised Learning
Mathematics & Optimization > Optimization > Continuous Optimization
Machine Learning > Core Methods > Feature Learning
Machine Learning > Core Methods > Matrix Factorization
Machine Learning > Learning Types > Feature Learning