Low-Rank Winograd Transformation for 3D Convolutional Neural Networks
This paper focuses on Winograd transformation in 3D convolutional neural
networks (CNNs) that are more over-parameterized compared with the 2D version.
The over-increasing Winograd parameters not only exacerbate training complexity
but also barricade the practical speedups due simply to the volume of
element-wise products in the Winograd domain. We attempt to reduce trainable
parameters by introducing a low-rank Winograd transformation, a novel training
paradigm that decouples the original large tensor into two less
storage-required trainable tensors, leading to a significant complexity
reduction. Built upon our low-rank Winograd transformation, we take one step
ahead by proposing a low-rank oriented sparse granularity that measures
column-wise parameter importance. By simply involving the non-zero columns in
the element-wise product, our sparse granularity is empowered with the ability
to produce a very regular sparse pattern to acquire effectual Winograd
speedups. To better understand the efficacy of our method, we perform extensive
experiments on 3D CNNs. Results manifest that our low-rank Winograd
transformation well outperforms the vanilla Winograd transformation. We also
show that our proposed low-rank oriented sparse granularity permits practical
Winograd acceleration compared with the vanilla counterpart.
Ziran Qin, Mingbao Lin, Weiyao Lin
# Low-Rank Winograd Transformation for 3D Convolutional Neural Networks

###### Abstract

This paper focuses on Winograd transformation in 3D convolutional neural networks (CNNs) that are more over-parameterized compared with the 2D version. The over-increasing Winograd parameters not only exacerbate training complexity but also barricade the practical speedups due simply to the volume of element-wise products in the Winograd domain. We attempt to reduce trainable parameters by introducing a low-rank Winograd transformation, a novel training paradigm that decouples the original large tensor into two less storage-required trainable tensors, leading to a significant complexity reduction. Built upon our low-rank Winograd transformation, we take one step ahead by proposing a low-rank oriented sparse granularity that measures column-wise parameter importance. By simply involving the non-zero columns in the element-wise product, our sparse granularity is empowered with the ability to produce a very regular sparse pattern to acquire effectual Winograd speedups. To better understand the efficacy of our method, we perform extensive experiments on 3D CNNs. Results manifest that our low-rank Winograd transformation well outperforms the vanilla Winograd transformation. We also show that our proposed low-rank oriented sparse granularity permits practical Winograd acceleration compared with the vanilla counterpart.

## 1 Introduction

3D convolutional neural networks (CNNs) have achieved substantial accuracy increases in many video processing tasks, as a result of their superior capacity of extracting spatio-temporal features. Unfortunately, they come with large amounts of computing resources, primarily because the 3D kernels are more computationally intensive. Many restrictions such as runtime, memory, and power budget prevent 3D CNNs from running on many real-world devices.

Fast convolution algorithms such as Winograd convolution [18] and fast Fourier transform (FFT) [33] can greatly reduce the convolutional cost. Their principle is to replace spatial convolution operations with element-wise product and discard redundant multiplications in convolution. Conventional FFT based convolution is fast for large filters, therefore most recent attention focuses on Winograd convolution principally for the small 3\(\times\)3 filters adopted by state-of-the-art CNNs. Another potential solution is network pruning that reduces network complexity by removing unnecessary units [6; 32]. It seems that Winograd convolution and network pruning can be well combined to further save computation costs. However, they are not naturally compatible since the sparsity property from network pruning is diminished after the kernel transformation of the Winograd algorithm. To tackle this incompatibility, [24] performed pruning operations upon Winograd domain while [28] added the ReLU function after the Winograd transformation to increase the sparsity of element-wise product. However, both studies do not consider that Winograd kernel is location-sensitive as later demonstrated by [24] where an importance factor matrix is utilized to gauge the significance of different kernel locations.

Current investigations mostly give attention to the Winograd transformation in 2D CNNs. A direct extension of these methods to 3D CNNs is inapplicable, as we analyze, for two issues. First, 3D Winograd transformation causes considerable parameter increase. Taking F(2, 3)-based Winograd algorithm as an example, a typical 3D convolutional kernel with a shape of \(3\times 3\times 3\) is often replaced by a \(4\times 4\times 4\) Winograd kernel, leading to 2.37\(\times\) more parameters which it is only 1.78\(\times\) for 2D case. More parameters from Winograd transformation do not always benefit model capacity but cause model redundancy as analyzed in Sec. 3.2 and verified in Sec. 4.2. Also, the over-increasing trainable parameters pose a serious challenge to the capability of training machine. Second, existing methods fail to accelerate Winograd transformation even though conducting pruning upon the Winograd domain. Similar to the weight pruning [20; 8; 6], prior implementations derive irregular sparse weight matrix, which receives very limited speed gains since the irregular sparsity barely takes advantage of vector processing architectures such as single instruction multiple data (SIMD), and poorly utilizes memory buses [27]. Therefore, it remains unsolved to excavate Winograd transformation for acceleration, in particular to 3D CNNs primarily for the ever-increasing element-wise product in the Winograd domain.
In this paper, we put forward a novel Winograd transformation for 3D CNNs towards solving the above issues. Considering the over-increasing parameters in 3D CNNs, as shown in Fig. 1, compared with the vanilla version, we introduce a low-rank Winograd transformation method that represents the updating matrix (variation from a pre-trained Winograd weight tensor to the final fine-tuned one) with two smaller matrices. In this fashion, we concentrate on updating weights in the main directions of the whole Winograd space during the sparse training, leading to superior performance over the vanilla Winograd transformation. Besides, the two less storage-required matrices lead to a significant reduction in trainable Winograd parameters. With regard to Winograd transformation acceleration, we further present a low-rank oriented sparse granularity that quantifies the importance of each tensor column. The rationale behind this is to derive a more regular sparse pattern by simply involving the non-zero columns in the element-wise product of the Winograd domain. Thus, we introduce a scoring sequence to continuously accumulate the magnitude and gradient of column location in each training iteration as the importance assessment, and finally remove all weights in compliance with the low-scored columns. Practical speedups are observed from our low-rank oriented sparse granularity (see Table 3).

