A Clustering Approach to Learning Sparsely Used Overcomplete Dictionaries

Agarwal, Alekh and Anandkumar, Animashree and Netrapalli, Praneeth (2017) A Clustering Approach to Learning Sparsely Used Overcomplete Dictionaries. IEEE Transactions on Information Theory, 63 (1). pp. 575-592. ISSN 0018-9448. doi:10.1109/TIT.2016.2614684. https://resolver.caltech.edu/CaltechAUTHORS:20170920-111802806

PDF - Submitted Version
See Usage Policy.
350kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170920-111802806

Abstract

We consider the problem of learning over complete dictionaries in the context of sparse coding, where each sample selects a sparse subset of dictionary elements. Our main result is a strategy to approximately recover the unknown dictionary using an efficient algorithm. Our algorithm is a clustering-style procedure, where each cluster is used to estimate a dictionary element. The resulting solution can often be further cleaned up to obtain a high accuracy estimate, and we provide one simple scenario where ℓ_1-regularized regression can be used for such a second stage.

Item Type:

Article

Related URLs:

URL	URL Type	Description
https://doi.org/10.1109/TIT.2016.2614684	DOI	Article
http://ieeexplore.ieee.org/document/7580653/	Publisher	Article
https://arxiv.org/abs/1309.1952	arXiv	Discussion Paper

Additional Information:

© 2017 IEEE. Manuscript received July 6, 2014; revised June 6, 2016; accepted September 11, 2016. Date of publication September 30, 2016; date of current version December 20, 2016. A. Anandkumar was supported in part by the Microsoft Faculty Fellowship, in part by the NSF Career Award under Grant CCF1254106, in part by the NSF Award under Grant CCF-1219234, and in part by the ARO YIP Award under Grant W911NF-13-1-0084. This paper was presented at the 2014 COLT.

Funders:

Funding Agency	Grant Number
Microsoft Research	UNSPECIFIED
NSF	CCF-1254106
NSF	CCF-1219234
Army Research Office (ARO)	W911NF-13-1-0084

Subject Keywords:

Dictionary learning, sparse coding, overcomplete dictionaries, incoherence, lasso

Issue or Number:

DOI:

10.1109/TIT.2016.2614684

Record Number:

CaltechAUTHORS:20170920-111802806

Persistent URL:

https://resolver.caltech.edu/CaltechAUTHORS:20170920-111802806

Official Citation:

A. Agarwal, A. Anandkumar and P. Netrapalli, "A Clustering Approach to Learning Sparsely Used Overcomplete Dictionaries," in IEEE Transactions on Information Theory, vol. 63, no. 1, pp. 575-592, Jan. 2017. doi: 10.1109/TIT.2016.2614684 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7580653&isnumber=7792231

Usage Policy:

No commercial reproduction, distribution, display or performance rights in this work are provided.

ID Code:

81620

Collection:

CaltechAUTHORS

Deposited By:

Tony Diaz

Deposited On:

20 Sep 2017 18:55

Last Modified:

15 Nov 2021 19:44

Repository Staff Only: item control page