Sparse dictionary learning
≈ 9 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Sparse dictionary learning (also known as sparse coding or SDL) is a representation learning method which aims to find a sparse representation of the input data in the form of a linear combination of basic elements as well as those basic elements themselves. These elements are called atoms, and they compose a dictionary. Atoms in the dictionary are not required to be orthogonal, and they may be an over-complete spanning set. This problem setup also allows the dimensionality of the signals being represented to be higher than any one of the signals being observed. These two properties lead to having seemingly redundant atoms that allow multiple representations of the same signal, but also provide an improvement in sparsity and flexibility of the representation. One of the most important applications of sparse dictionary learning is in the field of compressed sensing or signal recovery. In compressed sensing, a high-dimensional signal can be recovered with only a few linear measurements, provided that the signal is sparse or near-sparse. Since not all signals satisfy this condition, it is crucial to find a sparse representation of that signal such as the wavelet transform or the directional gradient of a rasterized matrix.…
Sparse dictionary learning (also known as sparse coding or SDL) is a representation learning method which aims to find a sparse representation of the input data in the form of a linear combination of basic elements as well as those basic elements themselves. These elements are called atoms, and they compose a dictionary. Atoms in the dictionary are not required to be orthogonal, and they may be an over-complete spanning set. This problem setup also allows the dimensionality of the signals being represented to be higher than any one of the signals being observed. These two properties lead to having seemingly redundant atoms that allow multiple representations of the same signal, but also provide an improvement in sparsity and flexibility of the representation. One of the most important applications of sparse dictionary learning is in the field of compressed sensing or signal recovery. In compressed sensing, a high-dimensional signal can be recovered with only a few linear measurements, provided that the signal is sparse or near-sparse. Since not all signals satisfy this condition, it is crucial to find a sparse representation of that signal such as the wavelet transform or the directional gradient of a rasterized matrix. Once a matrix or a high-dimensional vector is transferred to a sparse space, different recovery algorithms like basis pursuit, CoSaMP, or fast non-iterative algorithms can be used to recover the signal. One of the key principles of dictionary learning is that the dictionary has to be inferred from the input data. 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. Sparsity and overcomplete dictionaries have immense applications in image compression, image fusion, and inpainting. Given the input dataset X = [x_1, ..., x_K], x_i \in \mathbb{R}^d we wish to find a dictionary \mathbf{D} \in \mathbb{R}^{d \times n}: D = [d_1, ..., d_n] and a representation R = [r_1,...,r_K], r_i \in \mathbb{R}^n such that both \|X-\mathbf{D}R\|^2_F is minimized and the representations r_i are sparse enough. This can be formulated as the following optimization problem: \underset{\mathbf{D} \in \mathcal{C}, r_i \in \mathbb{R}^n}{\text{argmin}} \sum_{i=1}^K\|x_i-\mathbf{D}r_i\|_2^2+\lambda \|r_i\|_0 , where \mathcal{C} \equiv \{\mathbf{D} \in \mathbb{R}^{d \times n}: \|d_i\|_2 \leq 1 \,\, \forall i =1,...,n \} , \lambda>0 \mathcal{C} is required to constrain \mathbf{D} so that its atoms would not reach arbitrarily high values allowing for arbitrarily low (but non-zero) values of r_i . \lambda controls the trade off between the sparsity and the minimization error. The minimization problem above is not convex because of the ℓ 0 -"norm" and solving this problem is NP-hard. In some cases L 1 -norm is known to ensure sparsity and so the above becomes a convex optimization problem with respect to each of the variables \mathbf{D} and \mathbf{R} when the other one is fixed, but it is not jointly convex in (\mathbf{D}, \mathbf{R}) . 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 \mathbf{D} = XR^+ where R^+ is a Moore-Penrose pseudoinverse. After this update \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. \|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. \mathbf{D}_i = \text{proj}_{\mathcal{C}} \left\{\mathbf{D}_{i-1}-\delta_i\nabla_{\mathbf{D}}\sum_{i \in S}\|x_i-\mathbf{D}r_i\|_2^2+\lambda\|r_i\|_1 \right\} , where S is a random subset of \{1...K\} and \delta_i is a gradient step. \mathcal{L}(\mathbf{D}, \Lambda) = \text{tr}\left((X-\mathbf{D}R)^T(X-\mathbf{D}R)\right) + \sum_{j=1}^n\lambda_j \left({\sum_{i=1}^d\mathbf{D}_{ij}^2-c} \right) , where c is a constraint on the norm of the atoms and \lambda_i are the so-called dual variables forming the diagonal matrix \Lambda . We can then provide an analytical expression for the Lagrange dual after minimization over \mathbf{D} : \mathcal{D}(\Lambda) = \min_{\mathbf{D}}\mathcal{L}(\mathbf{D}, \Lambda) = \text{tr}(X^TX-XR^T(RR^T+\Lambda)^{-1}(XR^T)^T-c\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 \mathbf{D} : \mathbf{D}^T=(RR^T+\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.
LASSO
In this approach, the optimization problem is formulated as: \min_{r \in \mathbb{R}^n}\{\,\,\|r\|_1\} \,\, \text{subject to}\,\,\|X-\mathbf{D}R\|^2_F , where \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 1 -norm constraint in the solution vector, formulated as: \min_{r \in \mathbb{R}^n} \,\, \dfrac{1}{2}\,\,\|X-\mathbf{D}r\|^2_F + \lambda \,\,\|r\|_1 , where \lambda > 0 controls the trade-off between sparsity and the reconstruction error. This gives the global optimal solution. See also Online dictionary learning for Sparse coding Sparse dictionaries. This method focuses on not only providing a sparse representation but also constructing a sparse dictionary which is enforced by the expression \mathbf{D} = \mathbf{B}\mathbf{A} where \mathbf{B} is some pre-defined analytical dictionary with desirable properties such as fast computation and \mathbf{A} is a sparse matrix. Such formulation allows to directly combine the fast implementation of analytical dictionaries with the flexibility of sparse approaches. For t = 1...T: Draw a new sample x_t Find a sparse coding using LARS: r_t = \underset{r \in \mathbb{R}^n}{\text{argmin}}\left(\frac{1}{2}\|x_t-\mathbf{D}_{t-1}r\|+\lambda\|r\|_1\right) Update dictionary using block-coordinate approach: \mathbf{D}_t = \underset{\mathbf{D} \in \mathcal{C}}{\text{argmin}}\frac{1}{t}\sum_{i=1}^t\left(\frac{1}{2}\|x_i-\mathbf{D}r_i\|^2_2+\lambda\|r_i\|_1\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).
Text derived from https://en.wikipedia.org/w/index.php?oldid=1370370286 under CC BY-SA 4.0; modifications have been made.