## 2 Related Work

### Spatial-Domain Pruning

Spatial-domain pruning is the practice of removing parameters from an existing network. It may entail removing individual parameters, _a.k.a._ weight pruning, or parameters in groups such as filter pruning and block pruning. For weight pruning, individual weights are measured by a certain criterion such as weight magnitude [8; 7; 6], higher-order information [20; 10; 5; 21] and so on. These methods are demonstrated to well preserve model performance. However, the resulting irregular sparse matrix requires specialized hardware/libraries to achieve practical speedups. For filter pruning, the entire filters are removed by standards such as \(\ell_{1}\)/\(\ell_{2}\)-norm [23; 30; 11], activation sparsity [14], lasso regression-based channel selection [12], and rank of feature maps [26]. In contrast to weight pruning, filter pruning advantages in acceleration but causes more performance drops. Therefore, block pruning, where a block of weights is removed simultaneously, has received recent research focus [37; 27] for its better performance than filter pruning as well as hardware-friendly deployment than weight pruning. However, vanilla spatial pruning methods cannot be directly combined with the Winograd convolution because the Winograd transformation diminishes the sparsity resulting from pruning [45].

### Winograd-Domain Pruning

Though vanilla spatial pruning fails to cooperate with the Winograd convolution, its main pruning principles have been extended to remove parameters in the Winograd domain. [29] removed Winograd-domain kernels, meanwhile, they retained kernels from the original network. However, dimension inconsistency arises since the Winograd-domain kernels are of a higher dimension than the spatial-domain kernels. [24] introduced Winograd layers in exchange for the standard convolutional layers. The pruning and training are simultaneously conducted in the Winograd layers. Thus, the dimension inconsistency issue is eliminated and the sparsity in Winograd domain also increases. [28] introduced the ReLU operation to the Winograd domain to derive sparse transformed activations. It improves the possibility of sparse element-wise products in the Winograd domain. [45] specified that different locations of the Winograd layers contribute differently to the output activations. Despite the progress, these studies lead to hardware-unfriendly irregular sparse patterns, causing imbalanced workloads among the data flows. To leverage the multiplication reduction from sparsity, [31; 44] devised sparse patterns that benefit more from speedups on specialized hardware.

## 3 Methodology

### 3D Winograd

Giving a 3D convolution kernel \(\mathcal{G}\in\mathbb{R}^{C_{o}\times C_{i}\times r_{d}\times r_{h}\times r_{w}}\) where \(C_{o}\) and \(C_{i}\) denote the number of output and input channel, and \((r_{d},r_{h},r_{w})\) forms the kernel size, it is convoluted with a four-dimensional input data \(\mathcal{I}\in\mathbb{R}^{C_{i}\times D_{i}\times H_{i}\times W_{i}}\) where \(D_{i}\), \(H_{i}\) and \(W_{i}\) respectively denote the depth, height, and width of the input \(\mathcal{I}\). Typical 3D convolution operation

Figure 1: Comparison between (a) the vanilla Winograd transformation and (b) our low-rank Winograd transformation. We decouple the whole Winograd weights into two smaller matrices, leading to a significant reduction in trainable parameters.
with unit stride and unit dilation can be formulated as:

\[\mathcal{O}(n,:,:,:)=\sum_{c=0}^{C_{i}-1}\mathcal{G}(n,c,:,:,:)*\mathcal{I}(c,:,:,:), \tag{1}\]

where \(\mathcal{O}\in\mathbb{R}^{C_{o}\times D_{o}\times H_{o}\times W_{o}}\) is the output feature map, \(D_{o}\), \(H_{o}\) and \(W_{o}\) denote the depth, height and width of \(\mathcal{O}\), respectively, and \(*\) stands for 3D convolution.

