2017/11/09 by Niladri S. Chatterji, Peter L. Bartlett, Chatterji, Niladri S. +1 · 1 citation
Computer Science · Engineering · #Blind Source Separation Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Microwave Imaging and Scattering Analysis #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1711.03634
openalex publication_date 2017/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present theoretical guarantees for an alternating minimization algorithm for the dictionary learning/sparse coding problem. The dictionary learning problem is to factorize vector samples y1,y2,…, yn into an appropriate basis (dictionary) A^* and sparse vectors x1*,…,xn*. Our algorithm is a simple alternating minimization procedure that switches between ℓ1 minimization and gradient descent in alternate steps. Dictionary learning and specifically alternating minimization algorithms for dictionary learning are well studied both theoretically and empirically. However, in contrast to previous theoretical analyses for this problem, we replace a condition on the operator norm (that is, the largest magnitude singular value) of the true underlying dictionary A^* with a condition on the matrix infinity norm (that is, the largest magnitude term). Our guarantees are under a reasonable generative model that allows for dictionaries with growing operator norms, and can handle an arbitrary level of overcompleteness, while having sparsity that is information theoretically optimal. We also establish upper bounds on the sample complexity of our algorithm.