## 6 Complexity Analysis of Image Classification with RRFs and SCNs
### SCNs  
As shown in Figure 3, we assume that an SCN consists of an input layer (IL), a convolutional layer (CL), a max pooling layer (ML), and a fully connected layer (FC), which coincides with the output layer (OL). The SCN uses ReLU as the activation function for all nodes. Let the input dimensions to the CL be \(R_{I}\times C_{I}\times L_{I}\) and suppose that the CL has \(N_{F}\) filters, each of which has dimensions \(R_{F}\times C_{F}\). The formula for the total number of parameters in the CL, \(P_{CL}\), is given in Equation (3) as the sum of the numbers of the shared weights in the filters and the number of biases, the latter being equal to the number of the filters. \[P_{CL}=R_{F}\cdot C_{F}\cdot L_{I}\cdot N_{F}+N_{F}=N_{F}(R_{F}\cdot C_{F} \cdot L_{I}+1) \tag{3}\]  
The ML does not add any additional parameters, because the feature maps obtained from the CL are downsampled, i.e., converted into the feature maps of lower dimensions with such functions as maximum, mean, etc. Figure 4: Number of DT parameters in classification of single image. Let the FC have \(N_{I}\) input nodes and suppose the number of nodes in the FC itself is \(N_{FC}\). The total number of parameters in the FC, \(P_{FC}\), is given in Equation (4) as the sum of the number of weights connected between the layers and and number of biases. \[P_{FC}=N_{I}N_{FC}+N_{FC} \tag{4}\]  
Let the input dimension to the convolutional layer be \(R_{I}\times C_{I}\times L_{I}\) and use \(N_{F}\) filters, where each filter's dimensions are \(R_{F}\times C_{F}\). A single convolution contains \(R_{F}\cdot C_{F}\cdot L_{I}\) multiplications while the filter is overlapped with the LRF, \(R_{F}\cdot C_{F}\cdot L_{I}-1\) additions to sum the multiplications, 1 bias addition, and 2 operations for ReLU activation. Thus, there are \(2\cdot R_{F}\cdot C_{F}\cdot L_{I}+2\) operations in a single convolution (See Figure 5). The total number of operations happening in the CL, \(O_{CL}\), for an output size of \(R_{o}\times C_{o}\) is shown in Equation (5). \[O_{CL}=(2\cdot R_{F}\cdot C_{F}\cdot L_{I}+2)\cdot R_{o}\cdot C_{o}\cdot N_{F} \tag{5}\]  
Let the input dimension to the ML be \(R_{I}\times C_{I}\times L_{I}\) and let the filter dimensions be \(R_{F}\times C_{F}\). In a single max-pooling operation, there are a maximum of \(2\cdot R_{F}\cdot C_{F}\) operations (See Figure 6). The total number of operations happening in the OL, \(O_{MP}\), for an output size of \(R_{o}\times C_{o}\) is given in Equation (6). \[O_{ML}=(2\cdot R_{F}\cdot C_{F})\cdot R_{o}\cdot C_{o}\cdot L_{I} \tag{6}\]  
Let the number of input nodes to the FL be \(N_{I}\) and the number of nodes in the fully connected layer be \(N_{FL}\). For a single node in the FL, there are \(N_{I}\) multiplication to  
Figure 5: Graphic representation of convolution. Figure 6: Graphic representation of max-pooling. multiply the inputs and the respective weights, \(N_{I}-1\) additions to compute the sum of the input and weight multiplications, 1 bias addition, a maximum of 2 operations for ReLU activation. Thus, there are \(2N_{I}+2\) operations for a single node in the FL. The total number of operations happening in in the FL, \(O_{FL}\), is given in Equation (7). \[O_{FL}=(2N_{I}+2)\cdot N_{FL} \tag{7}\]  
Let the number of nodes in the FL be \(N_{FC}\) and number of nodes in the output layer (number of classes) be \(N_{OL}\). The activation used in the output layer is softmax which calculates the probabilities based on the weighted output calculated before the activation. In addition to the operations happening for the multiplications and additions, there are \(N_{OL}\) operations to sum all weighted outputs, \(N_{OL}\) operations to normalize the weighted outputs and \(2N_{OL}\) operations to calculate the maximum activation to define the class of the input. The total number of operations in the OL, \(O_{OL}\), is given in Equation (8) and the total number of operations in the SCN, \(O_{SN}\), is given in Equation (9).