The above 3D operation can be split into multiple basic convolutions, each of which can be optimized to obtain lower arithmetic complexity by using the Winograd convolution [42]. Specifically, the Winograd convolution disassembles the input data \(\mathcal{I}\) into several overlapping tiles \(\{\mathcal{I}_{1},\mathcal{I}_{2},...\}\), in which each tile is a sub-matrix of \(\mathcal{I}_{k}\in\mathcal{I}\) and has a shape of \(C_{i}\times t_{d}\times t_{h}\times t_{w}\). Similar to Eq. (1), each tile \(\mathcal{I}_{t}\) can be convoluted separately with \(\mathcal{G}\), resulting in a basic output tile \(\mathcal{O}_{t}\) that is a sub-matrix of \(\mathcal{O}\) and has a shape of \(C_{o}\times m_{d}\times m_{h}\times m_{w}\) where \(m_{d}=t_{d}-r_{d}+1\), \(m_{h}=t_{h}-r_{h}+1\) and \(m_{w}=t_{w}-r_{w}+1\). Note that, any \(\mathcal{O}_{k}\) and \(\mathcal{O}_{s}\) are non-overlapping and the spatial convolution result \(\mathcal{O}\) can be obtained by reassembling \(\{\mathcal{O}_{1},\mathcal{O}_{2},...\}\) in order. Eq. (1) can be further formulated as:

\[\tilde{\mathcal{I}}\in\mathbb{R}^{T\times C_{i}\times t_{d}\times t _{h}\times t_{w}}\rightarrow\tilde{\mathcal{O}}\in\mathbb{R}^{T\times C_{o} \times m_{d}\times m_{h}\times m_{w}}\] \[\text{via}\quad\tilde{\mathcal{O}}(k,n,:,:,:)=\sum_{c=1}^{C_{i} }\mathcal{G}(n,c,:,:,:)*\tilde{\mathcal{I}}(k,c,:,:,:), \tag{2}\]

where \(\tilde{\mathcal{O}},\tilde{\mathcal{I}}\) denote the disassembled output feature and input data, \(\tilde{\mathcal{O}}(k,:,:,:,:)\), \(\tilde{\mathcal{I}}(k,:,:,:,:)\) denote basic output tile \(\mathcal{O}_{k}\), basic input tile \(\mathcal{I}_{k}\), respectively, and \(T=D_{i}H_{i}W_{i}/(t_{d}t_{h}t_{w})\) is the number of disassembled tiles. A thorough comprehension can be referred to [18]. Notice in what follows, we introduce \(r=r_{d}=r_{h}=r_{w}\) and \(t=t_{d}=t_{h}=t_{w}\) for brevity since current networks often have a uniform kernel size such as \(3\times 3\times 3\) across different dimensions, and also the basic output tile is characterized with \(m=m_{d}=m_{h}=m_{w}\). Since the spatial convolution is computationally intensive, Eq. (2) can be further optimized with the Winograd transformation [18]:

\[\tilde{\mathcal{O}}(k,n,:,:,:)=\mathscr{T}_{O}\Big{(}\sum_{c=0}^{C_{i}-1} \mathscr{T}_{K}\big{(}\mathcal{G}(n,c,:,:,:)\big{)}\odot\mathscr{T}_{I}( \tilde{\mathcal{I}}(k,c,:,:,:)\Big{)}, \tag{3}\]

where \(\odot\) stands for the element-wise product.

In Eq. (A), the kernel \(\mathcal{G}(n,c,:,:,:)\) and input tiles \(\tilde{\mathcal{I}}(k,c,:,:,:)\) are individually converted into the Winograd domain of the same shape by the Winograd kernel transformation \(\mathscr{T}_{K}(x)=(KxK^{T})^{R}K^{T}\) and input transformation \(\mathscr{T}_{I}(x)=(B^{T}xB)^{R}B\). Finally, the Winograd-domain kernel and input tile are multiplied in an element-wise manner, the results of which are transformed back to the vanilla spatial domain by the Winograd inverse transformation \(\mathscr{T}_{O}(x)=\big{(}(A^{T}xA)^{R}A\big{)}^{R}\). Herein, \(K\), \(B\) and \(A\) are three transformation matrices determined by \(F(m\times m\times m,r\times r\times r)\). Their specific formats can turn to [18]. \((\cdot)^{R}\) denotes clock-wise dimension rotation. Considering a 3-D Tensor \(T(z,y,x)\), a toy example for \((\cdot)^{R}\) is illustrated as: \(T(z,y,x)^{R}=T(y,x,z)\).

For better illustration, we first rearrange the spatial kernel \(\mathcal{G}\in\mathbb{R}^{C_{o}\times C_{i}\times r\times r\times r}\), the input tiles \(\tilde{\mathcal{I}}\in\mathbb{R}^{T\times C_{i}\times t\times t\times t}\), and the output tiles \(\tilde{\mathcal{O}}\in\mathbb{R}^{T\times C_{o}\times m\times m\times m}\) into 2D matrices \(G\in\mathbb{R}^{C_{o}C_{i}\times r^{3}}\), \(\tilde{I}\in\mathbb{R}^{TC_{i}\times t^{3}}\), and \(\tilde{O}\in\mathbb{R}^{TC_{o}\times m^{3}}\) accordingly. After rearrangement, Eq. (A) is modified as a new form:

\[\tilde{O}(kn,:)=\Big{(}\sum_{c=0}^{C_{i}-1}G(C_{i}n+c,:)T_{K}\odot\tilde{I}(kC_ {i}+c,:)T_{I})\Big{)}T_{O}, \tag{4}\]

