# Adaptive-Size Dictionary Learning Using Information Theoretic Criteria
## 1 Introduction  
Dictionary learning (DL) is now a mature field [1; 2; 3], with several efficient algorithms for solving the basic problem or its variants and with numerous applications in image processing (denoising and inpainting), classification, compressed sensing and others. The basic DL problem is: given \(N\) training signals gathered as the columns of the matrix \(\mathbf{Y}\in\mathbb{R}^{m\times N}\) and the sparsity level \(s\), find the dictionary \(\mathbf{D}\in\mathbb{R}^{m\times n}\) by solving  
\[ \begin{split}\min_{\mathbf{D},\mathbf{X}}&\|\mathbf{Y}-\mathbf{D} \mathbf{X}\|_{F}^{2}\\ \text{s.t.}&\|\mathbf{x}_{\ell}\|_{0}\leq s,\ \ell=1:N\\ &\|\mathbf{d}_{j}\|_{2}=1,\ j=1:n\end{split}  \tag{1}\]  
Here, \(\|\cdot\|_{F}\) is the Frobenius norm; and \(\mathbf{x}_{\ell}\) and \(\mathbf{d}_{j}\) are columns of \(\mathbf{X}\) and \(\mathbf{D}\), respectively. The first constraint says that the matrix \(\mathbf{X}\) has at most \(s\) nonzeros on each column. The second constraint is the normalization of the atoms (columns of the dictionary). An alternative view is to relate Equation (1) to the sparse matrix factorization--or dictionary recovery (DR)--problem. The different assumption is that there indeed exist a dictionary \(\mathbf{D}\) and a sparse matrix \(\mathbf{X}\) such that \(\mathbf{Y}\approx\mathbf{D}\mathbf{X}\); the purpose is to recover them from the data \(\mathbf{Y}\). Such a ground truth is usually not available in practical applications. However, investigating DR is useful for theoretical and practical developments. Significant recent work on this matter can be found in [4; 5; 6; 7]. Our contribution belongs more to the DR line of thought. In most DR algorithms, the dictionary size \(n\) (the number of atoms) is assumed to be known. In DL applications, \(n\) is chosen with a rather informal trial-and-error procedure: a few sizes are used and that giving the best performance in the application at hand is selected. A dictionary with more atoms typically gives a smaller error: if \(\mathbf{D}_{1}\in\mathbb{R}^{m\times n_{1}}\) and \(\mathbf{D}_{2}\in\mathbb{R}^{m\times n_{2}}\), with \(n_{1}<n_{2}\), we expect that \(\|\mathbf{Y}-\mathbf{D}_{1}\mathbf{X}_{1}\|_{F}^{2}>\|\mathbf{Y}-\mathbf{D}_{2}\mathbf{X}_{2}\|_{F}^{2}\). However, this does not mean that \(\mathbf{D}_{2}\) is necessarily better. We aimhere at an automatic choice of the size that is the most appropriate to the data, based on Information Theoretic Criteria (ITC). The only previous work based on ITC [8] uses Minimum Description Length for the choice of the size and the sparsity level. Their algorithm implements a virtual coder and searches exhaustively over all considered dictionary sizes. A recent method [9] reporting promising results has a similar purpose, but is based on geometric properties of the DR problem. All other methods are based on heuristics that essentially aim to obtain a dictionary having the same representation error as that obtained with a standard method, but with smaller size. We list a few of the successful approaches. In [10; 11], a small dictionary is grown by adding representative atoms from time to time in the iterative DL process. Clustering ideas are used in [12; 13; 14] to reduce the size of a large dictionary. A direct attempt of optimizing the size is employed in [15] by introducing in the objective a proxy for the size as penalization. An Indian Buffet Process is the tool in [16]. Other techniques based on Bayesian learning are [17; 18]. Unlike the method in [8] but similarly to that in [9], our approach tries to adapt the size during the DL process. It also has a much simpler implementation, using standard ITC that do not intervene in the learning itself, but only in the selection of the atoms. Hence, the complexity is not much higher than that of the underlying DL algorithm. Section 2 presents the ITC, specialized to the DL problem, and describes the pool of candidate dictionaries during the DL algorithm. Section 3 gives the details of our algorithm for adapting the dictionary size.