1
$\begingroup$

I am trying to determine the complexity of the neural network we use. The neural network is a U-net generator with an input shape of NxN (not an image but image-like data) and output of the same shape. There is 7x downsampling and 7x upsampling. Downsampling is a simple convolutional layer, where I have no problem to determine complexity as stated here:

$$ O\left(\sum_{l=1}^{d} n_{l-1} \cdot s_{l}^{2} \cdot n_{l} \cdot m_{l}^{2}\right) $$

I however cannot find what is big O complexity for the upsampling stage, where the UpSampling2D layer is used before convolution.

Any idea what is the time complexity of the upsampling convolutional layer, or where I might find information? Thanks in advance!

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I recently gave an answer where I explain the idea behind how you should calculate the time complexity of a convolution, although, right now, I don't give a general formula, but only the time complexity in a specific case. I think you can extend my reasoning to your use case, if nobody answers this question. I may answer your question later (if I have some time). $\endgroup$
    – nbro
    Commented Aug 10, 2020 at 15:00
  • $\begingroup$ @nbro by looking deeper into the problem, it seems my question is actually irrelevant, the UpSampling2d layer in keras according to it's documentation: Repeats the rows and columns of the data by size[0] and size[1] respectively. thus performs a linear function, which is followed by convolution $\endgroup$
    – Ruli
    Commented Aug 14, 2020 at 10:35

1 Answer 1

Reset to default
0
$\begingroup$

After further investigating the problem I have found the answer:

U-net generators' up-sampling stage consists of two steps:

  1. Use UpSampling2D layer
  2. Apply convolution on the output

The UpSampling2D layer is in the keras documentation described as:

Repeats the rows and columns of the data by size[0] and size[1] respectively.

From this information, we can calculate the time cost for UpSampling2D alone. Lets set size to (2,2), as is set in basic configuration of the U-net generator. The output of the UpSampling2D is then doubled. In case we started with (4,4,3), where the last index corresponds to number of channels, the output shape will be 8,8,3. We can see that each row and column need to be copied twice in each channel. From this we can define time complexity of a single up-sampling as:

$$ O\left(2 \cdot c \cdot n \cdot s\right) $$

Where c corresponds to number of channels, n corresponds to input length (one side of a matrix) and s is equal to filter size. Assuming that length and filter size have square shape, the complexity is multiplied by 2. Since in this case the the filter size is known, equal to (2,2), the notation can be simplified to:

$$ O\left(4 \cdot c \cdot n \right) = O\left(c \cdot n \right) $$

In my case, with only 1 channel, the complexity is simply

$$ O\left(n \right) $$

Which means the up-sampling stage is linear, and the only important feature is input size, which is negligible to the complexity of the following convolutional layer and can be ignored.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .