A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries

Abstract

We consider the problem of recovering an invertible $n\times n$ matrix $A$ and a sparse $n\times p$ random matrix $X$ based on the observation of $Y=AX$ (up to a scaling and permutation of columns of $A$ and rows of $X$). Using only elementary tools from the theory of empirical processes we show that a version of the Er-SpUD algorithm by Spielman, Wang and Wright with high probability recovers $A$ and $X$ exactly, provided that $p\ge Cn\log n$, which is optimal up to the constant $C$.

Minor typos corrected

Cited by in corpus (2)

• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• An improved analysis of the ER-SpUD dictionary learning algorithm