SeKron: A Decomposition Method Supporting Many Factorization Structures
Authors: Marawan Gamal
Ali Mosleh
Marzieh S. Tahaei
Vahid Partovi Nia
Venue: Submitted to ICLR 2023 (2023)
Keywords: model compression
tensor decomposition
factorization structure

Abstract: While convolutional neural networks (CNNs) have become the de facto standard for most image processing and computer vision applications, their deployment on edge devices remains challenging. Tensor decomposition methods provide a means of compressing CNNs to meet the wide range of device constraints by imposing certain factorization structures on their convolution tensors. However, being limited to the small set of factorization structures presented by state-of-the-art decomposition approaches can lead to sub-optimal performance. We propose SeKron, a novel tensor decomposition method that offers a wide variety of factorization structures, using sequences of Kronecker products. By recursively finding approximating Kronecker factors, we arrive at optimal decompositions for each of the factorization structures. We show that SeKron is a flexible decomposition that generalizes widely used methods, such as Tensor-Train (TT), Tensor-Ring (TR), Canonical Polyadic (CP) and Tucker decompositions. Crucially, we derive an efficient convolution projection algorithm shared by all SeKron structures, leading to seamless compression of CNN models. We validate SeKron for model compression on both high-level and low-level computer vision tasks and find that it outperforms state-of-the-art decomposition methods.

Under review as a conference paper at ICLR 2023
SEKRON: A DECOMPOSITION METHOD SUPPORTING MANY FACTORIZATION STRUCTURES
Anonymous authors Paper under double-blind review
ABSTRACT
While convolutional neural networks (CNNs) have become the de facto standard for most image processing and computer vision applications, their deployment edge devices remains challenging. Tensor decomposition methods provide means compressing CNNs meet the wide range of device constraints by imposing certain factorization structures on their convolution tensors. However, being limited to the small set of factorization structures presented by state-of-the-as decomposition approaches can lead to sub-optimal performance. We propose SeKron, a novel tensor decomposition method that offers wide variety of factorization structures, using sequences of Kronecker products. The flexibility of SeKron leads to many compression rates and also allows it to cover commonly used factorizations such Tensor-Traie Train (TT), Tensor- Ring (TR), Canonical Polyadic (CP) and Tucker. Crucially, we derive an efficient convolution projection algorithm shared by all SeKron structures, leading to seamless compression of CNN models. We validate our approach for model compression on both high-level and low-level computer vision tasks and find that it outperforms state-of-the-art decomposition methods.
INTRODUCTION
Deep learning models have introduced new sfute-of-the-arr solutions to both high-level computer vision problems (He al. 2016 Ren et al. 2015), and low-level image processing tasks (Wang et al.) 2018b Schuler et al. 2015 Kokkinos & Lefkimmiatis 2018) through convolutional neural networks (CNNs). Such models are obtained at the expense millions of training parameters that come along deep CNNs making them computationally intensive. As a result, many of these models are of limited use as they are challenging to deploy on resource-constrainee edge devices. Compared with neural networks for high-level computer vision tasks (e.g., ResNet-50 (He et al. 2016)), models for low-level imaging problems such as single image super-resolution have much a higher computational complexity due to the larger feature map sizes. Moreover, they are typically infeasible computing servers. Thus, their deployment on edge devices is even more critical.
on cloud
In recent years increasing trend has begun in reducing the size of state-of-the-art CNN backbones through efficient architecture designs such as Xception (Chollet 2017). MobileNet (Howard et al.) 2019). ShuffleNet (Zhang et 2018c). and EfficientNet (Tan & Le 2019), to name few. On the other hand, there have been studies demonstrating significant redundancy in the parameters of large CNN models, implying that in theory the number of model parameters can be reduced while maintaining performance (Denil et al. 2013). These studies provide the basis for the development of many model compression techniques such as pruning (He al. 2020), quantization (Hubara et al.) 2017) knowledge distillation (Hinton et al. 2015), and tensor decomposition (Phan et al. 2020).
Tensor decomposition methods such as Tucker (Kim et al. 2016), Canonical Polyadic (CP) (Lebddey et 2015). Tensor-Train (TT) (Novikov et al. 2015)) and Tensor-Ring (TR) (Wang et al. 201 (0) rely on finding low-rank approximations of tensors under some imposed factorization structure as illustrated in Figure Dp. In practice, some structures more suitable than others when decomposing tensors. Choosing from a limited set of factorization structures can lead to sub-optimal compressions as well lengthy runtimes depending the hardware. This limitation can be alleviated by reshaping tensors prior to their compression to improve performance as shown in (Garipov et al. 2016). However, this approach requires time-consuming development of customized convolution algorithms.

---

Under review as a conference paper at ICLR 2023
A
W
(a)
Tucker
CP
TR
S
(b)
A (3)
4
.
(3)
18
X
X
X
SeKron with two sequence lengths
TT
ScKron
Figure 1: (a): Tensor network diagrams of various decomposition methods for a 4D convolution tensor W E IR Fx K.. Unlike all other decomposition methods where J, c, h, w index fixed dimensions (i.e., dimensions of W), SeKron is flexible in its factor dimensions, with fu.Ck, Cb, hg, Wh, Vk E (1,...,,S) 5} indexing over variable dimension choices, as well as its sequence length S. Thus, allows for wide range of factorization structures be achieved. (b): Example of 16 x 16 tensor W that can be more efficiently represented using a sequence of four Kronecker factors (requiring 16 parameters) in contrast to using sequence length of two (requiring 32 parameters).
We propose SeKron, novel tensor decomposition method offering wide range of factorization structures that share the same efficient convolution algorithm. Our method is inspired by approaches based on the Kronecker Product Decomposition (Thakker al. 2019 Hameed other decomposition methods, Kronecker Product Decomposition generalizes the product of smaller factors from vectors and matrices a range of tensor shapes, thereby exploiting local redundancy between arbitrary slices of munti-diimesional weight tensors. SeKron represents tensors using sequences of Kronecker products to compress convolution tensors in CNNs. Using sequences of Kronecker products leads to a wide range of factorization structures including commonly used ones such as Tensor-Train (TT), Tensor-Ring Ring (TR), Canonical Polyadic (CP) and Tucker.
(022).. Unlike
Sequences of Kronecker products also have the potential to exploit local redundancies using far fewer parameters as illustrated in the example in Figure[p. By performing the convolution operation using each of the Kronecker factors independently, the number of parameters, computational intensity, and runtime are reduced, simultaneously. Leveraging the flexibility SeKron, we find efficient factorization structures that outperform existing decomposition methods various image classification and low-level image processing super-resolution tasks. In summary, our contributions are:
Introducing SeKron, a novel tensor decomposition method based on sequences of Kronecker products that allows for a wide range of factorization structures.
Providing solution to the problem of finding the summation of sequences of Kronecker products between factor tensors that well approximates the original tensor.
Deriving a single convolution algorithm shared by all factorization structures achievable by SeKron, utilized compressed convolutional layers in CNNs.
Improving the state-of-the-an tht of low-rank model compression on image classification (high- level vision) benchmarks such as ImageNet and CIFAR-10, as well as super-resolution (low-level vision) benchmarks such as Set4, Set14, B100 and Urban100.
RELATED WORK ON DNN MODEL COMPRESSION
Sparsification. Different components of DNNs, such as weights (Han et al. 2015b a). convolutional filters (He et al. 2018 Luo et al. (017) and feature maps (He et al. 2017 Zhuang al. (0188) can
be sparse. The sparsity can be enforced using sparsity-awe aware regularization (Liu et al. 2015] Zhou
al. 2016) or pruning techniques (Luo et al. 2017 Han al. 2015b). Many pruning methods (Luo
2

---

Under review as a conference paper at ICLR 2023
et al. 2017; Zhang et al. 2018b) aim for a high compression ratio and aceuracy regardless of the structure of the sparsity. Thus, they often suffer from imbalanced workload caused by irregular memory access. Hence, several works aim at zeroing out structured groups of DNN components through more hardware friendly approaches (Wen et al. 2016).
The computation and memory complexity of DNNS can be reduced by quantizing model parameters into lower bit-widths; wherein the majority of research works use fixed-bit -it quanti-
Quantization.
zation. For instance, the methods proposed in (Gysel al. 2018 Louizos et al. 2018 use fixed 4 or 8-bit quantization. Model parameters have been quantized even further into ternary (Li et al. 2016
Zhu al. 2016) and binary (Courbariaux et al. 2015, Rastegari et al. 2016) Courbariaux al. 2016
representations. These methods often achieve low performance even with unquantized activations al. 2016). Mixed-pres preeedppreiiioon approaches, however, achieve more competitive performance as shown in (Uhlich et al. 2019) where the bit-width for each layer is determined in an adaptive manner. Also,
choosing uniform (Jacob et al. 2018) or nonuniform (Han et al. 2015a Tang 20.7 [Zhang et al.) 20) quantization interval has important effects on the compression rate and the acceleration.
Tensor Decomposition. Tensor decomposition approaches are based on factorizing weight tensors into smaller tensors to reduce model sizes (Yin et al. 202T). Singular value decomposition (SVD) applied on matrices as a 2-dimensional instance of tensor decomposition is used as one of the pioneering approaches to perform model compression (Jaderberg et al. (2014). Other classical high- dimensional tensor decomposition methods, such as Tucker (Tucker 1963) and CP decomposition (Harshman et al. 1970), also adopted perform model compression. However, using these methods often leads to significant accuracy drops (Kim et al. 2015, Lebedev et al. 2015 Phan et al. 2020). The idea of reshaping weights of fully-connected layers into high-dimensional lensors and representing them in TT format (Oseledets) 201T) was extended to CNNs in (Garipov et al. 2011)). For multidimensional tensors, TR decomposition (Wang et al. 201 8a) has become a more popular option than TT WWan et al. 2017). Subsequent filter basis decomposition works polished these approaches using a shared filter basis. They have been proposed for low-level computer vision tasks such as single image super- resolution in (I.i et al. 2019). Kronecker factorization is another approach to replace the weight tensors within fully-connected and convolution layers (Zhou et al. 2015). The rank- I Kronecker product representation limitation of this approach is alleviated in (Hameed al. 2022). The compression rate in (Hameed et al. (2022) is determined by both the rank and factor dimensions. For fixed rank, the maximum compression is achieved by selecting dimensions for each factor that are closest to the square root the original tensors' dimensions. This leads to representations with more parameters than those achieved using sequences of Kronecker products shown in Fig. Db.
There has been extensive research on tensor decomposition through characterizing global correlation of tensors (Zheng et al. 2021), extending CP to non-Gaussias Gaussian data (Hong et al. 2020), employing augmented decomposition loss functions (Afshar et al. 2021). etc. for different applications. Our main focus in this paper is on the ones used for NN compression.
Other Methods NNs can also be compressed using Knowledge Distillation (KD) where a large pre- trained network known as teacher is used train a smaller student network (Mirzadeh et al. [2020] Heo
et 2019)) Sharing weights in a more structured manner can be another model compression approach as FSNet Yang et al. 2020) which shares filter weights across spatial locations or ShaResNet (Boulch)
2018) which reuses convolutional mappings within the same scale level. Designing lightweight CNNs
(Sandler et al. 20188] 8 landola et al. 2016 Chollet 2017 7 Howard et al. 2019 Zhang et al, 2018c
Tan
Le 2019) is another direction orthogonal to the aforementioned approaches.
3 METHOD
In this section, we introduce SeKron and how it can be used to compress tensors in deep learning models. We start by providing background on the Kronecker Product Decomposition in Section 3.1 Then, introduce our decomposition method in 3.2 In Section 3.3] provide algorithm for computing the convolution operation using each of the factors directly (avoiding reconstruction) at runtime. Finally, discuss the computational complexity of the proposed method in Section 3.4
3

