## A Note on the Sample Complexity of the Er-SpUD Algorithm by Spielman, Wang and Wright for Exact Recovery of Sparsely Used Dictionaries

*Radoslaw Adamczak*; 17(177):1−18, 2016.

### 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$.

[abs][pdf][bib]