On Learning Sparsely Used Dictionaries from Incomplete Samples

Thanh Nguyen, Akshay Soni, Chinmay Hegde
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:3769-3778, 2018.

Abstract

Existing algorithms for dictionary learning assume that the entries of the (high-dimensional) input data are fully observed. However, in several practical applications, only an incomplete fraction of the data entries may be available. For incomplete settings, no provably correct and polynomial-time algorithm has been reported in the dictionary learning literature. In this paper, we provide provable approaches for learning – from incomplete samples – a family of dictionaries whose atoms have sufficiently “spread-out” mass. First, we propose a descent-style iterative algorithm that linearly converges to the true dictionary when provided a sufficiently coarse initial estimate. Second, we propose an initialization algorithm that utilizes a small number of extra fully observed samples to produce such a coarse initial estimate. Finally, we theoretically analyze their performance and provide asymptotic statistical and computational guarantees.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-nguyen18e, title = {On Learning Sparsely Used Dictionaries from Incomplete Samples}, author = {Nguyen, Thanh and Soni, Akshay and Hegde, Chinmay}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {3769--3778}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/nguyen18e/nguyen18e.pdf}, url = {https://proceedings.mlr.press/v80/nguyen18e.html}, abstract = {Existing algorithms for dictionary learning assume that the entries of the (high-dimensional) input data are fully observed. However, in several practical applications, only an incomplete fraction of the data entries may be available. For incomplete settings, no provably correct and polynomial-time algorithm has been reported in the dictionary learning literature. In this paper, we provide provable approaches for learning – from incomplete samples – a family of dictionaries whose atoms have sufficiently “spread-out” mass. First, we propose a descent-style iterative algorithm that linearly converges to the true dictionary when provided a sufficiently coarse initial estimate. Second, we propose an initialization algorithm that utilizes a small number of extra fully observed samples to produce such a coarse initial estimate. Finally, we theoretically analyze their performance and provide asymptotic statistical and computational guarantees.} }
Endnote
%0 Conference Paper %T On Learning Sparsely Used Dictionaries from Incomplete Samples %A Thanh Nguyen %A Akshay Soni %A Chinmay Hegde %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-nguyen18e %I PMLR %P 3769--3778 %U https://proceedings.mlr.press/v80/nguyen18e.html %V 80 %X Existing algorithms for dictionary learning assume that the entries of the (high-dimensional) input data are fully observed. However, in several practical applications, only an incomplete fraction of the data entries may be available. For incomplete settings, no provably correct and polynomial-time algorithm has been reported in the dictionary learning literature. In this paper, we provide provable approaches for learning – from incomplete samples – a family of dictionaries whose atoms have sufficiently “spread-out” mass. First, we propose a descent-style iterative algorithm that linearly converges to the true dictionary when provided a sufficiently coarse initial estimate. Second, we propose an initialization algorithm that utilizes a small number of extra fully observed samples to produce such a coarse initial estimate. Finally, we theoretically analyze their performance and provide asymptotic statistical and computational guarantees.
APA
Nguyen, T., Soni, A. & Hegde, C.. (2018). On Learning Sparsely Used Dictionaries from Incomplete Samples. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:3769-3778 Available from https://proceedings.mlr.press/v80/nguyen18e.html.

Related Material