where \(T_{K}\in\mathbb{R}^{r^{3}\times t^{3}}\), \(T_{I}\in\mathbb{R}^{t^{3}\times t^{3}}\), \(T_{O}\in\mathbb{R}^{t^{3}\times m^{3}}\) are transformation matrices and the operations with transformation matrices \(T_{K}\), \(T_{I}\), \(T_{O}\) correspond to the process of Winograd input transformation \(\mathscr{T}_{i}(\cdot)\), Winograd kernel transformation \(\mathscr{T}_{k}(\cdot)\) and Winograd output transformation \(\mathscr{T}_{\mathcal{G}}(\cdot)\) in Eq. (A), respectively1. To simplify the description, we denote the Winograd input transformed result \(\tilde{I}T_{I}\) as \(V\) and use \(\tilde{\odot}\) to represent the consecutive operations of element-wise product and summation over the output channel in Eq. (4) for ease of the following representation. Eq. (4) can be simplified as:

Footnote 1: A comprehensive derivation of Eq. (4) as well as the formats of transformation matrices \(T_{K}\), \(T_{I}\) and \(T_{O}\) can be referred to the appendix.

\[\tilde{O}=\big{(}GT_{K}\tilde{\odot}V\big{)}T_{O}. \tag{5}\]

Particularly, [24] introduced a 2D Winograd layer parameterized by a weight tensor \(\mathcal{G}_{W}\in\mathbb{R}^{C_{o}\times C_{i}\times t\times t}\) to replace the Winograd kernel transformation. The element-wise operation costs are expected to decrease from deriving a sparse \(\mathcal{G}_{W}\). In this paper, we extend the Winograd layer to 3D and introduce the Winograd-domain weight \(\mathcal{G}_{W}\in\mathbb{R}^{C_{o}\times C_{i}\times t\times t\times t}\) to directly perform element-wise products with the Winograd-domain input tiles. We also rearrange \(\mathcal{G}_{W}\) to a 2D Winograd-domain weight matrix \(G_{W}\in\mathbb{R}^{C_{o}C_{i}\times t^{3}}\), therefore Eq. (5) becomes as follows:

\[\tilde{O}=\big{(}G_{W}\tilde{\odot}V\big{)}T_{O}. \tag{6}\]

The weight matrix \(G_{W}\) is directly inherited from the pre-trained spatial-domain weight matrix transformed into the Winograd domain, _i.e._, \(G_{W}=GT_{K}\). After getting \(G_{W}\), the problem of pruning the 3D Winograd layer is converted into sparsifying the weight matrix \(G_{W}\).

Different from the 1D or 2D Winograd layer, 3D Winograd layer introduces more parameters, which raises a formidable challenge in not only the increasing parameters of sparse training but also accelerating the element-wise product. These two issues are respectively solved in this paper by introducing a low-rank Winograd transformation in Sec. 3.2 and a low-rank oriented sparse granularity in Sec. 3.3, which are also two core contributions of this paper. In what follows, we refer to the model with Winograd layers as Winograd model and the one with convolutional layers as spatial model.

### Low-rank Winograd Transformation

The sparse training of the Winograd model shares a two-step pipeline similar to the spatial model, including pruning weights that are unimportant and retraining the model for recovering accuracy. However, it is challenging to train the
3D Winograd model due to the increasing trainable parameters and expensive element-wise products. When looking back on the Winograd weight \(G_{W}\), we observe that the over-increasing parameters do not always benefit the performance gains. Then, we analyze the over-increasing parameters by performing singular value decomposition (SVD) on the rearranged Winograd-domain weight matrix \(G_{W}\in\mathbb{R}^{C_{o}C_{i}\times t^{3}}\). In this fashion, \(G_{W}\) can be represented by the \(t^{3}\)-dimensional subspace as: \(G_{W}=\sum_{i=0}^{s^{3}-1}\sigma_{i}\vec{u_{i}}\vec{v_{i}}^{T}\), where \(\sigma_{i}\) and \(\vec{u_{i}}\vec{v_{i}}\) indicate the \(i\)-th largest singular value and the corresponding left/right singular vector. Fig. 2 visualizes the singular values where two phenomena can be observed. First, among all the \(t^{3}\) singular values, larger-magnitude ones are concentrated in the top-\(r^{3}\) (\(r^{3}=27\) in Fig. 2), which is exactly the number of weight elements in the spatial domain. Second, among the top-\(r^{3}\) singular values, those in the front part are much larger than those in the back part. Such phenomena suggest the existence of over-parameterized weights in the Winograd domain, which means that it may not be necessary to train the Winograd model within the full Winograd domain. A more efficient training way is urgent for 3D Winograd models.

