Sparse dictionary learning#Properties of the dictionary

Given the input dataset $X\; =\; [x\_1,\; ...,\; x\_K],\; x\_i\; \backslash in\; \backslash mathbb\{R\}^d$ we wish to find a dictionary $\backslash mathbf\{D\}\; \backslash in\; \backslash mathbb\{R\}^\{d\; \backslash times\; n\}:\; D\; =\; [d\_1,\; ...,\; d\_n]$ and a representation $R\; =\; [r\_1,...,r\_K],\; r\_i\; \backslash in\; \backslash mathbb\{R\}^n$ such that both $\backslash |X-\backslash mathbf\{D\}R\backslash |^2\_F$ is minimized and the representations $r\_i$ are sparse enough. This can be formulated as the following optimization problem:

$\backslash underset\{\backslash mathbf\{D\}\; \backslash in\; \backslash mathcal\{C\},\; r\_i\; \backslash in\; \backslash mathbb\{R\}^n\}\{\backslash text\{argmin\}\}\; \backslash sum\_\{i=1\}^K\backslash |x\_i-\backslash mathbf\{D\}r\_i\backslash |\_2^2+\backslash lambda\; \backslash |r\_i\backslash |\_0$, where $\backslash mathcal\{C\}\; \backslash equiv\; \backslash \{\backslash mathbf\{D\}\; \backslash in\; \backslash mathbb\{R\}^\{d\; \backslash times\; n\}:\; \backslash |d\_i\backslash |\_2\; \backslash leq\; 1\; \backslash ,\backslash ,\; \backslash forall\; i\; =1,...,n\; \backslash \}$, $\backslash lambda>0$

$\backslash mathcal\{C\}$ is required to constrain $\backslash mathbf\{D\}$ so that its atoms would not reach arbitrarily high values allowing for arbitrarily low (but non-zero) values of $r\_i$. $\backslash lambda$ controls the trade off between the sparsity and the minimization error.

The minimization problem above is not convex because of the ℓ₀-"norm" and solving this problem is NP-hard.A. M. Tillmann, "On the Computational Intractability of Exact and Approximate Dictionary Learning", IEEE Signal Processing Letters 22(1), 2015: 45–49. In some cases L¹-norm is known to ensure sparsity{{Cite journal|title = For most large underdetermined systems of linear equations the minimal 𝓁1-norm solution is also the sparsest solution|journal = Communications on Pure and Applied Mathematics|date = 2006-06-01|issn = 1097-0312|pages = 797–829|volume = 59|issue = 6|doi = 10.1002/cpa.20132|first = David L.|last = Donoho| s2cid=8510060 }} and so the above becomes a convex optimization problem with respect to each of the variables $\backslash mathbf\{D\}$ and $\backslash mathbf\{R\}$ when the other one is fixed, but it is not jointly convex in $(\backslash mathbf\{D\},\; \backslash mathbf\{R\})$.

The dictionary $\backslash mathbf\{D\}$ defined above can be "undercomplete" if or "overcomplete" in case $n>d$ with the latter being a typical assumption for a sparse dictionary learning problem. 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 $d\_1,...,d\_n$ to be orthogonal. 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. However, their main downside is limiting the choice of atoms.

Overcomplete dictionaries, however, do not require the atoms to be orthogonal (they will never have a basis anyway) thus allowing for more flexible dictionaries and richer data representations.

An overcomplete dictionary which allows for sparse representation of signal can be a famous transform matrix (wavelets transform, fourier transform) or it can be formulated so that its elements are changed in such a way that it sparsely represents the given signal in a best way. Learned dictionaries are capable of giving sparser solutions as compared to predefined transform matrices.

As the optimization problem described above can be solved as a convex problem with respect to either dictionary or sparse coding while the other one of the two is fixed, most of the algorithms are based on the idea of iteratively updating one and then the other.

The problem of finding an optimal sparse coding $R$ with a given dictionary $\backslash mathbf\{D\}$ is known as sparse approximation (or sometimes just sparse coding problem). A number of algorithms have been developed to solve it (such as matching pursuit and LASSO) and are incorporated in the algorithms described below.

