2013/10/29 by Alekh Agarwal, Agarwal, Alekh, Animashree Anandkumar +5 · 1 citation
Computer Science · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and ELM #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1310.7991
openalex publication_date 2013/10/29 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
We consider the problem of sparse coding, where each sample consists of a\nsparse linear combination of a set of dictionary atoms, and the task is to\nlearn both the dictionary elements and the mixing coefficients. Alternating\nminimization is a popular heuristic for sparse coding, where the dictionary and\nthe coefficients are estimated in alternate steps, keeping the other fixed.\nTypically, the coefficients are estimated via \ℓ1 minimization, keeping\nthe dictionary fixed, and the dictionary is estimated through least squares,\nkeeping the coefficients fixed. In this paper, we establish local linear\nconvergence for this variant of alternating minimization and establish that the\nbasin of attraction for the global optimum (corresponding to the true\ndictionary and the coefficients) is order1/s2, where s is the sparsity\nlevel in each sample and the dictionary satisfies RIP. Combined with the recent\nresults of approximate dictionary estimation, this yields provable guarantees\nfor exact recovery of both the dictionary elements and the coefficients, when\nthe dictionary elements are incoherent.\n