Given the pre-trained Winograd-domain weight \(G_{W}\), we denote the fine-tuned weight as \(G_{W}+\Delta G_{W}\), where \(\triangle G_{W}\in\mathbb{R}^{C_{o}C_{i}\times t^{3}}\) denotes the updates from the \(G_{W}\) to the eventual fine-tuned \(\tilde{G}_{W}\). [13] and [25] showed that the update \(\Delta G_{W}\) is supposed to have a low "intrinsic rank" if the pre-trained weight \(G_{W}\) is over-parameterized. This indicates that fine-tuning in the Winograd domain raises attention to the main directions of the whole Winograd space. In light of this, we freeze the pre-trained dense Winograd weight \(G_{W}\) first and then achieve low-rank update \(\Delta G_{W}\) by a low-rank decomposition \(\Delta G_{W}=G_{r}G_{c}\) where \(G_{r}\in\mathbb{R}^{C_{o}C_{i}\times s}\) and \(G_{c}\in\mathbb{R}^{s\times t^{3}}\) (\(s\ll t^{3}\)). Therefore, our low-rank Winograd transformation can be finally described as:

\[\tilde{O}=\big{(}(G_{W}+G_{r}G_{c})\tilde{\odot}V\big{)}T_{O}. \tag{7}\]

During sparse training, we freeze \(G_{W}\), and upgrade \(G_{r}\) and \(G_{c}\) only. In this fashion, the amount of trainable parameters are reduced from \(C_{o}C_{i}t^{3}\) to \(C_{o}C_{i}s+st^{3}\) in the Winograd domain. In order to train \(G_{r}\) and \(G_{c}\) more effectively, we initialize \(G_{r}\) by: \(G_{r}(\cdot,i)=\alpha\sigma_{i}\vec{u_{i}}\) and \(G_{c}\) by: \(G_{c}(i,:)=\vec{v_{i}}^{T}\), where \(\alpha\) is a scalar hyper-parameter that controls the amplitude of the update and is set to 0.1 in this paper.

### Low-Rank Oriented Sparse Granularity

In addition to trainable parameter reduction, we further attempt to decrease the computation cost from the element-wise product at inference time. By virtue of our low-rank Winograd transformation in Eq. (7), the element-wise multiplications can be lessened if most elements in the resulting \(G_{W}+G_{r}G_{c}\) are zeros. [24] imposed a sparse constraint upon \(G_{W}\) given that only \(G_{W}\) involves in the element-wise product of Eq. (6). However, sparse constraints often cause irregular weight matrix that receives little acceleration, a simple extension of which prevents the practicality in our settings of Eq. (7).

**Sparse Granularity**. Instead, in this paper, we devise a low-rank oriented sparsity to purchase effectual speedups. Our motive mainly stems from [45] that measured the element importance of 2D Winograd kernel using a score matrix and removed low-scored weights accordingly which leads to a distinct sparsity at different locations. We also intend to measure the weight importance, but at a more regular pattern. For ease of presentation, we denote our dense 3D Winograd weight as \(G_{W}+G_{r}G_{c}=[\alpha_{1},\alpha_{2},...,\alpha_{t^{3}}]\in\mathbb{R}^{C_{o }C_{i}\times t^{3}}\) where each column \(\alpha_{i}\in\mathbb{R}^{C_{o}C_{i}\times 1}\). Our sparse granularity consists of a single column location in \(G_{W}+G_{r}G_{c}\). In other words, pruning based on column locations results in removing the entire column elements.

The implementation of our low-rank oriented sparsity is of two stages including location scoring and weight retraining, respectively to filter out pruned target column locations and to recover the pruned model performance. In the former stage, we freeze the Winograd parameter \(G_{W}\) and initialize trainable parameters \(G_{r}\) and \(G_{c}\) as introduced in Sec. 3.2. Then, we introduce a score sequence \(S\in\mathbb{R}^{t^{3}}\), which is initialized with zeros, to evaluate location importance. Alike to Taylor pruning [35], we opt to accumulate the location magnitude and gradient in each training iteration to be served as the values of \(S\):

\[S^{t}= S^{t-1}+\frac{1}{C_{i}^{2}C_{o}^{2}}\big{(}\sum_{u=0}^{C_{i}C_{o}-1}|G _{W}+G_{r}G_{c}|^{t-1}\left(u,:\right)\big{)}\] \[\odot\big{(}\sum_{v=0}^{C_{i}C_{o}-1}|\frac{\partial\mathcal{L}}{ \partial G_{r}}\frac{\partial\mathcal{L}}{\partial G_{c}}|^{t-1}(v,:)\big{)}, \tag{8}\]

where the superscript \(t\) represents weight/magnitude and score sequence at the \(t\)-th training iteration. Here, no additional parameters are introduced during determining \(S\).