The method of optimal directions (or MOD) was one of the first methods introduced to tackle the sparse dictionary learning problem.{{Cite book|date = 1999-01-01|pages = 2443–2446 vol.5|volume = 5|doi = 10.1109/ICASSP.1999.760624|first1 = K.|last1 = Engan|author-link=Kjersti Engan|first2 = S.O.|last2 = Aase|first3 = J.|last3 = Hakon Husoy| title=1999 IEEE International Conference on Acoustics, Speech, and Signal Processing. Proceedings. ICASSP99 (Cat. No.99CH36258) | chapter=Method of optimal directions for frame design |isbn = 978-0-7803-5041-0|s2cid = 33097614}} The core idea of it is to solve the minimization problem subject to the limited number of non-zero components of the representation vector:

$\backslash min\_\{\backslash mathbf\{D\},\; R\}\backslash \{\backslash |X-\backslash mathbf\{D\}R\backslash |^2\_F\backslash \}\; \backslash ,\backslash ,\; \backslash text\{s.t.\}\backslash ,\backslash ,\; \backslash forall\; i\; \backslash ,\backslash ,\backslash |r\_i\backslash |\_0\; \backslash leq\; T$

Here, $F$ denotes the Frobenius norm. 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 $\backslash mathbf\{D\}\; =\; XR^+$ where $R^+$ is a Moore-Penrose pseudoinverse. After this update $\backslash mathbf\{D\}$ is renormalized to fit the constraints and the new sparse coding is obtained again. The process is repeated until convergence (or until a sufficiently small residue).

MOD has proved to be a very efficient method for low-dimensional input data $X$ requiring just a few iterations to converge. However, due to the high complexity of the matrix-inversion operation, computing the pseudoinverse in high-dimensional cases is in many cases intractable. This shortcoming has inspired the development of other dictionary learning methods.

{{main|K-SVD}}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. It enforces that each element of the input data $x\_i$ is encoded by a linear combination of not more than $T\_0$ elements in a way identical to the MOD approach:

$\backslash min\_\{\backslash mathbf\{D\},\; R\}\backslash \{\backslash |X-\backslash mathbf\{D\}R\backslash |^2\_F\backslash \}\; \backslash ,\backslash ,\; \backslash text\{s.t.\}\backslash ,\backslash ,\; \backslash forall\; i\; \backslash ,\backslash ,\backslash |r\_i\backslash |\_0\; \backslash leq\; T\_0$

This algorithm's essence is to first fix the dictionary, find the best possible $R$ under the above constraint (using Orthogonal Matching Pursuit) and then iteratively update the atoms of dictionary $\backslash mathbf\{D\}$ in the following manner:

\|X - \mathbf{D}R\|^2_F = \left| X - \sum_{i = 1}^K d_i x^i_T\right|^2_F = \| E_k - d_k x^k_T\|^2_F

The next steps of the algorithm include rank-1 approximation of the residual matrix $$

E_k

, updating $$

d_k

and enforcing the sparsity of $$

x_k

after the update. 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.

{{Main|Stochastic gradient descent}}One can also apply a widespread stochastic gradient descent method with iterative projection to solve this problem.{{Cite journal|title = Sparse and Redundant Modeling of Image Content Using an Image-Signature-Dictionary|journal = SIAM Journal on Imaging Sciences|pages = 228–247|volume = 1|issue = 3|doi = 10.1137/07070156x|first1 = Michal|last1 = Aharon|author1-link=Michal Aharon|first2 = Michael|last2 = Elad|year = 2008|citeseerx = 10.1.1.298.6982}} The idea of this method is to update the dictionary using the first order stochastic gradient and project it on the constraint set $\backslash mathcal\{C\}$. The step that occurs at i-th iteration is described by this expression:

$\backslash mathbf\{D\}\_i\; =\; \backslash text\{proj\}\_\{\backslash mathcal\{C\}\}\; \backslash left\backslash \{\backslash mathbf\{D\}\_\{i-1\}-\backslash delta\_i\backslash nabla\_\{\backslash mathbf\{D\}\}\backslash sum\_\{i\; \backslash in\; S\}\backslash |x\_i-\backslash mathbf\{D\}r\_i\backslash |\_2^2+\backslash lambda\backslash |r\_i\backslash |\_1\; \backslash right\backslash \}$, where $S$ is a random subset of $\backslash \{1...K\backslash \}$ and $\backslash delta\_i$ is a gradient step.

