Sparse dictionary learning

One of the most important applications of sparse dictionary learning is in the field of compressed sensing or signal recovery.

The emergence of sparse dictionary learning methods was stimulated by the fact that in signal processing, one typically wants to represent the input data using a minimal amount of components.

Before this approach, the general practice was to use predefined dictionaries such as Fourier or wavelet transforms.

However, in certain cases, a dictionary that is trained to fit the input data can significantly improve the sparsity, which has applications in data decomposition, compression, and analysis, and has been used in the fields of image denoising and classification, and video and audio processing.

[3] In some cases L1-norm is known to ensure sparsity[4] and so the above becomes a convex optimization problem with respect to each of the variables

The case of a complete dictionary does not provide any improvement from a representational point of view and thus isn't considered.

Undercomplete dictionaries represent the setup in which the actual input data lies in a lower-dimensional space.

This case is strongly related to dimensionality reduction and techniques like principal component analysis which require atoms

The choice of these subspaces is crucial for efficient dimensionality reduction, but it is not trivial.

And dimensionality reduction based on dictionary representation can be extended to address specific tasks such as data analysis or classification.

Learned dictionaries are capable of giving sparser solutions as compared to predefined transform matrices.

[5] The core idea of it is to solve the minimization problem subject to the limited number of non-zero components of the representation vector:

MOD alternates between getting the sparse coding using a method such as matching pursuit and updating the dictionary by computing the analytical solution of the problem given by

MOD has proved to be a very efficient method for low-dimensional input data

K-SVD is an algorithm that performs SVD at its core to update the atoms of the dictionary one by one and basically is a generalization of K-means.

under the above constraint (using Orthogonal Matching Pursuit) and then iteratively update the atoms of dictionary

This algorithm is considered to be standard for dictionary learning and is used in a variety of applications.

However, it shares weaknesses with MOD being efficient only for signals with relatively low dimensionality and having the possibility for being stuck at local minima.

One can also apply a widespread stochastic gradient descent method with iterative projection to solve this problem.

[6] The idea of this method is to update the dictionary using the first order stochastic gradient and project it on the constraint set

Solving this problem is less computational hard because the amount of dual variables

by minimizing the least square error subject to a L1-norm constraint in the solution vector, formulated as:

[9] This allows to construct more powerful generalized dictionaries that can potentially be applied to the cases of arbitrary-sized signals.

However, this might not be the case in the real-world scenario as the size of the input data might be too big to fit it into memory.

The other case where this assumption can not be made is when the input data comes in a form of a stream.

Such cases lie in the field of study of online learning which essentially suggests iteratively updating the model upon the new data points

A dictionary can be learned in an online manner the following way:[13] This method allows us to gradually update the dictionary as new data becomes available for sparse representation learning and helps drastically reduce the amount of memory needed to store the dataset (which often has a huge size).

The dictionary learning framework, namely the linear decomposition of an input signal using a few basis elements learned from data itself, has led to state-of-art[citation needed] results in various image and video processing tasks.

[14] Sparse dictionary learning has been successfully applied to various image, video and audio processing tasks as well as to texture synthesis[15] and unsupervised clustering.

Such medical signals include those from electroencephalography (EEG), electrocardiography (ECG), magnetic resonance imaging (MRI), functional MRI (fMRI), continuous glucose monitors [19] and ultrasound computer tomography (USCT), where different assumptions are used to analyze each signal.