With the score sequence \(S\), we can finally derive a location set \(\mathcal{P}=\{p_{1},p_{2},...,p_{l}\}\) that contains locations whose scores within the top-\(l\) largest, leading to a sparsity rate of \((t^{3}-l)/t^{3}\).

Figure 2: Singular value analysis for layer5b of C3D and layer4b_2b of R3D-18.
Then, we can obtain a binary mask \(M\in\mathbb{R}^{t^{3}}\) as:

\[M(i)=\begin{cases}1,&i\in\mathcal{P},\\ 0,&\text{Otherwise}.\end{cases} \tag{9}\]

The location scoring stage feeds back a fixed binary mask \(M\). In the stage of retraining, \(M\) is applied to remove low-scored column locations and we only need to fine-tune the trainable parameters \(G_{r}\) and \(G_{c}\) to recover the accuracy of the pruned model. Therefore, the computation of input tiles becomes:

\[\tilde{O}=\Big{(}\big{(}(G_{W}+G_{r}G_{c})\odot M\big{)}\tilde{\odot}V\Big{)}T _{O}. \tag{10}\]

After retraining, \(G_{W}\) is finally updated by \(G_{W}=(G_{W}+G_{r}G_{c})\odot M=[\vec{0},\alpha_{p_{1}},\vec{0},\alpha_{p_{2}},\cdots,\alpha_{p_{l}},\vec{0}]\), where \(\vec{0}\), \(\alpha_{p}\) represent the pruned column and reserved important column, respectively. Fig. 3(a) gives an illustrative example of sparse training of our low-rank oriented sparse granularity.

**Speedup and Compression Mechanism**. Unlike the irregular sparse patterns [24], our low-rank oriented sparse granularity results in a very regular sparse pattern. Therefore, it can well support practical speedups in the inference by simply involving non-zero columns with the multiplication in the code implementation. The model pruned in low-rank oriented sparse granularity can be easily compressed by storing the corresponding reserved columns. The inference process after applying our low-rank oriented sparse granularity is illustrated in Fig. 3(b), and its detailed process is provided in the following.

Similar to \(G_{W}\), the transformed input tiles can be represented as \(t^{3}\) columns: \(V=[\beta_{1},\beta_{2},...,\beta_{t^{3}}]\), where \(\beta_{i}\in\mathbb{R}^{TC_{i}\times 1}\), and output transformation matrix can be represented as \(t^{3}\) rows: \(T_{O}=[\xi_{1};\xi_{2};...;\xi_{t^{3}}]\) where \(\xi_{i}\in\mathbb{R}^{1\times m^{3}}\). Based on Eq. (6), the output can be given as:

\[\begin{split}\tilde{O}&=\big{(}[\vec{0},\alpha_{p_{ 1}},\vec{0},\alpha_{p_{2}},\cdots,\alpha_{p_{l}},\vec{0}]\tilde{\odot}V\big{)}T _{O}\\ &=(\alpha_{p_{1}}\tilde{\odot}\beta_{p_{1}})\xi_{p_{1}}+(\alpha_{ p_{2}}\tilde{\odot}\beta_{p_{2}})\xi_{p_{2}}+\cdots+(\alpha_{p_{l}}\tilde{ \odot}\beta_{p_{l}})\xi_{p_{l}}\\ &=(\tilde{G}_{W}\tilde{\odot}\tilde{V})\bar{T}_{O}.\end{split} \tag{11}\]

Recall that \(\mathcal{P}=\{p_{1},p_{2},...,p_{l}\}\) contains column locations with their scores within the top-\(l\) largest. Therefore, in the inference stage, we only need to store a compact Winograd weight \(\tilde{G}_{W}=[\alpha_{p_{1}},\alpha_{p_{2}},...,\alpha_{p_{l}}]\in\mathbb{R}^ {C_{o}\mathcal{S}_{c}\times l}\) as well as the location set \(\mathcal{P}\) to extract the columns \(\bar{V}=[\beta_{p_{1}},\beta_{p_{2}},...,\beta_{p_{l}}]\in V\) and rows in \(\bar{T}_{O}=[\xi_{p_{1}};\xi_{p_{2}};...;\xi_{p_{l}}]\in T_{O}\) which are operated with the corresponding columns in \(G_{W}\). The cost of data extraction is negligible compared to the large percentage of reduction on element-wise products, _i.e._, \((l/t^{3})\).

## 4 Experiments

### Experimental Setup