An algorithm based on solving a dual Lagrangian problem provides an efficient way to solve for the dictionary having no complications induced by the sparsity function.Lee, Honglak, et al. "Efficient sparse coding algorithms." Advances in neural information processing systems. 2006. Consider the following Lagrangian:

$\backslash mathcal\{L\}(\backslash mathbf\{D\},\; \backslash Lambda)\; =\; \backslash text\{tr\}\backslash left((X-\backslash mathbf\{D\}R)^T(X-\backslash mathbf\{D\}R)\backslash right)\; +\; \backslash sum\_\{j=1\}^n\backslash lambda\_j\; \backslash left(\{\backslash sum\_\{i=1\}^d\backslash mathbf\{D\}\_\{ij\}^2-c\}\; \backslash right)$, where $c$ is a constraint on the norm of the atoms and $\backslash lambda\_i$ are the so-called dual variables forming the diagonal matrix $\backslash Lambda$.

We can then provide an analytical expression for the Lagrange dual after minimization over $\backslash mathbf\{D\}$:

$\backslash mathcal\{D\}(\backslash Lambda)\; =\; \backslash min\_\{\backslash mathbf\{D\}\}\backslash mathcal\{L\}(\backslash mathbf\{D\},\; \backslash Lambda)\; =\; \backslash text\{tr\}(X^TX-XR^T(RR^T+\backslash Lambda)^\{-1\}(XR^T)^T-c\backslash Lambda)$.

