On Learning Sparsely Used Dictionaries from Incomplete Samples
Most existing algorithms for dictionary learning assume that all entries of the (high-dimensional) input data are fully observed. However, in several practical applications (such as hyper-spectral imaging or blood glucose monitoring), 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Dictionary LearningSimilar Papers 제목 키워드 기반
Towards Learning Sparsely Used Dictionaries with Arbitrary Supports
Dictionary learning is a popular approach for inferring a hidden basis or dictionary in which data has a sparse representation. Data generated from the dictionary A (an n by m matrix, with m > n in the over-complete sett…
Dictionary LearningA 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 …
ClusteringregressionLearning parametric dictionaries for graph signals
In sparse signal representation, the choice of a dictionary often involves a tradeoff between two desirable properties -- the ability to adapt to specific signal data and a fast implementation of the dictionary. To spars…
DenoisingDictionary LearningEfficient and Parallel Separable Dictionary Learning
Separable, or Kronecker product, dictionaries provide natural decompositions for 2D signals, such as images. In this paper, we describe a highly parallelizable algorithm that learns such dictionaries which reaches sparse…
DenoisingDictionary LearningImage DenoisingDictionary Learning for the Almost-Linear Sparsity Regime
Dictionary learning, the problem of recovering a sparsely used matrix $\mathbf{D} \in \mathbb{R}^{M \times K}$ and $N$ $s$-sparse vectors $\mathbf{x}_i \in \mathbb{R}^{K}$ from samples of the form $\mathbf{y}_i = \mathbf…
Dictionary Learning