K-SVD - Sparse Representation using Overcomplete Dictionaries
Table of Contents
[Paper] K-SVD - Overcomplete Dictionaries for Sparse Representation
1. Introduction
The paper focuses on sparse representation of signals, where a signal is expressed as a sparse linear combination of atoms from an overcomplete dictionary. Applications of sparse representation include compression, regularization in inverse problems, feature extraction, and image processing. While significant research has been done on pursuit algorithms for sparse decomposition, designing optimized dictionaries remains an open problem.
2. Terminology
- Sparse Representation
A signal \(y\) is represented as \(y = Dx\), where \(D\) is an overcomplete dictionary and \(x\) is a sparse coefficient vector.
The goal is to minimize the number of nonzero elements in \(x\) while preserving signal accuracy.
- Overcomplete Dictionary
- Dictionary \(D\) is a collection of sample signals. Where each sample \(d_i\) is called an atom. If the number of atoms is greater than the dimension of the signal then the dictionary is overcomplete. It is called overcomplete because if the dictionary is full rank, then it can be used to represent any other signal using a linear combination, and the solution to coefficents of that linear combination is not unique.
- Pursuit Algorithm
- Algorithm for finding the coefficents in linear combination of the atoms to recreate a given signal \(y\). The purpose is to find sparse combination.
- Dictionary Learning
- Dictionaries can be pre-selected (e.g., wavelets, curvelets) or learned from data. Learning-based approaches generally yield better results for specific data sets.
3. Contribution of the Paper
Introduces K-SVD, an iterative algorithm for designing overcomplete dictionaries that optimize sparse representation. K-SVD generalizes the K-means clustering approach, alternating between sparse coding and dictionary updating for better signal representation. The algorithm can be used with different pursuit methods like Basis Pursuit, Matching Pursuit, and FOCUSS.
4. The K-SVD Algorithm
Step 1: Sparse Coding
Given a dictionary \(D\), find a sparse representation \(x\) for each training signal using a pursuit algorithm.
Step 2: Dictionary Update
Update one dictionary column \(d_i\) at a time using Singular Value Decomposition (SVD). [See Page 7]
Unlike previous methods, K-SVD updates dictionary atoms and their corresponding coefficients simultaneously, leading to faster convergence.
Step 3: Iterate Until Convergence
The process continues iteratively until the reconstruction error stabilizes.
5. Experimental Results
Image Processing Applications:
Image Denoising: K-SVD-trained dictionaries achieve better reconstruction of missing pixels compared to wavelet and DCT-based methods. [See Figure 7]
- Compression: A learned dictionary provides superior compression efficiency compared to standard overcomplete Haar and DCT dictionaries.
6. Conclusion
K-SVD is a powerful, flexible, and efficient dictionary learning algorithm for sparse representation. It improves over existing methods by combining sparse coding and adaptive dictionary updates using SVD. The paper suggests that learned dictionaries can significantly enhance image processing applications such as denoising, inpainting, and compression.