Our methodology is applied on 3D CNN models including 3D Resnet [9] (denoted as R3D) and C3D [40] which consist of plentiful 3D convolution layers with \(3\times 3\times 3\) kernels and a stride of 1. We use pre-trained R3D and C3D on the Kinetics dataset [3] and Sports-1M dataset [15], and fine-tune upon the UCF101 [39] and HMDB51 [17] datasets, results of which serve as the dense models. We follow the steps in [9] and [40] to generate training samples with 16-frame length, which are cropped to 112 \(\times\) 112. For R3D and C3D, we replace all the 3D convolutional layers with \(3\times 3\times 3\) kernels and a stride of 1 (except the first layer) with 3D Winograd layers (\(t=4\)) and prune on 3D Winograd layers with our proposed low-rank Winograd transformation. The sparsity of 3D Winograd layers is defined as \((t^{3}-l)/t^{3}\), where \(l\) denotes the number of remaining columns after pruning. We initialize the low-rank matrices \(G_{r}\) and \(G_{c}\) described in Sec. 3.2. The training epochs are set to 50, of which the first 2 epochs are used for location scoring and the remaining ones are used for weight retraining. The initial learning rate is 1e-4 for C3D and 5e-4 for R3D during location scoring and is divided by 10 for every 15 epochs during weight retraining. Stochastic gradient descent (SGD) serves as the optimizer and cross-entropy loss is adopted to guide model learning.

Figure 3: (a)Sparse training of our low-rank oriented sparse granularity. (b)Inference after applying our low-rank oriented sparse granularity.
### Result Analysis

**Low-rank Winograd Transformation**. One of the supreme advantages of our low-rank Winograd transformation is that the two less storage-required matrices significantly reduce the trainable parameters during pruning in the Winograd domain. Table 1 compares the results for pruning R3D-18 in our proposed sparse pattern with and without low-rank Winograd transformation on the UCF101 dataset. As can be observed, low-rank Winograd transformation saves numerous trainable parameters (\(5.94\times\) in this situation) while achieving better performance when sparsity \(<0.7\). In the case of a large proportion (sparsity \(>0.7\)) of redundant parameters pruned in the Winograd domain, low-rank Winograd transformation can still achieve nearly the same performance as the full Winograd-domain parameters. Results in Table 1 well validate the effectiveness of low-rank Winograd transformation for pruning the redundant Winograd-domain parameters and reducing the storage requirement.

**Low-Rank Oriented Sparse Granularity**. We compare the proposed method with state-of-art methods of pruning 3D CNNs in the different domains, such as FP (Filter Pruning) [36], RT3D (Group Pruning) [37], DPR (Stripe Pruning) [46] in the spatial domain, and MRP [38] in the Winograd domain. Table 2 displays the pruning results of different methods. As can be seen, compared with pruning in the Winograd domain, spatial-domain pruning methods suffer the most performance degradation while achieving the same or even lower speedups. As a contrast, our proposed Winograd-domain pruning pattern achieves the highest speedup ratio and even obtains the highest accuracy for both C3D and R3D-18. For example, when pruning C3D, our method achieves \(5.8\times\) speedups with an accuracy loss of \(0.9\%\) while MRP achieves \(4.3\times\) speedups with an accuracy loss of \(1.1\%\), and RT3D achieves only \(3.6\times\) speedups with an accuracy loss of \(1.4\%\). Similarly, our method also outperforms other methods by a large margin when pruning R3D-18.

To further investigate the effect of sparsity on our proposed method, we evaluate low-rank oriented sparse granularity on R3D-18 and R3D-34 on UCF101 and HMDB51 datasets. Fig. 4 demonstrates the performance results of R3D-18 and R3D-34 under different sparsity ratios. As can be seen, our method is capable of maintaining performance drops within \(1\%\) when the sparsity ratio \(<0.5\). However, due to the extremely regular sparse granularity of our pruning pattern, our method degrades drastically if the sparsity ratio \(>0.8\).

**Acceleration Performance**. The acceleration capacity of our proposed method is evaluated on CPUs-based platforms. We first compare our proposed method with Img2col and Winograd algorithms which are commonly used methods for accelerating convolutional operations. For fair comparison, the inference code for our method and the compared methods are all implemented based on the mobile inference framework of Tencent ncnn2 and optimized by advanced SIMD (Single Instruction, Multiple Data). We respectively deploy C3D with different acceleration methods to obtain the end-to-end network inference latency on the Redmi Note10 platform. Table 3 presents the experimental results. Compared with Img2col, the Winograd algorithm reduces a large amount of multiplications, which makes it obtain a 2.1\(\times\) acceleration ratio and our method is able to reduce more inference latency based on the Winograd algorithm. For example, our method obtains a 5.0\(\times\) acceleration ratio under the sparsity of 0.9 and a 3.4\(\times\) acceleration ratio under the sparsity of 0.3. The results shown in Table 3 demonstrate the excellent acceleration capacity of our proposed method.

