LCNN is a novel layer that can replace any convolutional layer. The main thing is that a filter is “decomposed” as a linear combination of parts from a dictionary. The ability to tune the dictionary size and the number of elements in the linear combination allows an efficiency/accuracy trade-off (see Figure 3). In addition, the authors argue that LCNN has an advantage in few-shot learning and few-iteration learning settings.

Filter Construction

Let’s first define the 4 tensors that we’ll need:

• \(\bold{W} \in \mathbb{R}^{m \times k_w \times k_h}\) is a filter, where \((k_w, k_h)\) are its spatial dimensions and \(m\) is the number of channels in the input image.
• \(\bold{D} \in \mathbb{R}^{k \times m}\) is the dictionary. It contains \(k\) vectors of size \(m\). Those vectors will be combined to construct the filter (See Figure 1).
• \(\bold{I} \in \mathbb{N}^{s \times k_w \times k_h}\) is the lookup indices tensor, where \(s\) is the number of elements in the linear combination.
• \(\bold{C} \in \mathbb{R}^{s \times k_w \times k_h}\) is the coefficient tensor.

Then, we can formulate the construction as follows:

\[\bold{W}_{[:,r,c]} = \sum_{t=1}^s \bold{C}_{[t,r,c]} \cdot \bold{D}_{[\bold{I}_{[t,r,c]},:]}\]

Fast Convolution using a Shared Dictionary

Now, let’s imagine that our dictionary is in fact the weights of a 1x1 convolution layer: we thus have \(k\) filters of dimensions \((m, 1, 1)\). By passing our input image \(\bold{X} \in \mathbb{R}^{m \times w \times h}\) through this 1x1 convolutional layer, we get \(\bold{S} \in \mathbb{R}^{k \times w \times h}\). With \(\bold{I}\) and \(\bold{C}\) in hand, we can compute the result of the convolution \(\bold{X} * \bold{W}\) for each filter, without really constructing any \(\bold{W}\). (See section 3.1.1 of paper.) By reducing \(k\) and \(s\), we can reduce the number of lookups and floating point operations.

One problem arises from using indices to select values in tensors: it makes the network non-differentiable. During training, a trick is used to be able to backpropagate. For each filter \(\bold{W}\), a sparse tensor \(\bold{P} \in \mathbb{R}^{k \times k_w \times k_h}\) is constructed. In this tensor, elements at indices \(\bold{I}\) have values \(\bold{C}\). Then, we have that \(\bold{X} * \bold{W} = \bold{S} * \bold{P}\) for each \(\bold{W}, \bold{P}\) pair.

During training, we learn \(\bold{D}\) and \(\bold{P}\). To obtain a tensor \(\bold{P}\) that is \(s\)-sparse, we impose a \(\ell_1\) norm and keep only \(s\) non-zero elements. From \(\bold{P}\), we can easily obtain \(\bold{I}\) and \(\bold{C}\).

Few-shot learning

The authors argue that this layer architecture has a performance advantage in few-shot learning settings, as we can see in the following plot (extracted from Figure 4).

Few-iteration learning

The authors also argue that LCNN can learn more in the first iterations of training than an ordinary CNN. In one experiment, they transferred the dictionary learned with a shallow network to a deeper network and only trained \(\bold{I}\) and \(\bold{C}\). See Figure 5 for the learning curves.