# Fast and Efficient Union of Sparse Orthonormal Transforms via DCT and Bayesian Optimization +
## 2 Related Works  
### Sparse Orthonormal Transform  
For sparse coding based on an overcomplete dictionary, finding an appropriate dictionary is generally a non-deterministic polynomial time-hard problem. This problem requires iterative optimization such as the method of optimal directions (MOD), the alternating direction method of multipliers (ADMM) [16], and augmented Lagrange multipliers (ALM) [17], with greedy algorithms, such as basis pursuit and orthogonal matching pursuit to estimate the approximate value [1]. These methods help solve the sparse approximation problem but inevitably require considerable time and memory resources for learning. Therefore, designing fast and efficient dictionary learning algorithms is one of the main problems in the field. Compared with overcomplete dictionary-based sparse coding, orthogonal sparse coding techniques are mathematically simple because they remove iterations in sub-optimizations, and they use much smaller dictionaries. They can compute the orthogonal dictionary via singular value decomposition, and the inner products and thresholding easily compute the coefficients. Of course, the singular value decomposition is not efficient in the high-dimensional case, but in the case of a general block size for image transformation, it is efficient enough. Therefore, orthogonal sparse coding is much faster than overcomplete sparse coding for image transform.  
Furthermore, the orthonormal dictionary can be applied as a dictionary form as well as a transform because the inverse matrix of the orthonormal dictionary is its transpose. In short, the orthonormal dictionary via sparse coding has the same properties as the analytic transforms. Therefore, many attempts have been made to develop data-driven transforms by using sparse coding to achieve better performance than analytic transforms [4; 6; 7; 8]. In particular, orthogonal dictionary-based sparse coding not only provides more compact representations of input data than existing analytic transforms but also decorrelates data such as analytic transforms. In this section, we introduce recent work based on an SOT.  
In [4; 9; 18], the basic idea of an SOT is simple. Its design was based on an orthogonal sparse coding methodology. [PERSON] et al. formulated a transform with an orthonormal matrix and an \(L_{0}\) norm constraint on the transform coefficients:  
\[\begin{split}\min_{G,A}&\Big{\{}\|X-GA\|_{F}^{2}+ \lambda\|A\|_{0}\Big{\}}\\ s.t.& G^{T}G=GG^{T}=I_{n},\end{split} \tag{2}\]  
Here, \(A\) is the sparse transform coefficient, \(G\) is the SOT matrix, and \(I_{n}\) is an \(n\times n\) identity matrix. [PERSON] et al. used iterative optimization methods to find two variables: a dictionary and a coefficient matrix. Using Algorithm 1 solved this problem. As a hard-operator, \(\mathcal{T}(\cdot,\alpha)\) zerorizes when the absolute value is smaller than \(\alpha\). \(U\) and \(V\) are the left and right singular vector matrix, respectively. Then, the solution is also the local optimal point as in one of overcomplete sparse coding.  
[PERSON] et al. verified that SOT is a principled extension of Karhunen-Loeve Transform (KLT) because this transform is theoretically reduced to KLT in Gaussian processes. That the KLT is optimal in the Gaussian process is well known, and it shows that the optimal dictionary in Equation (2) has the same structure as KLT in the Gaussian process. In other words, the SOT is also optimal in the Gaussian process and is superior to KLT in non-Gaussian processes. [PERSON] et al. experimentally showed that the transform is superior to DCT and KLT in image compression.  
```
Given the dataset \(X=\{x_{1},x_{2},\ldots,x_{m}\}\in\mathbb{R}^{n\times N}\), Initialization: \[G=G_{0}\.\] whileStoppingCondition is not metdo  Update the coefficients: \[A=\mathcal{T}(G^{T}X,\lambda^{1/2}).\]  Find the optimal dictionary: (a) Compute the SVD: \[XA^{T}=U\Sigma V^{T}.\] (b) Update dictionary by the inner product: end
```  
**Algorithm 1**Orthogonal sparse coding.