More Algorithms for Provable Dictionary Learning

Abstract

In dictionary learning, also known as sparse coding, the algorithm is given samples of the form $y=Ax$ where $x\in {\mathbb{R}}^m$ is an unknown random sparse vector and $A$ is an unknown dictionary matrix in ${\mathbb{R}}^{n\times m}$ (usually $m>n$, which is the overcomplete case). The goal is to learn $A$ and $x$. This problem has been studied in neuroscience, machine learning, visions, and image processing. In practice it is solved by heuristic algorithms and provable algorithms seemed hard to find. Recently, provable algorithms were found that work if the unknown feature vector $x$ is $\sqrt{n}$-sparse or even sparser. Spielman et al. \cite{DBLP:journals/jmlr/SpielmanWW12} did this for dictionaries where $m=n$; Arora et al. \cite{AGM} gave an algorithm for overcomplete ($m>n$) and incoherent matrices $A$; and Agarwal et al. \cite{DBLP:journals/corr/AgarwalAN13} handled a similar case but with weaker guarantees. This raised the problem of designing provable algorithms that allow sparsity $\gg \sqrt{n}$ in the hidden vector $x$. The current paper designs algorithms that allow sparsity up to $n/poly(\log n)$. It works for a class of matrices where features are individually recoverable, a new notion identified in this paper that may motivate further work. The algorithm runs in quasipolynomial time because they use limited enumeration.

23 pages

References in corpus (1)

• Provable Bounds for Learning Some Deep Representations

Cited by in corpus (16)

• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• When Are Nonconvex Problems Not Scary?
• A Unified Framework for Identifiability Analysis in Bilinear Inverse Problems with Applications to Subspace and Sparsity Models
• Greedy Deep Dictionary Learning
• Convolutional Phase Retrieval via Gradient Descent
• Fast Orthonormal Sparsifying Transforms Based on Householder Reflectors
• Dictionary Learning with BLOTLESS Update
• An improved analysis of the ER-SpUD dictionary learning algorithm
• Matrix Completion and Related Problems via Strong Duality
• 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
• Robust Correlation Clustering with Asymmetric Noise
• Non-Convex Compressed Sensing with Training Data
• Deep Sparse Coding for Non-Intrusive Load Monitoring
• How to Train Your Deep Neural Network with Dictionary Learning