---

Under review as a conference paper at ICLR 2023
3.1 PRELIMINARIES
Convolutional layers prevalent in CNNs transform an input tensor X E IR RCKKakk using a weight tensor W E TR RRxxCXXxXK via a multi-linear map given by
Kn
K
V 1,2.9
W Sea.3 X cetzejty
== c=1
i=1
where C' and F denote the number of input channels and output channels, respectively, and K₁, x K denotes the spatial size of the weight (filter).
Tensor decomposition seeks an approximation to replace W, typically through finding lower-rank lensors using SVD. One such approximation comes from the fact that any tensor W E IR ths K.. be written
of Kronecker products (i.e., W Σx= R2
A, X Br, where A,
IR X-xXa B, IR X--x and 0 wi for {1,-... N).. (Hameed al. 2022). Thus, lower-rank approximation can be obatined by solving
R
min (A)).BB))
W
Σ
A,
B,
(2)
r=1
for sums of Kronecker products ( < R) using the SVD of a particular reshaping (unfolding) of
W, where ||
||r denotes the Frobenius norm.
3.2 SEKRON TENSOR DECOMPOSITION
The Kronecker decomposition in equation 2 can be extended to finding an approximating sequence
of Kronecker factors (R) IR
Ri x x xa; x...aa as follows:
(k)
Rs-1
min (400)
W
A (1)
( r112
Σ
An-rs-1
(S-1)
Amprss-
P5-1=1
(3)
Although this non-convex objective, a quasi-optimal solution based on recursive application of SVD is given in Theorem 1. Note that alternative expansion directions to 3 are viable (See Appendix B).
Theorem 1 (Tensor Decomposition using Sequence of Kronecker Products). Any tensor W
IR XWN can be represented by sequence of Kronecker products between S IN factors:
R
R2
Re-1
W
=
PITZ
(2)
... 8
Σ
(5-1) 11 & (S)
(4)
r1=1
1=11=1
where R, IN and (A) IR Ri X R4
xa
Proof. See Appendix
C
Our approach to solving equation involves finding two approximating Kronecker factors that minimize the reconstruction error with respect to the original tensor, then recursively applying this procedure on the latter factor found. More precisely, we define intermediate tensors
RE+1
Re49
RS-1
B PI
(S-1) M--
(S) & Arp-ssn (5)
7641=1
P
M5-1=1
allowing us re-write the reconstruction error in equation
for the t iteration, as
Rs
min
W
r
(k)
k B
Fi
(6)
(A (A)
B
rt=1
F
4

---

Under review as a conference paper at ICLR 2023
Algorithm 1: SeKron Tensor Decomposition
Input: Input tensor W X Kronecker factor shapes {d()) ji=1
Output: Kronecker factors {A)
for f- ,,,
do
d(a) (
d()) < I (b)
W UNFOLD shape - d // IR BxLxIII- &
U, V +- BATCHSVD(W) // U E IR BxLxR where R 1=m ve2))
A STACK U henr shape d(a)) 1,2,,.,... 1,2 ... R))
( (RESHAPEE V birr shape d(b)) b 1,2....4 r 1,2 R))
W t ((i)
end
A (5) - BS-1
return (A]
In the first iteration, the tensor being decomposed is the original tensor (i.e., W < W). Whereas in subsequent iterations, intermediate tensors are decomposed. At each iteration, we can convert the problem in equation to the low-rank matrix approximation problem
Rv
min
W
Σ
(R)
(
PI-
(a
Fy
through reshaping, such that the overall sum of squares is preserved between equation equation 7 The problem in equation can be readily solved, as it has a well known solution using SVD. The reshaping operations that facilitate this transformation are
W FI MAT(UNFOLD (W (W (k) d (B (2)
(8)
(k) ari..r (A
(k)
Arginrk
b
( VEC (k) r
where UNFOLD reshapes tensor ((()) P by extracting multidimensional patches of shape
d f Pr..ir
from tensor (k) W in any order, then stacking them along a new first dimension.
Vector dg denotes vector describing the shape of tensor B, VEC IR x xxx
flattens tensor, MAT Rd xd2x--xxxx -> dRd xd2-ddy matricizes tensor and I denotes an identity tensor with the same number of modes as A and each dimension set to one.
Once each B (K)) ",,,,, is obtained by solving equation (and using the inverse of the VFC operation in equation 9 we proceed recursively by setting ( (1++1)
and solving the k + 1hh iteration of equation equation 7 In other words, the 1.th iteration, we find Kronecker factors A A and (k),
Pi--rs + -B( ((k)
where the latter is used in the following iteration. Except in the final iteration (i.e.,
S 1), where the intermediate tensor B (k), is the solution to the last Kronecker factor A (9) (See Algorithm I
By virtue of the connectivity between all of the Kronecker factors as illustrated in Figure Db. SeKron can achieve many other commonly used structures, as stated in the following theorem:
Theorem 2. The factorization structure imposed by CP. Tucker, TT and TR when decomposing given tensor W E IR X--Xwy can be achieved using SeKron.
Proof. See Appendix C
3.3 CONVOLUTION WITH SEKRON STRUCTURES
In this section, we provide an efficient algorithm for performing a convolution operation using a tensor represented by sequence of Kronecker factors. Assuming W is approximated sequence
5

---

Under review as a conference paper at ICLR 2023
Algorithm 2: Convolution operation using a sequence of Kronecker factors
Input: (A (A)) AD) 11=1
TRR*K Output: X E IR Nx Ih fxxIxwW
X IR NxCxHXW
for
S,S 1,..., do
if = S then
X' < CONV3D(UNSQUBEEBCC 1), UNSQUEEZE
/+ IR TR.NXIlIE=+ Tex 4xHxW IR Nx fon-- XXHW */
X +- RESHAPE (X)
else
X' < CONV3D ( ggropps ri)
/+ IR NxIIl==+ fixr;fixll xxHxW IR
X' <- RESHAPF2
end
end
return
of Kronecker products using SeKron, i.e., W x W and
R
R2
Re-1
W
= Σ
Σ
S-
@ A
(10)
11--88-1
r1=1
78-1=1
the convolution operation in equation D can be re- re-written
Kr.K=.C
P
A--1
y Fzy Σ
Σ r1=1
(1) 2
H
Σ
A
(5-1) AT--T-1
(8) A
X Reitzity
(11)
b..0=1
TS-1=1
faij
Due the factorization structure of tensor W, the computation in equation out without its explicit reconstruction. Instead, the projection can be performed using each of the Kronecker factors independently. This property is essential performing efficient convolution operations using SeKron factorizations, and leads to a reduction in both memory and FLOPs at runtime. In practice, this amounts replacing large convolution operation (i.e., one with large convolution tensor) with sequence of smaller grouped 3D convolutions, as summarized in Algorithm 2
11 be carried
The ability to avoid reconstruction at runtime when performing convolution using any SeKron factorization the result of the following Theorem:
Theorem 3 (Linear Mappings with Sequences of Kronecker Products). Any linear mapping using given tensor W can be written directly in terms of its Kronecker factors A(k) (1))
IR Ri Xax--Ry Ry za (8)
xx.xa That is:
R R Σ
A(5)
W Wipwiy X t JNtEN
13) (9) X f0.))er.-
151 18)...
riJi
..N
riurs
TI...NN
where (k) E IN is a function of input indices (see Appendix A and f(im) = DS In II an
Proof. See Appendix C
Using Theorem
3 we re- eerit the projection in equation
11 directly in terms of Kronecker factors
y fzy Σ
(1)
ij..,m
12
(8-1) m.
- INewiNjj X fz)) (12)
(8)
where i - (i1, (i,....,in) j (i,,2, ... .jnj),, (ci, CN) denote vectors containing
indices in. je, C₁ that enumerate positions in tensors (k). Finally, exchanging the order of

---

Under review as a conference paper at ICLR 2023
summation separates the convolution follows:
fay Σ
(1) rihonii
Σ
A
"1 ifxewiziN f00).f(0-a.f00+ (13)
Overall, the projection equation 13 can be carried out efficiently using a sequence of grouped 3D convolutions with intermediate reshaping operations described in Algorithm Refer to Appendix Capendix([foor universal approximation properties neural networks when using SeKron.
3.4 COMPUTATIONAL COMPLEXITY
In order to decompose given tensor using our method, the sequence length and the Kronecker factor shapes must be specified. Different selections will lead to different FLOPs, parameters, and latency. Specifically, for the decomposition given by equation 10 for W E IR xexhxx using factors
PI E fex xh,xw, the compression ratio (CR) and FLOPs reduction ratio (FR) are given by
I1 Sayhis 1=1 [lk= Rehechhw
Ih Succhrwe
CR
FR
(14)
ES
(II Fi))
(Ii- Rs) (ITi Ck) how,
Applying SeKron compress DNN models requires a selection strategy for sequence lengths and factor shapes for each layer in network. We adopt a simple approach that involves selecting configurations that best match desired CR while also having a lower latency than the original layer being compressed, as FR may not be a good indicator of runtime speedup in practice.
EXPERIMENTAL RESULTS
To demonstrate the effectiveness of SeKron for model compression, we evaluate different CNN models on both high-level and low-level computer vision tasks. For image classification tasks, we evaluate Wede (Zagoruyko & Komodakis 2016) and ResNet50 (He et al. 2016) models on CIFAR-10 (Krizhevsky 2009) and ImageNet Krizhevsky et al. 2012). respectively. For super- resolution task, evaluate EDSR 8- 128 and SR trained on DIV2k(Agustssson & Timofte 2017). Lastly, we discuss the latency of our proposed decomposition method. In all experiments we compress convolution layers of pre-trained networks using various compression approaches and then re-train the resulting compressed models. We provide implementation details in Appendix [
4.1 IMAGE CLASSIFICATION EXPERIMENTS
First, we evaluate SeKron by compressing WideResNet16-8 Zagoruyko & Komodakis 2016) for image classification CIFAR- 10 and comparing against various approaches. Namely, PCA (Zhang et al. 2016) which imposes that filter responses lie approximately on a low-rank subspace; SVD- Energy (Alvarez & Salzmann 2017) which imposes low-rank regularization into the training procedure; L-Rank (learned rank selection) (Idelbayev & Carreira- Perrinaa- 2020) which jointly optimizes over matrix elements and ranks; ALDS (Liebenwein al. (021] which provides a global compression framework that finds optimal layer-wise compressions leading to an overall desired global compression rate; TR Wang et al. 2018a): TT (Novikov et al. 2015) as well as two pruning approaches FT (Li et al. (017) and PFP (Liebenwein et al. 2022)).
Figure 2 shows the CIFAR- 10 classification performance drop (i.e., A Top-1) versus compression rates using different methods. SeKron outperforms all other decomposition and pruning methods, at variety of compression rates. In Table we highlight that at a compression rate 4x SeKron outper- forms all other methods with small accuracy drop of -0.51, whereas the next best decomposition method (omitting rank selection approaches) suffers a - 1.27 drop in accuracy.
Next, we evaluate SeKron to compress ResNet50 for the image classification task ImageNet. Table commpree our method to other compression approaches. Most notably, SeKron outperforms all decomposition methods, achieving 74.94% Top-1 accuracy which is ~1.1% greater than the second highest accuracy achieved by using TT decomposition. At the same time, SeKron is 3x faster than TT on single CPU.
7

---

Under review as a conference paper at ICLR 2023
Table Performance of compressed WideResNet16- using various methods on CIFAR-10
Model
CR
A Top-1 (%)
A Top-1 (%
ALDS
4.0
-0.73
SeKmnn
ALDS
L-Rank
4.0
-3.52
SVD-Faegg
FT
4.1
-.50
PFP
4.0
0.94
L-Rank
SVD
4.0
4.40
PCA
4.0
-2.88
20
40
60
SVD Energy
4.0
1.27
Parameters Retained (%)
TT
4.0
-286
TR
4.0
0.70
Figure 2: Performance drop of WideResNet at various compression rates achieved by differ- ent methods on CIFAR-10.
CP
4.0
-3.13
Tucker
4.0
1.61
SeKron (Ours)
4.1
0..1
Table 2: Performance of ResNet50 using various compression methods measured on ImageNet. indicates models obtained from compressing baselines with different accuracies, for this reason we report accuracy drops of each model with respect to their own baselines well. The baselines compared are FSNet (Yang et al. 2020). ThiNet (Luo et al. 2017) CP (He et al. 2017) MP (Liu et al. 2019) and Binary Kronecker (Hameed et al. 2022)
Method
Type
Params (E+6) CR FLOPS (E+9)
CPU (ms)
Top-1 A Top-1
FSNet
Other
13.9/
73.11
ThiNet
2.1
71.01 / 1.9
CP1
Pruning
2.0
73.30/ -3.0
MP
10.6 2.4
73.40/ -3.2
Tensor Ring
13.9 1.8
2.1
105 +
73.30/ -27
Tensor Train
13.3 1.9
1.9
395 + 54
73.85 2211
Decomposition
Binary Kronecker
12.0/2.1
73.95 / 2.0
SeKron S (Ours)
12.3
2.9
125 +
74.66 113
ScKron S = 3 (Ours)
13.8 1.8
2.5
133 + 4
74.94 111
Baseline
Uncompressed
25.5/ 1.0
4.10
133 1 33
75.99 / 0.0
4.2 SUPER- RESOLURIOOO EXPERIMENTS
In this section we use SeKron to compress SRResNet (Ledig et al. 2017) and EDSR-8 8-18 (Li et al. 2019). Both networks were trained on DIV2K (Agustsson & Timofte 2017) and valuated on Set5 (Bevilacqua et al. 2012), Set14 (Zeyde et al. 2012). B 1100 Martin et al. 2001) and Urban 100 (Huang al. 2015). Table presents the performances in terms of PSNR measured on the test images for the models once compressed using SeKron along with the original uncompressed models.
Among model compression methods, Filter Basis Decomposition (FBD) (Li al. 2019) has been previously shown to achieve state-of-the-art compression on super-resolution CNNs. Therefore, we compare our model compression results with those obtained using FBD as shown in Table 3 We highlight that our approach outperforms FBD, on all test datasets when compressing SRResNet16 at similar compression rates. this table suggests, when compression rate increased, FBD results in much lower PSNRs for both EDSR- 8- 1-828 and SRResNet16 compared to our proposed SeKron.
4.3 CONFIGURING SEKRON CONSIDERING LATENCY AND COMPRESSION RATE
Using the configuration selection strategy proposed in 3.4 we find that small sequence length (S) is limited to few achievable candidate configurations (and consequently compression rates) that do not sacrifice latency. This illustrated in Figure 3 for S = where targeting a CPU latency less than ms and compression ratio less than 10x leaves only 3 options for compression. In contrast,
8

---

Under review as a conference paper at ICLR 2023
Table PSNR (dB) performance of compressed Se and EDSR-8-128 (x4 scaling factor)
models using FBD (with casis-64-161 (Li et al. 2019) and our SeKron
Dataset
Model
Method
Params (E+6)
CR
Sct5
Sct14
B100
Urban100
Baseline
1.54
1.0
32.03
28.5
27.52
25.88
SRResNer16
FBD
0.65
2.4
31.84
28.38
27.39
25.54
SeKron
0.65
2.4
31.91
28.42
27.43
25.64
FBD
0.36
4.3
31.49
28.18
27.28
25,20
SeKron
0.37
4.2
31.73
28.32
27.37
25.48
Baseline
3.70
32.13
28.55
27.55
26.02
EDSR-8-122 128
FBD
1.62
2.3
31.80
28.34
27.40
25.54
SeKron
1.50
2.5
31.79
28.34
27.39
25.52
FBD
0.48
7.8
31.64
28.23
27.32
25.31
ScKron
0.47
7.8
31.77
28.32
27.38
25.46
Table 4: CPU latency (ms) for uncom- pressed (baseline) and compressed SR- ResNet16 and 1OSRR-8-125 models us- ing SeKron
Model
Method
CR
CPU (ms)
Baseline
1.0
72 + 3
1.MM Contor
SRResNet16
SeKron
2.4
70 +
ScKron
4.2
70 2
Rogion
Compresiin Rani
Baseline
1.0
151 1
Figure 3: CPU latency for candidate configurations obtained using SeKron tensor W IR 512x5122x333 with (red) and S = (blue), aiming for a speedup (e.g., < 5 ms) and a typical compression rate (e.g., 10x).
EDSR-8-128
SeKron
124 +
ScKron
7.8 131 9
increasing the sequence length to S 3 leads to wider range of achievable compression rates (i.e., 129 configurations). Despite the flexibility they provide, large sequence lengths lead to an exponentially larger number of candidate configurations and time-consuming generation of all their runtimes. For this reason, unless otherwise stated, we opted to use = 3 in all the mentiooe experiments it provided suitable range of compression rates and manageable search space.
As an example, in Table we compress EDSR-8 1-18 using a compression rate of CR = 2.5x, by selecting configurations for each layer that satisfy the desired CR while simultaneously resulting in speedup. This led to an overall model speedup 124ms (compressed) vs. 15 151ms (uncompressed).
5 CONCLUSIONS
We introduced SeKron, a tensor decomposition approach using sequences of Kronecker products. SeKron allows for wide variety of factorization structures be achieved, while, erucially, sharing the same compression and convolution algorithms. Moreover, SeKron has been shown to generalize popular decomposition methods such as TT, TR, CP and Tucker. Thus, mitigates the need for time-consuming development of customized convolution algorithms. Unlike other decomposition methods, SeKron not limited to a single factorization structure, which leads to improved com- pressions and reduced runtimes different hardware. Leveraging SeKron's 's flexibility, find efficient factorization structures that outperform previous decomposition methods on various image classification and super-resolution tasks.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ardavan Afshar, Kejing Yin, Sherry Yan, Cheng Qian, Joyce Ho, Haesun Park, and Jimeng Sun. Swift: scalable wasserstein factorization for sparse nonnegative tensors. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp.
2021.
Eirikur Agustsson and Radu Timofte. NTIRE 2017 challenge on single image super-resolution Dataset and study. In IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pp. 122-1131, 2017.
Jose M Alvarez and Mathieu Salzmann. Compression-awan training of deep networks. In Advances in Neural Information Processing Systems, 2017.
Marco Bevilacqua, Aline Roumy, Christine Guillemot, and Marie line Alberi Morel. Low-complexity single-image super-resolution based on nonnegative neighbor embedding. In British Machine Vision Conference, pp. 135.1-135. 2012.
Alexandre Boulch. Reducing parameter number in residual networks by sharing weights. Pullern Recognition Letters, 103:53-59, 2018.
François Chollet. Xception: Deep learning with depthwise separable convolutions. In IEEE Confer- ence on Computer Vision and Pattern Recognition, pp. 1251-1258, 2017.
Matthieu Courbariaux, Yoshua Bengio, and Jean- David. Binaryconnect: Training deep neural networks with binary weights during propagations. Advances in Neural Information Processing Systems, 28, 2015.
Matthieu Courbariaux, Itay Hubara, Daniel Soudry, Ran El- Yaniv, and Yoshua Bengio. Binarized neural networks: Training deep neural networks with weights and activations constrained to -1. arXiv preprint arXiv:1602.02830, 2016.
Misha Denil, Babak Shakibi, Laurent Dinh, Marc' Aurelio Ranzato, and Nando de Freitas. Predicting parameters in deep learning. In Advances in Neural Information Processing Systems, 2013.
Timur Garipov, Dmitry Podoprikhin, Alexander Novikov, and Dmitry P. Vetrov. Ultimate tensoriza- tion: compressing convolutional and FC layers alike. CoRR, abs/1611 1.03214, 2016.
Philipp Gysel, Jon Pimentel, Mohammad Motamedi, and Soheil Ghiasi. Ristretto: A framework for empirical study of resource-efficient inference in convolutional neural networks. IEEE Transactions on Neural Networks and Learning Systems, 29(11):5784 5789, 2018
Marawan Gamal Abdel Hameed, Marzieh S. Tahaei, Ali Mosleh, and Vahid Partovi Nia. Convolu- tional neural network compression through generalized Kronecker product decomposition. In AAAI Conference on Artificial Intelligence, 2022.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruming, trained quantization and Huffman coding. arXiv preprint arXiv:1510.001 2015a
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. Advances in Neural Information Processing Systems, 28, 2015b.
Richard A Harshman al. Foundations of the parafac procedure: Models and conditions for an" explanatory" multimodal factor analysis. 1970.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. pp. 770-778, 2016.
Yang He, Guoliang Kang, Xuanyi Dong, Yanwei Fu, and Yi Yang. Soft filter pruning for accelerating deep convolutional neural networks. arXiv preprint arXiv: 1808. 2018.
Yang He, Yuhang Ding, Ping Liu, Linchao Zhu, Hanwang Zhang, and Yi Yang. Learning filter pruning criteria for deep convolutional neural networks acceleration. In JEEE/CVF Conference on Computer Vision and Patern Recognition (CVPR), 2020.
10

---

Under review as a conference paper at ICLR 2023
Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural networks. In IEEE International Conference on Computer Vision, pp. 1389-199,, 2017.
Byeongho Heo, Minsik Lee, Sangdoo Yun, and Jin Young Choi. Knowledge distillation with adversarial samples supporting decision boundary. In AAAI Conference on Artificial Intelligence, pp. 3771-3778, 2019.
Geoffrey E. Hinton, Oriol Vinyals, and Jeffrey Dean. Distilling the knowledge in a neural network. CoRR, 0as//5533.25333 2015.
David Hong, Tamara G Kolda, and Jed A Duersch. Generalized canonical polyadic tensor decompo- sition. SIAM Review, 62(1):133-163 2020.
Andrew Howard, Mark Sandler, Grace Chu, Liang-Chich Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang. Vijay Vasudevan, al. Searching for MobileNetV3. In IEEF/CVF International Conference on Computer Vision, pp. 1314-1324, 2019.
Jia- Bin Huang, Abhishek Singh, and Narendra Ahuja. Single image super-resolution from transformed self-exemplars. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2015.
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran HI- Yaniv,,v, and Yoshua Bengio. Quantized neural networks: Training neural networks with low precision weights and activations. The Journal of Machine Learning Research, 18(1):68696885 2017.
Forrest N landola. Song Han, Matthew W Moskewicz, Khalid Ashraf, William Dally, and Kurt Keutzer. Squeezenet: Alexnet-level accuracy with 50x fewer parameters and < 0.5 MB model size. arXiv preprint arXiv: wtt.:::62200000 070600 2016.
Yerlan Idelbayev and Miguel A. Carreira-Perpinan. Low-rank compression of neural nets: Learning the rank of each layer. In /EEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko. Quantization and training of neural networks for efficient integer- arithmetic-only inference. IEEE Conference on Computer Vision and Pattern Recognition, pp. 2704-2713, 2018.
Max Jaderberg, Andrea Vedaldi, and Andrew Zisserman. Speeding up convolutional neural networks with low rank expansions. arXiv preprint arXiv: 1405.3:60, 2014.
Yong-Deok Kim, Eunhyeok Park, Sungjoo Yoo, Taelim Choi, Lu Yang, and Dongjun Shin. Com- pression of deep convolutional neural networks for fast and low power mobile applications. arXiv preprint 1rXiv:1511.06530 2015.
Yong-Deok Kim, Eunhyeok Park, Sungjoo Yoo. Taelim Choi, Lu Yang, and Dongjun Shin. Com- pression of deep convolutional neural networks for fast and low power mobile applications. In International Conference Learning Representations, 2016.
Filippos Kokkinos and Stamatios Lefkimmiatis. Deep image demosaicking using cascade of convolutional residual denoising networks. In European Conference on Computer Vision (ECCV), pp. 303-319, 2018.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. ImageNet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems, pp. 1106-1114, 2012.
Vadim Lebedev, Yaroslav Ganin, Maksim Rakhuba, Ivan V. Oseledets, and Victor S. Lempitsky. Speeding up convolutional neural networks using fine-tuned CP-decomposition. In International Conference Learning Representations, 2015.
11

---

Under review as a conference paper at ICLR 2023
Christian Ledig, Lucas Theis, Ferenc Huszár, Jose Caballero, Andrew Cunningham, Alejandro Acosta, Andrew Aitken, Alykhan Tejani, Johannes Totz, Zehan Wang, et al. Photo-realistic single image super-resolution using a generative adversarial network. In IEEE Conference Computer Vision and Pattern Recognition, pp. 1690,, 2017.
Fengfu Li, Bo Zhang, and Bin Liu. Ternryy weight networks. arXiv preprint arXiv:1605.04711 2016.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient ConvNets. In International Conference on Learning Representations, 2017.
Yawei Li, Shuhang Gu, Lue Van Gool, and Radu Timofte. Learning filter basis for convolutional neural network compression. In IEEE International Conference on Computer Vision, 2019.
Lucas Liehenwein, Cenk Baykal, Harry Lang, Dan Feldman, and Daniela Rus. Provable filter pruning for efficient neural networks. In International Conference on Learning Representations, 2020.
Lucas Liebenwein, Alaa Maalouf, Dan Feldman, and Daniela Rus. Compressing neural networks: Towards determining the optimal layer-wise decomposition. In Advances in Neural Information Processing Systems, 2021.
Baoyuan Liu, Min Wang, Hassan Foroosh, Marshall Tappen, and Marianna Pensky. Sparse con- volutional neural networks. IEEE Conference on Computer Vision and Pattern Recognition, pp. 806-814, 2015.
Zechun Liu, Haoyuan Mu. Xiangyu Zhang, Zichao Guo, Xin Yang, Kwang-Ting Cheng, and Jian Sun. Metapruning: Meta learning for automatic neural network channel pruning. In IEEE International Conference on Computer Vision, pp. 3296-3305, 2019.
Christos Louizos, Matthias Reisser, Tijmen Blankevoort, Efstratios Gavves, and Max Welling, Relaxed quantization for discretized neural networks. arXiv preprint arXiv: 181000888 2018.
Jian-Hao Luo, Jianxin Wu, and Weiyao Lin. ThiNet: A filter level pruming method for deep neural network compression. In IEEE International Conference on Computer Vision, pp. 5058-5066, 2017.
D. Martin, C. Fowlkes, D. Tal, and J. Malik. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In IEEE International Conference on Computer Vision, volume 2, pp. 416-423 vol.2, 2001.
Beyed-Iman Mirzadeh, Mehrdad Farajtabar, Ang Li, Nir Levine, Akihiro Matsukawa, and Hassan Ghasemzadeh. Improved knowledge distillation via teacher assistant. In AAAI Conference on Artificial Intelligence, pp. 5191-5198, 2020.
Alexander Novikov, Dmitrii Podoprikhin, Anton Osokin, and Dmitry P Vetrov. Tensorizing neural networks. In C. Cortes, Lawrence, Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, 2015.
Ivan Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33(5):
2295-2317, 2011.
Anh-Huy Phan, Konstantin Sobolev, Konstantin Sozykin, Dmitry Ermilov, Julia Gusak, Petr Tichavský, Valeriy Glukhov, Ivan Oseledets, and Andrzej Cichocki. Stable low-rank tensor de- composition for compression convolutional neural network. European Conference on Computer Vision, pp. 522 539. Springer, 2020.
Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. Xnor-net: ImageNet classification using binary convolutional neural networks. In European Conference Computer Vision, pp. 525 242- Springer. 2016.
Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster R-CNN: Towards real-time object detection with region proposal networks. Advances in Neural Information Processing Systems, 28: 91-99, 2015.
12

---

Under review as a conference paper at ICLR 2023
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chich Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. In IEEE Conference on Computer Vision and Pattem Recognition, pp. 4510 4520000-00222 2018.
Christian Schuler, Michael Hirsch, Stefan Harmeling, and Bernhard Schölkopf. Learning to deblur. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(7):133-1451, 2015.
Mingxing Tan and Quoe Le. EfficientNet: Rethinking model scaling for convolutional neural networks. In International Conference on Machine Learning, pp. 6105-6114. PMLR, 2019.
Wei Tang, Gang Hua, and Liang Wang. How to train a compact binary neural network with high accuracy? In AAAI Conference on Artificial Intelligence, 2017.
Urmish Thakker, Jesse Beu, Dibakar Gope, Chu Zhou, Igor Fedorov, Ganesh Dasika, and Matthew Mattina. Compressing RNNs for IoT devices by 15-38x using Kronecker products. arXiv preprint arXiv:1906.0220 02876, 2019.
Ledyard R Tucker. Implications of factor analysis of three-way way matrices for measurement of change. Problems in Measuring Change, 15(122-137):3, 1963.
Stefan Uhlich, Lukas Mauch, Fabien Cardinaux, Kazuki Yoshiyama, Javier Alonso Garcia, Stephen Tiedemann, Thomas Kemp, and Akira Nakamura. Mixed precision DNNs: All you need is good parametrization. In International Conference on Learning Representations, 2019.
Wenqi Wang, Vaneet Aggarwal, and Shuchin Aeron. Efficient low rank tensor ring completion. In IEEE International Conference on Computer Vision, pp. 5697-5705, 2017.
Wenqi Wang. Yifan Sun, Brian Eriksson, Wenlin Wang, and Vaneet Aggarwal. Wide compression: Tensor ring nets. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018a.
Xintao Wang, Ke Yu, Shixiang Wu, Jinjin Gu, Yihao Liu, Chao Dong, Yu Qiao, and Chen Change Loy. ESRGAN: Enhanced super-resolution generative adversarial networks. In European Conference on European Conference Vision (ECCV), pp. 0-0, 2018b.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. Advances in Neural Information Processing Systems, 29, 2016.
Yingzhen Yang, Jiahui Yu, Nebojsa Jojic, Jun Huan, and Thomas S. Huang. Fsnet: Compression of deep convolutional neural networks by filter summary. In International Conference on Learning Representations, 2020.
Miao Yin, Yang Sui, Siyu Liao, and Bo Yuan. Towards efficient tensor decomposition- DNN model compression with optimization framework. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 10674-10683, June 2021.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXiv: 00 146, 2016.
Roman Zeyde, Michael Elad, and Matan Protter. On single image scale-up using sparse- representations. In Jean-Daniel Boissonnat, Patrick Chenin, Albert Cohen, Christian Gout, Tom Lyche, Marie-Laurence Mazure, and Larry Schumaker (eds.), Curves and Surfaces, pp. 711-730, 2012.
Dongqing Zhang, Jiaolong Yang. Dongqiangzi Ye, and Gang Hua. LQ-nets: Learned quantization for highly accurate and compact deep neural networks. In European Conference on Computer Vision (ECCV), pp. 365-382, 2018a.
Tianyun Zhang, Shaokai Ye, Kaiqi Zhang, Jian Tang, Wujie Wen, Makan Fardad, and Yanzhi Wang. systematic DNN weight pruning framework using alternating direction method of multipliers. In European Conference on Computer Vision (ECCV), pp. 184-199, 2018b.
Xiangyu Zhang, Jianhua Zou, Kaiming He, and Jian Sun. Accelerating very deep convolutional networks for classification and detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(10)) 2016.
13

---

Under review as a conference paper at ICLR 2023
Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. ShuffleNet: An extremely efficient convolutional neural network for mobile devices. In IEEE Conference on Computer Vision and Pattem Recognition, pp. 6848-6856 2018c.
Yu-Bang Zheng, Ting-Zhu Huang, Xi-Le Zhao, Qibin Zhao, and Tai-Xiang Jiang. Fully-connected tensor network decomposition and its application to higher-order tensor completion. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 11071-11078, 2021.
Hao Zhou, Jose M Alvarez, and Fatih Porikli. Less is more: Towards compact CNNs. In European Conference on Computer Vision, pp. 662-677, 2016.
Shuchang Zhou, Jia-Nan Wu, Yuxin Wu, and Xinyu Zhou. Exploiting local structures with the kronecker layer in convolutional networks. arXiv preprint arXiv:1512.09190 2015.
Chenzhuo Zhu, Song Han, Huizi Mao, and William J Dally. Trained ternary quantization. arXiv preprint 1rXiv:1612.0106 2016.
Zhuangwei Zhuang, Mingkui Tan, Bohan Zhuang, Jing Liu, Yong Guo, Qingyao Wu, Junzhou Huang. and Jinhui Zhu. Diserimination-wware channel pruning for deep neural networks. Advances in Neural Information Processing Systems, 31, 2018.
APPENDIX
SEQUENCE OF KRONECKER PRODUCTS
The Kronecker product between sequence of factor tensors is given by
(A (1) 8 ... e (9)
(15)
1100..08 (5)
where
Li=1
Jn
(0)
!
mod an
(S)
k: = S
bn Ei
An
otherwise,
(16)
+1
and (A)
(k)
RR
xa
ALTERNATIVE EXPANSION DIRECTIONS OF SEKRON
The proposed SeKron structure represents given tensor W E IR X Kronecker products as follows:
Xue using a sequence of
R2 Σ
Rs-1 Σ TS 1=1
W
Σ r1=1 r2=1
2 F1
8
(S-1) A 8 A()
Ar 1'
revisited)
While this decomposition structure is obtained by recursively finding the Kronecker decomposition of the right-most tensor, many alternative sequential Kronecker structures be obtained illustrated in Figure 4 However, such alternative structures do not fall within our SeKron framework as they cannot make of our convolution algorithm (Algorithm)
C THEOREM PROOFS
Theorem 1 (Tensor Decomposition using Sequence of Kronecker Products). Any tensor W e
IR wh X XWN can be represented by sequence of Kronecker products between E IN factors:
R
R
Re-1
W
Σ
(2) Fira
A
(5-1) ( @ (S)
(4)
T8-1
riml
r8-1=1
where R2 IN and (k) IR
Rí X... Rexa xx
14

---

Under review as a conference paper at ICLR 2023
(G)0)
A
Σ
1000 A
(6)0) (1)) n. 2
An
E E
Σ
(410) @ All
$ (0009)
Figure 4: Illustration of alternative expansion directions using sequences of Kronecker products. SeKron structures are those which are leftmost on each level of the tree. Each node is obtained through the decomposition of a single tensor present in its parent node.
Proof.
First, we define intermediate tensors
RE+1
RE42
Rs-1
B (k)
Prirre
(I+1)
A
(k++) Tr
Σ
A
1)
revisited)
Th+11
Th++2
Then the reconstruction error can written as
|
R Σ
A m
&
B
(17)
=2=1
where (!)) is the initial tensor being decomposed. As described in Section 3.2 operations
using reshaping
(K) P
MWT (R)
d
B
(b)
)), Pginn
revisited)
(k) ar1-.k
VEC(UNFOLD A (k)
ATT dz (N)
}),
br
VEC (k) F
revisited)
that preserve the sum of squares allows equivalently write the reconstruction error
(k) Fi
(k) Tg
(A)T Driao
(18)
Now consider the singular value decomposition of matrix W/ r and let u Vir.., denote its left and right singular vectors, respectively (with the right singular vector scaled according to its corresponding singlar value). Set a uys and define and define error terms
(k)
(k)
(k) 0
Vr b Gr
(1)
(k)
(K)
110(/))
(19)
15

