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

作者：Adamczak Radoslaw^*

来源：Journal of Machine Learning Research, 2016, 17: 1-18.

• sparse dictionaries
• Er-SpUD algorithm
• l(1) minimization
• exact recovery
• sample complexity

We consider the problem of recovering an invertible n x n matrix A and a sparse n x 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 >= Cn log n, which is optimal up to the constant C.

• 出版日期2016