Answers.Body: <p>After further investigating the problem I have found the answer:</p>
  <p>U-net generators' up-sampling stage consists of two steps:</p>
  <ol>
  <li>Use <code>UpSampling2D</code> layer</li>
  <li>Apply convolution on the output</li>
  </ol>
  <p>The <code>UpSampling2D</code> layer is in the keras documentation described as:</p>
  <p><code>Repeats the rows and columns of the data by size[0] and size[1] respectively.</code></p>
  <p>From this information, we can calculate the time cost for <code>UpSampling2D</code> alone. Lets set size to <code>(2,2)</code>, as is set in basic configuration of the U-net generator. The output of the <code>UpSampling2D</code> is then doubled. In case we started with <code>(4,4,3)</code>, where the last index corresponds to number of channels, the output shape will be <code>8,8,3</code>. 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:</p>
  <p><span class="math-container">$$
  O\left(2 \cdot c \cdot n \cdot s\right)
  $$</span></p>
  <p>Where <em>c</em> corresponds to number of channels, <em>n</em> corresponds to input length (one side of a matrix) and <em>s</em> 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 <code>(2,2)</code>, the notation can be simplified to:</p>
  <p><span class="math-container">$$
  O\left(4 \cdot c \cdot n \right) = O\left(c \cdot n \right)
  $$</span></p>
  <p>In my case, with only 1 channel, the complexity is simply</p>
  <p><span class="math-container">$$
  O\left(n \right)
  $$</span></p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-17T07:51:00.977Z
Answers.LastActivityDate: 2020-08-17T07:51:00.977Z
Answers.UserDisplayName: Ruli
Body: <p>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 <a href="https://arxiv.org/pdf/1412.1710.pdf" rel="nofollow noreferrer">stated here</a>:</p>
  <p><span class="math-container">$$
  O\left(\sum_{l=1}^{d} n_{l-1} \cdot s_{l}^{2} \cdot n_{l} \cdot m_{l}^{2}\right)
  $$</span></p>
  <p>I however cannot find what is big O complexity for the upsampling stage, where the UpSampling2D layer is used before convolution.</p>
  <p>Any idea what is the time complexity of the upsampling convolutional layer, or where I might find information? Thanks in advance!</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-08-10T15:00:05.067Z
Comments.Text: I recently gave [an answer](https://ai.stackexchange.com/a/22929/2444) 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).
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-08-14T10:35:38.247Z
Comments.Text: @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
Comments.UserDisplayName: Ruli
Tags: <convolutional-neural-networks><time-complexity><u-net><computational-complexity><pooling>
Title: What is the time complexity of the upsampling stage of the U-net?
UserDisplayName: Ruli
ThreadText: # What is the time complexity of the upsampling stage of the U-net?
  
  (Asked by: username_0 on 2020-08-10)
  
  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](https://arxiv.org/pdf/1412.1710.pdf):
  
  $$
  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!
  
  **Tags:** convolutional-neural-networks, time-complexity, u-net, computational-complexity, pooling
  > **Comments:**
  > **username_1**: I recently gave [an answer](https://ai.stackexchange.com/a/22929/2444) 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).  
  > **username_0**: @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  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2020-08-17. Score: 0 | Accepted answer
  
  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.
  
  
  ---
  
  