---

Under review as a conference paper at ICLR 2023
Expanding out equation
18
reveals its recursive form
Rx
2
Ra
2
W(
a
(R)
b
b
(K)T
W
71-1
ary
(k)
(v
Pt
p T
8
(20)
r==1
F
-==1
R2
Ri
(
P1
arporry V
a P
(21)
Ph
m
R2
R
W (k)
(k)T
(k)
(k)
P1--P-11
a
+
Br
(22)
r==1
r==1
2
R
W (k)
11-
appork
(k)
Vri
(K)T
+
(b)
Cri.Tr
(R)
(23)
===1
R
Σ
rg
(Wil))
(---
+
(1))
(2)
(24)
r== +1
Rg
o
(w
(
+
d(kk
Veruire
(2) brs
(25)
Ty= +1
Fh
where d(k)
E N is the number of dimensions of vector ar and Rg is the rank of matrix
(k)
((()
P1 rx (W ( denotes the rx singular value of tensor Wilh 1--1" By reshaping
vectors V b to matrices according to
(8)
S
S
)
V (6) P1 MAT
UNFOLD
VEC-I
(k) ViL
II amk++
d
II smb++2
d
(1)
(26)
S
g
(K) B =
MAT
UNFOLD
VFC
b
(b)
II +=
(
II (
(27)
S
s=k-2
where (*) = (a
describes the dimensions of the 5h factor, we can re-write equation
25
N
as
R (k)
2
Σ
(W(k)
(k)
V
(R)
b
(b)
(28)
++=0++1
R
Re
Σ
o W
(k)
Σ
(kk
(k)
B
(k)
(29)
P
Bl
R
2
(W(A) Pimiry
) +
((M)
(k) Vi
a
(k+1) an
(k+1)T bri-
(30)
T==1
Tkii=l
The last line reveals the recursive nature of the formula (compare with equation 20 Unrolling the recursive formula for k I,..., 1, by setting w(++1) formula for the reconstruction error:
((k)
Virre leads to the following
m Σ
Erenn D) =
of of (W()) + (())
Σ
(2 ri
+
+1 +1
R1+1
Rsg
Rgg
+ () ... (-
Σ
Σ
0
(W
(S-1)
Pjorrg a) (31)
r1,72....
rs 1 R--1t1
16

---

Under review as a conference paper at ICLR 2023
where (R1. ..... Rg-1) contains the rank values, D d contains the Kronecker factor shapes and is referred to as the Dr-SeKron approximation error (note that the dependency of intermediate
matrices (A) P Kronecker factor shapes D is implied). Selecting R; R, vi in equation 31 results in zero reconstruction error.
Theorem 2. The factorization structure imposed by CP, Tucker, TT and TR when decomposing given tensor W "R X=N can be achieved using SeKron.
Proof. The SeKron decomposition tensor W is given by
R
W ii
Σ
(S) rs 19(9).. (9)
(32)
where A Bix
x- x--xxxx- RRxxxxxaaa
x...x and
in
1=
In
(t)
an
mod an
(8)
S,
jb
T6 revisited)
otherwise,
The CP decomposition of tensor W in scalar form is
R(CP)
W iimi
(CP1)
A
(CPx) viy
(33)
where (CPx)) (e xus Configuring the SeKron decomposition in equation 32 such that
S = N; R1 = R(CP); R2, R2,.... RN and (n) W/ for = -, 1,..., N leads to the equivalent
form
Windi
ri-l--1
r.1-
(34)
n==1
The Tucker decomposition of tensor W is given by
R
W i
9
(Ti)
A (Tx) SyEN
(35)
:I....
where G E IR*t
R x R
and A (Tx) E IR x R The SeKron decomposition of tensor W, with
S N + Ry R
and an (n)
Wn for n 11 I...., yields
R
R
W Vi
(1)
A (N)
A
(N+1) 1
(36)
which is equivalent to equation 35 in the special case where there are nullity constraints on some elements in the Kronecker factors, such that for k = .....N
(k) mh 1.. 1ic1..1 = when rj E fo E x R, # R,T) j= k (37)
for any choice of RTTx) E Ex x R R. The Tensor Ring (TR) decomposition of W is given
by
(2(TR) (T
W
(RR1)
A (Ry)
(38)
INT87841
where A (TR,)
As the Tensor Train decomposition can be viewed special of the Tensor Ring decomposition (with R(IR) R(TR) 1), it suffices to
"R x (T
m and
R
(TR)
(TR)
17

---

Under review as a conference paper at ICLR 2023
show that SeKron generalizes Tensor Ring. The SeKron decomposition of tensor W, with S = N+1; ( for
Rs
1, N and an (n+1) Wn for ,,...;A. leads to
R
W Wx
Σ
(N+1) Tx+1 1iy.
(39)
ri 1rrhh111
F PIoOP
which is equivalent to equation 38 in the special case where some elements in the Kronecker factors are constrained, such that all elements in tensor A are constrained to one and
(8) Fy Looli lig 1ool
Vry E ENEN
H (R)) + Rg (T)
(40)
for
j= 1, k - 2 k k= 2..,..,
(41)
2, 2.....,
k N
for any choice of R
(TR)) ( )
Theorem 3 (Linear Mappings with Sequences of Kronecker Products). Any linear mapping using given tensor W can be written directly in terms of its Kronecker factors A(k IR Ri x- Ry xa
(k) xxxxay That is:
(k)
Ry....e
W Win X Ris ii teN
Σ
AA
A()) P1-- 18 1.)...991 X f( (GN)+aN
ridh r1 ...
where j(b) E IN is a function of input indices (see Appendix A and f(in) = - 1k=1 I 1
(k)
Proof. First we bring out the summations in the SeKron representaion of W
R
Ra
Rs.
W
Σ
8
P172
11"
(S-1)
@
(9)
(9) Arirss
revisted)
such that
Rip Rs
W =
(1) ② ... @
(1)
(42)
Then, using the scalar form definition of sequences of kronecker products in equation 16
in
Σ 1= Jn 1+
(t)
an mod a. (9)
k=S S,
1
16 revisited)
otherwise,
allows us re-write equation 42
scalar form as
R Σ
A (5)
W i
(43)
F1"mg=1
As the (000 terms decompose in into an integer weighted sum, we can recover in using
5
5
in = f(j)) A
(k)
II
(44)
k=1
1=k+1
where j. = (1 (5)). Thus, we can write
X iuta X fo.) fix)))
(45)
Finally, combining equations equation 43 and equation 45 leads
By.... R.
W Wipwdy Ris tn. AN+EN
(S)
(8) X f(.))..." f(N)
ri 1) .....
18

---

Under review as a conference paper at ICLR 2023
Theorem 4. (Universal approximation via shallow SeKron networks) Any shallow SeKron factorized neural network f(() with I--Lipschitz activation function o, dense in the class of continuous functions (XX) for any compact subset X of IR.
Proof. Let f denote a shallow neural network, and f E C(X). Then,
| - p(0) 1 - xx
[(0) - (a)
dp
(46)
f(x) (F()) - f(x)
= /
-f(x)
du
(47)
2
+ / ((x)) (()
dp
(48)
+ / (1()) ((x)
((6))-Po -c) du
(49)
According Hornik (1991), equation 47 dense in C(X); therefore, suffices to show that equation 48 is bounded as well.
1 (1L) - (()(()) -
2 dp du=/ /,
aaaaaWlk W (TT((Wx) w (a(()))))))) ) dp
(50)
S S [||w]]
ScKoo (,r,D)
(51)
where denotes the Dr-SeKron approximation enror as in equation 31 with matrix D and vector describing the shapes of the Kronecker factors the ranks used in the SeKron decomposition of W respectively.
D IMPLEMENTATION DETAILS
In all of our experiments we use 4 NVIDIA Tesla V100 SXM2 32 GB GPUs during training and evaluate run time on single core of Intel(R) Xeon(R) Gold 6148 CPU @ 2.40GHz.
D.1 IMAGENET EXPERIMENTS
We train all models using stochastic gradient descent for 100 epochs using batch size of 256. The learning rate is initially set to 0.1 and reduced by a factor 10x at epochs number 30, 60 and 90. We also 0.0001 weight decay.
D.2 CIFAR- 10 EXPERIMENTS
We train all models using using stochastic gradient descent for 200 epochs using batch size of 128. The learning rate is initially set to 0. and is reduced by factor 5x at epochs number 60, 120 and 160. We use nestrov momentum to 0.9 and weight decay set to 0.0005.
D.3 DIV2K
We train all models using using the ADAM optimizer for 300 epochs using batch size of 16. The optimizer's learning rate to 0.0001 and 31, 33 are set 0.9, 0.999 respectively.
19


Reviews:
[{"review_id": "ZFlZnjFHq8", "reviewer": "Reviewer_Qck6", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new tensor decomposition method for neural network compression. The main idea is to devise a decomposition structure that is composed of a sequence of Kronecker products, which generalizes most of the well-known tensor decompositions. Existing decompositions mostly rely on specific structures (of decomposition), which might not be best suited for network compression purposes. The method itself is quite simple (applying successive greedy binary Kronecker decompositions), which is a good point for the main goal. Experiments show that the proposed method achieves state-of-the-art performance for CIFAR-10, ImageNet, and super-resolution experiments.", "summary_of_the_review": "I believe that the authors propose a flexible decomposition structure that is efficient for neural-net compression. SeKron might not add better characteristics with respect to the traditional tensor decomposition context, but it is surely more efficient for network compression. The previous criticism regarding the position of SeKron in the existing tensor decomposition literature is still not clearly resolved in this version, I suggest toning down and limiting the scope of discussion.\n\n[After rebuttal] I'm satisfied with the answers and raise my score to 8. The authors have appropriately revised the paper, i.e., toned down regarding the generality of SeKron, focusing more on the paper's main focus, i.e., neural net compression.", "strength_and_weaknesses": "The main idea is quite simple and intuitive (i.e., representing any possible form of tensor products with a series of Kronecker products), but it is definitely a worthy contribution. What the authors have proposed is basically a general tensor decomposition structure that is easy to manipulate. I was personally surprised by the fact that nobody has attempted this (which now seems to be a natural choice for network compression) until this moment, and I also think that this reflects the importance of this contribution. What existing tensor decompositions have focused on was mostly things like having good algebraic properties or finding the best approximation with respect to some criteria. On the other hand, the proposed method might not be particularly better (or might be even worse in some aspects) for the above properties, but it is definitely more flexible in determining the shapes of the factors. For network compression purposes, this can be a better choice.\n\nIn fact, I was one of the reviewers of this paper in another venue. I see that some of my previous concerns have been addressed in this paper. I asked about the binary Kronecker decomposition in the experimental comparison, and I see that it has been added in this version. However, the \"direction of expansion\" in successive SVD-based approximation has not been addressed in this version. (In the paper, the successive SVD approximation is performed in one direction, i.e., from 1 to S. But this is not the only direction possible.) I understand that investigating all the possible directions can be difficult, but I suggest adding this discussion with a few other example directions, which can motivate readers to try other possible combinations.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "PhA-74znqc", "reviewer": "Reviewer_f4rp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focuses on CNN compression using low-rank factorizations. In particular, the authors propose a new tensor decomposition called SeKron, which generalizes traditional TT, TR, CP and Tucker decomposition. The authors establish a SVD-based algorithm to decompose a given tensor into the SeKron format. Due to the special structure of SeKron, convolutional operations can be conducted without reconstructing the full tensor, which saves memory and FLOPs when doing inference in CNNs.\n\nThe authors conduct experiments on WideResNet/ResNet for classification and SRResNet/EDSR for super-resolution. They compare with several decomposition and pruning methods. The proposed model shows similar compression rates, but achieves better performance.", "summary_of_the_review": "This paper proposes a new tensor decomposition method which can be used for CNN compression. The proposed method is flexible, which is potential for some future applications. However, the intuition and advantage is not clear to me currently. I would like to raise my score if the authors could address my concerns.", "strength_and_weaknesses": "**Strengths**\n\n1. The authors propose a new tensor decomposition method based on SVD, which generalizes CP, Tucker and TT/TR.\n2. The authors show how to parameterize kernels in CNN by the proposed SeKron format. The proposed method allows convolutional operations by operating each core tensors, without computing the full tensor. Therefore, the proposed method is efficient to do CNN inference.\n\n\n**Weaknesses and Questions**\n\n1. I do not catch how the authors do the compression. Do they use end-to-end training for the given SeKron format or just apply Algorithm 1 on pretrained CNNs? Is there any finetuning after the decomposition?\nWhat devices do the authors use in experiments? Why do the authors only list CPU time? What about FLOPs and GPU time for SeKron and baselines?\n2. The authors consider addressing the architecture limitations of tensor decomposition by proposing the flexible SeKron. However, there exists some work to tackle the problem by exploring many potential tensor networks. I think a good reference is [1], since it also focuses on the CNN compression by using genetic algorithms to search tensor network structures. Moreover, [2] proposes a permutation and rank search for TR format, which can be also applied if the CNN is not trained end-to-end.\n3. As SeKron is developed based on the sum of Kronecker structure proposed by Hammed et al. (2022), can the authors provide more intuitions and advantages about using this sequence of sum of Kronecker in SeKron? Moreover, why did not the authors compare SeKron with the sum of Kronecker in experiments? I think it is an important baseline. Currently, the advantages of SeKron are not clear to me. \n4. If I understand correctly, in Algorithm 2, the contraction or projection must be done sequentially for $i= S, \\dots, 1$. Why do the authors say the projection can be performed independently? Moreover, will this sequential procedure increase computational time compared with traditional convolutional layers which are highly parallelized?\n\n[1]. Hayashi, K., Yamaguchi, T., Sugawara, Y., & Maeda, S. I. (2019). Exploring unexplored tensor network decompositions for convolutional neural networks. Advances in Neural Information Processing Systems, 32.\n\n[2]. Li, C., Zeng, J., Tao, Z., & Zhao, Q. (2022, June). Permutation Search of Tensor Network Structures via Local Sampling. In International Conference on Machine Learning (pp. 13106-13124). PMLR.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EWPVZEpiZG", "reviewer": "Reviewer_Pd7U", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers compression of CNN weight tensors by using a kind of tensor decomposition. The purpose of this is to reduce the number of parameters and speed up the convolution computation.\n\nIt is quite clear that the authors have compressed various white spaces in the paper (e.g., around equations, in captions, around floats). This, by itself, is grounds for rejection. In addition to this, the paper is confusing in many places, and key weaknesses of the approach aren't discussed.\n\n### Update after rebuttal ###\n\nI leave my score as it is due, to the following reasons:\n- The original submission violated the page limit due to substantial alterations of white spaces.\n- The paper doesn't sufficiently address the limitations with how dimensions of the factors have to be chosen. For a method like this to be useful, I think it should be relatively insensitive to the data tensor dimensions. For example, if the tensor to be decomposed is of size $1024 \\times 1024 \\times 1024$, then SeKron has a great deal of flexibility. In particular, since $1024=2^{10}$, the number of factors $S$ can be chosen to be anywhere from 1 to 10 and the sizes $a_1^{(k)}, a_2^{(k)}, a_3^{(k)}$ for $k=1,\\ldots,S$ can satisfy the requirement $\\prod_{k=1}^S a_i^{(k)} = 1024$ in many different ways. But if this is changed just slightly to a tensor of size $1021 \\times 1021 \\times 1021$, then all of a sudden there is no flexibility at all. In particular, since 1021 is a prime number, you have to choose $S=1$ and $a_i^{(1)} = 1021$ for each $i =1,2,3$. This sensitivity in the behavior of the model to the input tensor size is, in my opinion, a substantial weakness. This could potentially be alleviated with appropriate zero padding. But this isn't done in the paper, and the authors don't even acknowledge the weakness of their current model. ", "summary_of_the_review": "The authors have reduced white spaces of the paper, effectively violating the 9-page limit. In addition to this, there are issues with notation  that make the paper hard to follow. Important limitations haven't been discussed.  ", "strength_and_weaknesses": "--- Strengths ---\n\nS1. Sections 1-2 provide a nice introduction to the area. The overview in Section 2 is particularly good. I also appreciated the clear introduction to CNN layers at the start of Section 3.1.\n\n--- Weaknesses ---\n\nW1. The authors have clearly reduced whitespace throughout the paper; equations are crammed together, captions are too close to the figures. This by itself is grounds for rejection since it effectively violates the 9-page paper limit.\n\nW2. An important weakness that is not mentioned anywhere is that the factors $A^{(k)}$ in Eq (8) must have dimensions that factorize the dimensions of $W$. For example, they must satisfy $\\prod_{k=1}^S a_j^{(k)} = w_j$. So what is hailed as *greater flexibility* of the proposed model in the caption of Fig 1 is in fact a *limitation*. For example, if the dimensions of $W$ are prime numbers, then for each mode of $W$, only a single tensor $A^{(k)}$ can have a non-singleton dimension in that same mode. This may be fixable with appropriate zero padding, but this has to at least be discussed and highlighted in the paper.\n\nW3. The 2nd point in the list of contributions in Sec 1 claims that the paper provides a means of finding the *best approximation* in the proposed format. In fact, it is easy to see that this claim is likely to be false: The decomposition corresponds to a difficult non-convex optimization problem, and it is therefore unlikely that a simple algorithm with a finite number of steps could solve it optimally.\n\nW4. SeKron is claimed to generalize various other decompositions. But it is not clear that the proposed algorithm could ever reproduce those decompositions. For example, since there is no SVD-based algorithm for CP decomposition, I strongly suspect that the proposed algorithm (which is SVD-based) cannot recreate the decomposition that, say, an alternating least squares based approach for CP decomposition would achieve.\n\nW5. The paper is unclear and poor notation is used in multiple places. For examples:\n- Subscripts are sometimes used to denote indices (e.g., Eq (5)), sometimes to denote sequences of tensors (e.g., Eqs (7), (8)), and sometimes used to denote both at the same time (e.g., Thm 3, Eq (35))! This is very confusing.\n- It is unclear how Eq (7) follows from Eq (5). The confusing indices exacerbate this.\n- In Thm 1, $A^{(k)}$ are tensors, so it's unclear what you mean by \"$R_i$ are ranks of intermediate matrices\".\n- In Alg 1, you apply SVD to a 3-way tensors. This operation is not defined. If you mean batched SVD, you need to specify that.\n- The $W_{r_1 \\cdots r_{k-1}}^{(k)}$ tensors in Eq (10) haven't been defined.\n- The definition of Unfold below Eq (13) is ambiguous. Similarly, you say that Mat reformulates a tensor to a matrix, but list the output space as $R^{d_1 \\cdots d_N}$, i.e., indicating that the output is a vector.\n- Below Eq (15) you discuss \"projection\". This is not an appropriate term to use, since these aren't projections; projection is a term with a specific meaning in linear algebra.\n- In Eq (16), the $r_k$ indices appear on the right-hand side but not on the left-hand side.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject