What are deconvolutional layers? I recently read Fully Convolutional Networks for Semantic Segmentation by Jonathan Long, Evan Shelhamer, Trevor Darrell. I don't understand what "deconvolutional layers" do / how they work.

The relevant part is


  3.3. Upsampling is backwards strided convolution
  
  Another way to connect coarse outputs to dense pixels
  is interpolation. For instance, simple bilinear interpolation
  computes each output $y_{ij}$ from the nearest four inputs by a
  linear map that depends only on the relative positions of the
  input and output cells.
  In a sense, upsampling with factor $f$ is convolution with
  a fractional input stride of 1/f. So long as $f$ is integral, a
  natural way to upsample is therefore backwards convolution
  (sometimes called deconvolution) with an output stride of
  $f$. Such an operation is trivial to implement, since it simply
  reverses the forward and backward passes of convolution.
  Thus upsampling is performed in-network for end-to-end
  learning by backpropagation from the pixelwise loss.
  Note that the deconvolution filter in such a layer need not
  be fixed (e.g., to bilinear upsampling), but can be learned.
  A stack of deconvolution layers and activation functions can
  even learn a nonlinear upsampling.
  In our experiments, we find that in-network upsampling
  is fast and effective for learning dense prediction. Our best
  segmentation architecture uses these layers to learn to upsample
  for refined prediction in Section 4.2.


I don't think I really understood how convolutional layers are trained. 

What I think I've understood is that convolutional layers with a kernel size $k$ learn filters of size $k \times k$. The output of a convolutional layer with kernel size $k$, stride $s \in \mathbb{N}$ and $n$ filters is of dimension $\frac{\text{Input dim}}{s^2} \cdot n$. However, I don't know how the learning of convolutional layers works. (I understand how simple MLPs learn with gradient descent, if that helps).

So if my understanding of convolutional layers is correct, I have no clue how this can be reversed.

Could anybody please help me to understand deconvolutional layers?
Deconvolution layer is a very unfortunate name and should rather be called a transposed convolutional layer.

Visually, for a transposed convolution with stride one and no padding, we just pad the original input (blue entries) with zeroes (white entries) (Figure 1).



In case of stride two and padding, the transposed convolution would look like this (Figure 2): 



All credits for the great visualisations go to


Vincent Dumoulin, Francesco Visin - A guide to convolution arithmetic for deep learning


You can find more visualisations of convolutional arithmetics here.