Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization
We consider the problem of sparse coding, where each sample consists of a sparse linear combination of a set of dictionary atoms, and the task is to learn both the dictionary elements and the mixing coefficients. Alternating minimization is a popular heuristic for sparse coding, where the dictionary and the coefficients are estimated in alternate steps, keeping the other fixed. Typically, the coefficients are estimated via $\ell_1$ minimization, keeping the dictionary fixed, and the dictionary is estimated through least squares, keeping the coefficients fixed. In this paper, we establish local linear convergence for this variant of alternating minimization and establish that the basin of attraction for the global optimum (corresponding to the true dictionary and the coefficients) is $\order{1/s^2}$, where $s$ is the sparsity level in each sample and the dictionary satisfies RIP. Combined with the recent results of approximate dictionary estimation, this yields provable guarantees for exact recovery of both the dictionary elements and the coefficients, when the dictionary elements are incoherent.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Clustering Approach to Learn Sparsely-Used Overcomplete Dictionaries
We consider the problem of learning overcomplete 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 …
Clusteringregression3D seismic data denoising using two-dimensional sparse coding scheme
Seismic data denoising is vital to geophysical applications and the transform-based function method is one of the most widely used techniques. However, it is challenging to design a suit- able sparse representation to ex…
DenoisingVocal Bursts Valence PredictionAlternating minimization for dictionary learning: Local Convergence Guarantees
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 $y^{1},y^{2},\ldots, y^{n}$ in…
Dictionary LearningGeometric Analysis of Nonconvex Optimization Landscapes for Overcomplete Learning
Learning overcomplete representations finds many applications in machine learning and data analytics. In the past decade, despite the empirical success of heuristic methods, theoretical understandings and explanations of…
Representation LearningAlternating minimization for dictionary learning with random initialization
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 $y^{1},y^{2},\ldots, y^{n}$ in…
Dictionary Learning