After applying one of the optimization methods to the value of the dual (such as Newton's method or conjugate gradient) we get the value of $\backslash mathbf\{D\}$:

$\backslash mathbf\{D\}^T=(RR^T+\backslash Lambda)^\{-1\}(XR^T)^T$

Solving this problem is less computational hard because the amount of dual variables $n$ is a lot of times much less than the amount of variables in the primal problem.

{{main|Lasso (statistics)}}

In this approach, the optimization problem is formulated as:

, where $\backslash epsilon$ is the permitted error in the reconstruction LASSO.

It finds an estimate of $r\_i$ by minimizing the least square error subject to a L¹-norm constraint in the solution vector, formulated as:

$\backslash min\_\{r\; \backslash in\; \backslash mathbb\{R\}^n\}\; \backslash ,\backslash ,\; \backslash dfrac\{1\}\{2\}\backslash ,\backslash ,\backslash |X-\backslash mathbf\{D\}r\backslash |^2\_F\; +\; \backslash lambda\; \backslash ,\backslash ,\backslash |r\backslash |\_1$, where $\backslash lambda\; >\; 0$ controls the trade-off between sparsity and the reconstruction error. This gives the global optimal solution.{{Cite web|url=http://home.iitk.ac.in/~saurabhk/EE609A_12011_12807637_.pdf|title=Dictionary Learning Based Applications in Image Processing using Convex Optimisation|last1=Kumar|first1=Abhay|last2=Kataria|first2=Saurabh}} See also [https://www.di.ens.fr/~fbach/mairal_icml09.pdf Online dictionary learning for Sparse coding]

Parametric training methods are aimed to incorporate the best of both worlds — the realm of analytically constructed dictionaries and the learned ones.{{Cite journal|title = Dictionaries for Sparse Representation Modeling|journal = Proceedings of the IEEE|date = 2010-06-01|issn = 0018-9219|pages = 1045–1057|volume = 98|issue = 6|doi = 10.1109/JPROC.2010.2040551|first1 = R.|last1 = Rubinstein|first2 = A.M.|last2 = Bruckstein|first3 = M.|last3 = Elad|citeseerx = 10.1.1.160.527|s2cid = 2176046}} This allows to construct more powerful generalized dictionaries that can potentially be applied to the cases of arbitrary-sized signals. Notable approaches include:

• Translation-invariant dictionaries.{{Cite journal|title = Family of Iterative LS-based Dictionary Learning Algorithms, ILS-DLA, for Sparse Signal Representation|journal = Digit. Signal Process.|date = 2007-01-01|issn = 1051-2004|pages = 32–49|volume = 17|issue = 1|doi = 10.1016/j.dsp.2006.02.002|first1 = Kjersti|last1 = Engan|author-link=Kjersti Engan|first2 = Karl|last2 = Skretting|first3 = John H\a akon|last3 = Husøy| bibcode=2007DSP....17...32E }} These dictionaries are composed by the translations of the atoms originating from the dictionary constructed for a finite-size signal patch. This allows the resulting dictionary to provide a representation for the arbitrary-sized signal.
• Multiscale dictionaries.{{Cite journal|title = Learning Multiscale Sparse Representations for Image and Video Restoration|journal = Multiscale Modeling & Simulation|date = 2008-01-01|issn = 1540-3459|pages = 214–241|volume = 7|issue = 1|doi = 10.1137/070697653|first1 = J.|last1 = Mairal|first2 = G.|last2 = Sapiro|first3 = M.|last3 = Elad|citeseerx = 10.1.1.95.6239}} This method focuses on constructing a dictionary that is composed of differently scaled dictionaries to improve sparsity.
• Sparse dictionaries.{{Cite journal|title = Double Sparsity: Learning Sparse Dictionaries for Sparse Signal Approximation|journal = IEEE Transactions on Signal Processing|date = 2010-03-01|issn = 1053-587X|pages = 1553–1564|volume = 58|issue = 3|doi = 10.1109/TSP.2009.2036477|first1 = R.|last1 = Rubinstein|first2 = M.|last2 = Zibulevsky|first3 = M.|last3 = Elad|citeseerx = 10.1.1.183.992|bibcode = 2010ITSP...58.1553R|s2cid = 7193037}} This method focuses on not only providing a sparse representation but also constructing a sparse dictionary which is enforced by the expression $\backslash mathbf\{D\}\; =\; \backslash mathbf\{B\}\backslash mathbf\{A\}$ where $\backslash mathbf\{B\}$ is some pre-defined analytical dictionary with desirable properties such as fast computation and $\backslash mathbf\{A\}$ is a sparse matrix. Such formulation allows to directly combine the fast implementation of analytical dictionaries with the flexibility of sparse approaches.

Many common approaches to sparse dictionary learning rely on the fact that the whole input data $X$ (or at least a large enough training dataset) is available for the algorithm. 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 $x$ becoming available.

A dictionary can be learned in an online manner the following way:{{Cite journal|title = Online Learning for Matrix Factorization and Sparse Coding|url = http://dl.acm.org/citation.cfm?id=1756006.1756008|journal = J. Mach. Learn. Res.|date = 2010-03-01|issn = 1532-4435|pages = 19–60|volume = 11|first1 = Julien|last1 = Mairal|first2 = Francis|last2 = Bach|first3 = Jean|last3 = Ponce|first4 = Guillermo|last4 = Sapiro|bibcode = 2009arXiv0908.0050M|arxiv = 0908.0050}}

1. For $t\; =\; 1...T:$
2. Draw a new sample $x\_t$
3. Find a sparse coding using LARS: $r\_t\; =\; \backslash underset\{r\; \backslash in\; \backslash mathbb\{R\}^n\}\{\backslash text\{argmin\}\}\backslash left(\backslash frac\{1\}\{2\}\backslash |x\_t-\backslash mathbf\{D\}\_\{t-1\}r\backslash |+\backslash lambda\backslash |r\backslash |\_1\backslash right)$
4. Update dictionary using block-coordinate approach: $\backslash mathbf\{D\}\_t\; =\; \backslash underset\{\backslash mathbf\{D\}\; \backslash in\; \backslash mathcal\{C\}\}\{\backslash text\{argmin\}\}\backslash frac\{1\}\{t\}\backslash sum\_\{i=1\}^t\backslash left(\backslash frac\{1\}\{2\}\backslash |x\_i-\backslash mathbf\{D\}r\_i\backslash |^2\_2+\backslash lambda\backslash |r\_i\backslash |\_1\backslash right)$

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|date=August 2024}} results in various image and video processing tasks. This technique can be applied to classification problems in a way that if we have built specific dictionaries for each class, the input signal can be classified by finding the dictionary corresponding to the sparsest representation.

It also has properties that are useful for signal denoising since usually one can learn a dictionary to represent the meaningful part of the input signal in a sparse way but the noise in the input will have a much less sparse representation.Aharon, M, M Elad, and A Bruckstein. 2006. "[https://freddy.cs.technion.ac.il/wp-content/uploads/2017/12/K-SVD-An-Algorithm-for-Designing-Overcomplete.pdf K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation]." Signal Processing, IEEE Transactions on 54 (11): 4311-4322

Sparse dictionary learning has been successfully applied to various image, video and audio processing tasks as well as to texture synthesis{{Cite journal|title = Sparse Modeling of Textures|journal = Journal of Mathematical Imaging and Vision|date = 2008-11-06|issn = 0924-9907|pages = 17–31|volume = 34|issue = 1|doi = 10.1007/s10851-008-0120-3|first = Gabriel|last = Peyré|s2cid = 15994546|url = https://hal.archives-ouvertes.fr/hal-00359747/file/08-JMIV-Peyre-SparseTextures.pdf}} and unsupervised clustering.{{Cite book|url = http://www.computer.org/csdl/proceedings/cvpr/2010/6984/00/05539964-abs.html|publisher = IEEE Computer Society|date = 2010-01-01|location = Los Alamitos, CA, USA|isbn = 978-1-4244-6984-0|pages = 3501–3508|doi = 10.1109/CVPR.2010.5539964|first1 = Ignacio|last1 = Ramirez|first2 = Pablo|last2 = Sprechmann|first3 = Guillermo|last3 = Sapiro| title=2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition | chapter=Classification and clustering via dictionary learning with structured incoherence and shared features |s2cid = 206591234}} In evaluations with the Bag-of-Words model,{{Cite journal|last1=Koniusz|first1=Piotr|last2=Yan|first2=Fei|last3=Mikolajczyk|first3=Krystian|date=2013-05-01|title=Comparison of mid-level feature coding approaches and pooling strategies in visual concept detection|journal=Computer Vision and Image Understanding|volume=117|issue=5|pages=479–492|doi=10.1016/j.cviu.2012.10.010|issn=1077-3142|citeseerx=10.1.1.377.3979}}{{Cite journal|last1=Koniusz|first1=Piotr|last2=Yan|first2=Fei|last3=Gosselin|first3=Philippe Henri|last4=Mikolajczyk|first4=Krystian|date=2017-02-24|title=Higher-order occurrence pooling for bags-of-words: Visual concept detection|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=39|issue=2|pages=313–326|doi=10.1109/TPAMI.2016.2545667|pmid=27019477|issn=0162-8828|hdl=10044/1/39814|s2cid=10577592 |url=http://spiral.imperial.ac.uk/bitstream/10044/1/39814/2/pkpami2e-peter.pdf|hdl-access=free}} sparse coding was found empirically to outperform other coding approaches on the object category recognition tasks.

Dictionary learning is used to analyse medical signals in detail. Such medical signals include those from electroencephalography (EEG), electrocardiography (ECG), magnetic resonance imaging (MRI), functional MRI (fMRI), continuous glucose monitors {{Cite journal|last1=AlMatouq|first1=Ali|last2=LalegKirati|first2=TaousMeriem|last3=Novara|first3=Carlo|last4=Ivana|first4=Rabbone|last5=Vincent|first5=Tyrone|date=2019-03-15|title=Sparse Reconstruction of Glucose Fluxes Using Continuous Glucose Monitors|journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics|volume=17|issue=5|pages=1797–1809|doi=10.1109/TCBB.2019.2905198|pmid=30892232|issn=1545-5963|url=https://ieeexplore.ieee.org/document/8667648|hdl=10754/655914|s2cid=84185121|hdl-access=free}} and ultrasound computer tomography (USCT), where different assumptions are used to analyze each signal.

• Sparse approximation
• Sparse PCA
• K-SVD
• Matrix factorization
• Neural sparse coding

Category:Unsupervised learning