An improved analysis of the ER-SpUD dictionary learning algorithm

DOI10.4230/LIPICS.ICALP.2016.44MaRDI QIDQ4598183zbMATH OpenOpenAlexFDO

Authors Jarosław Błasiok, Jelani Nelson

Publication date 19 December 2017

Full work available at URL https://arxiv.org/abs/1602.05719

zbMATH Keywords

stochastic processesdictionary learninggeneric chaining

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Gaussian processes (60G15) Database theory (68P15)

Abstract: In "dictionary learning" we observe $Y=AX+E$ for some $Yinmathbb{R}^{nimesp}$, $Ainmathbb{R}^{mimesn}$, and $Xinmathbb{R}^{mimesp}$. The matrix $Y$ is observed, and $A,X,E$ are unknown. Here $E$ is "noise" of small norm, and $X$ is column-wise sparse. The matrix $A$ is referred to as a {em dictionary}, and its columns as {em atoms}. Then, given some small number $p$ of samples, i.e. columns of $Y$, the goal is to learn the dictionary $A$ up to small error, as well as $X$. The motivation is that in many applications data is expected to sparse when represented by atoms in the "right" dictionary $A$ (e.g. images in the Haar wavelet basis), and the goal is to learn $A$ from the data to then use it for other applications. Recently, [SWW12] proposed the dictionary learning algorithm ER-SpUD with provable guarantees when $E=0$ and $m=n$. They showed if $X$ has independent entries with an expected $s$ non-zeroes per column for $1lesssimslesssimsqrtn$, and with non-zero entries being subgaussian, then for $pgtrsim{n}^{2}lo{g}^{2}n$ with high probability ER-SpUD outputs matrices $A^{\prime },X^{\prime }$ which equal $A,X$ up to permuting and scaling columns (resp. rows) of $A$ (resp. $X$). They conjectured $pgtrsimnlogn$ suffices, which they showed was information theoretically necessary for {em any} algorithm to succeed when $ssimeq1$. Significant progress was later obtained in [LV15]. We show that for a slight variant of ER-SpUD, $pgtrsimnlog(n/delta)$ samples suffice for successful recovery with probability $1-delta$. We also show that for the unmodified ER-SpUD, $pgtrsim{n}^{1.99}$ samples are required even to learn $A,X$ with polynomially small success probability. This resolves the main conjecture of [SWW12], and contradicts the main result of [LV15], which claimed that $pgtrsimnlo{g}^{4}n$ guarantees success whp.

Recommendations

• A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries
• Sparse representation and performance analysis for LSP parameters via dictionary learning
• Sparsity and nullity: paradigms for analysis dictionary learning
• Analysis K-SVD: A Dictionary-Learning Algorithm for the Analysis Sparse Model
• A max-margin dictionary learning algorithm for sparse representation
• An improved algorithm for learning sparse parities in the presence of noise
• Dictionary Learning for Sparse Approximations With the Majorization Method
• Sparse and Spurious: Dictionary Learning With Noise and Outliers
• Dictionary Learning Algorithms for Sparse Representation

Cited in

(3)

• Provably accurate double-sparse coding
• A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries
• Identifiability of complete dictionary learning

This page was built for publication: An improved analysis of the ER-SpUD dictionary learning algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598183)