# Adaptive-Size Dictionary Learning Using Information Theoretic Criteria
## 3 Algorithm  
We assume first that the sparsity level is known. Our strategy is implemented by Algorithm 1, named ITC-ADL. Starting with an initial dictionary of size \(n_{\text{init}}\), we run the DL algorithm. We change the size only every \(c\) iterations, to allow the current set of atoms to be sufficiently trained together. Thus, the selection based on ITC described in Section 2.2 can be meaningful. Although we could compute ITC values for all dictionary sizes between \(n_{\text{min}}\) and the current \(n\), it is more efficient to consider only a smaller number of candidates \(n_{\text{cand}}\); note that the representations have to be recomputed for each sub-dictionary; although this can be done economically (see below the discussion on complexity), it may become a significant burden. Let us denote \(n_{\text{ITC}}\) the size with minimum ITC value among the \(n_{\text{cand}}\) largest possible dictionaries (those with sizes \(n\), \(n-1\),..., \(n-n_{\text{cand}}+1\)). The main question is now how to use this value. If \(n_{\text{ITC}}<n\), we might be tempted to continue the learning process with only \(n_{\text{ITC}}\) atoms. However, this seems to be (assertion confirmed by numerical experiments) a too drastic decision, that can easily lead to premature shrinking of the dictionary. Instead, we take \(n_{\text{ITC}}\) as an indicator of the direction where \(n\) must evolve. If \(n_{\text{ITC}}\) is much smaller than the current \(n\), we decrease the size by \(\delta_{-}\) (this number is 5 in our experiments); if \(n_{\text{ITC}}\) is only slightly smaller, than we decrease the size by one; finally, we interpret \(n_{\text{ITC}}=n\) as a sign that the size needs to be increased and add \(\delta_{+}\) atoms to the dictionary (we take \(\delta_{+}=5\)). There are several methods for generating new atoms [3] (Section 3.9); we choose the simplest: random atoms. The whole algorithm is run, as typical in DL, for a preset number \(K\) of iterations. Only at the end of these iterations we take \(n_{\text{ITC}}\) as a true size information. With this size, we run \(c\) more DL iterations, as a final refinement. ```
Data: training signals \(\mathbf{Y}\in\mathbb{R}^{m\times N}\) sparsity level \(s\) initial dictionary size \(n_{\text{init}}\) number of iterations between size changes \(c\) number of candidate sizes \(n_{\text{cand}}\) dictionary size change steps \(\delta_{+}\), \(\delta_{-}\) maximum number of iterations \(K\) Result: learned dictionary \(\mathbf{D}\), adapted size \(n\)
1 Initialization: \(n\gets n_{\text{init}}\), set \(\mathbf{D}\in\mathbb{R}^{m\times n}\) randomly
2 for\(k=1:K\)do
3 Sparse coding: compute \(\mathbf{X}\) using OMP (with sparsity level \(s\)) Dictionary update: update \(\mathbf{D}\) and \(\mathbf{X}\) with AK-SVD iteration if\(k\) mod \(c=0\)then
4 Sort atoms of \(\mathbf{D}\) in decreasing order of power (Equation (6)) Compute ITC values for dictionaries \(\mathbf{D}(:,1:\
u)\), with \(\
u=n-n_{\text{cand}}+1:n\) Let \(n_{\text{ITC}}\) be the size for which ITC is minimum if\(n_{\text{ITC}}=n\)then
5 Increase size: append \(\delta_{+}\) new atoms to \(\mathbf{D}\) and set \(n\gets n+\delta_{+}\)
6 else
7 if\(n_{\text{ITC}}<n-\delta_{-}\)then
8 Decrease size: \(n\gets n-\delta_{-}\)
9 else
10 Slightly decrease size: \(n\gets n-1\)
11 Trim dictionary: \(\mathbf{D}\leftarrow\mathbf{D}(:,1:n)\)
12
13 Set \(n\gets n_{\text{ITC}}\), trim dictionary and run \(c\) more iterations
```  
**Algorithm 1**ITC-ADL: DL with ITC-adapted dictionary size. It is relatively hard to estimate the complexity of ITC-ADL, due to the dictionary size variations. We describe only the extra operations with respect to a standard DL algorithm, disregarding the size. There are two main categories of operations that increase the complexity. The first is the total number of iterations, that has to be larger than for standard DL, in order to let the dictionary size converge. The ITC give reliable information if the dictionary is well trained, hence neither \(K\) nor \(c\) can be small.