Footnote 2: [https://github.com/Tencent/ncnn](https://github.com/Tencent/ncnn).

For Winograd convolution, the element-wise products in the Winograd domain occupy a vast majority of the inference time. The core acceleration mechanism of our method is to reduce a large number of operations in the Winograd domain by pruning Winograd-domain weights. Due to our

\begin{table}
\begin{tabular}{c|c|c|c|c|c|c|} \hline  & Trainable & \multicolumn{5}{c|}{Sparsity} \\  & Parameters & 0.1 & 0.3 & 0.5 & 0.7 & 0.9 \\ \hline w/o Low-Rank & 170.0M & 83.3 & 83.3 & 82.9 & 80.7 & 73.4 \\ \hline Low-Rank & 28.6M & 83.4 & 83.4 & 83.1 & 80.7 & 73.3 \\ \hline \end{tabular}
\end{table}
Table 1: Results of our proposed sparse pattern with and without low-rank Winograd transformation. The experiments are conducted using R3D-18 pruned with different sparsity on UCF101.

\begin{table}
\begin{tabular}{c|c|c|c} \hline Model & Methods & Speedup & Accuracy(\%)\(\downarrow\) \\ \hline \multirow{8}{*}{C3D} & FP* [36] & 1.6\(\times\) & 1.6 \\  & FP* [36] & 3.7\(\times\) & 10.1 \\  & DPR [46] & 2.0\(\times\) & 3.3 \\  & DPR [46] & 4.0\(\times\) & 6.6 \\  & RT3D [37] & 2.6\(\times\) & 1.0 \\  & RT3D [37] & 3.6\(\times\) & 1.4 \\  & MRP [38] & 3.8\(\times\) & 0.4 \\  & MRP [38] & 4.3\(\times\) & 1.1 \\  & Ours(sparsity=0.3) & 4.3\(\times\) & 0.6 \\  & Ours(sparsity=0.5) & 5.8\(\times\) & 0.9 \\ \hline \multirow{8}{*}{R3D-18} & FP* [36] & 1.6\(\times\) & 2.6 \\  & FP* [36] & 4.0\(\times\) & 8.5 \\  & DPR* [46] & 2.0\(\times\) & 3.4 \\  & DPR* [46] & 4.0\(\times\) & 5.0 \\  & MRP [38] & 3.2\(\times\) & 0.1 \\  & MRP [38] & 3.8\(\times\) & 1.2 \\  & Ours(sparsity=0.3) & 4.3\(\times\) & 0.1 \\  & Ours(sparsity=0.5) & 5.0\(\times\) & 0.5 \\ \hline \end{tabular}
\end{table}
Table 2: Results of different pruning methods on UCF101, where * denotes our re-implementation. The experiment is conducted using C3D (baseline accuracy 81.6\(\%\)) and R3D-18 (baseline accuracy 83.5\(\%\)) and the speedup ratio is computed by GFLOPs reduction.

Figure 4: Results of R3D-18 and R3D-34 pruned with our proposed low-rank oriented sparse granularity under different sparsity. The experiment is conducted on UCF101(left) and HMDB51(right).
proposed regular sparse pattern, extracting the corresponding arithmetic data only introduces a very small amount of overhead which makes sure that the sparsity obtained by pruning can be converted into actual speedups. Fig. 5 manifests the Winograd-domain inference latency of our method and its dense Winograd counterpart. As can be seen from the table, our proposed pruning pattern effectively translates the sparsity into actual speedups in the Winograd domain across different layers of C3D.

### Ablation Study

**Rank Selection**. To further explore the effect of ranks on low-rank Winograd transformation, we have tried different settings of rank \(s\) for \(G_{r}\) and \(G_{c}\). For R3D, we set ranks based on different blocks, and for C3D, we set ranks based on different layers. Specifically, for a rank set \(\mathbb{S}=\{s_{1},\cdots,s_{l}\}\), \(s_{i}\) denotes the concrete rank for \(i\)-th Winograd layer or \(i\)-th block containing Winograd layer and \(l\) denotes the total number of Winograd layers/blocks. Table 4 shows the effect of rank setting. As can be observed from the displayed table, a modest increase in ranks will improve the performance of low-rank Winograd transformation and deeper layers tend to require larger ranks than shallow layers. Considering the overall effect, we finally choose \(\mathbb{S}=\{2,4,8,12\}\) for R3D model and \(\mathbb{S}=\{1,1,2,4,8,12,12\}\) for C3D model to perform our experiments in this paper.

**Indicators of Location Importance**. In the stage of location scoring, the score sequence \(S\) updated by different metrics will produce different pruned columns, result of which greatly affects the performance of the sparse model. We compare several different indicators on C3D and R3D-18 models in Table 5. The results show that when selecting pruned columns, gradient-based score (\(S_{grad}\)) has a greater impact on the assessment of selecting locations than magnitude-based score (\(|G_{W}|\) and \(|G_{r}G_{c}|\)), while the combination of the two gives the best results.

## 5 Conclusion

Here, we have presented a novel low-rank Winograd transformation to reduce the over-parameterized issue in 3D CNNs. We decouple the original Winograd weight matrix into two less storage-required matrices, leading to remarkable trainable parameter reduction. The low-rank constraint well eliminates the redundant parameters and drives the updating toward the main directions of the whole Winograd space. Consequently, our low-rank Winograd transformation leads to a better performance increase. In addition, we have also introduced a low-rank oriented sparse granularity to purchase effectual speedups. It models the column-wise importance of the Winograd weight matrix and removes the low-scored ones. In this fashion, the sparsity tends to be more regular, which therefore better supports the practical acceleration in comparison with the existing irregular sparsity.
