IS ATTENTION BETTER THAN MATRIX DECOMPOSITION?
Year: 2021

Abstract:
As an essential ingredient of modern deep learning, attention mechanism, especially self-attention, plays a vital role in the global correlation discovery. However, is hand-crafted attention irreplaceable when modeling the global context? Our intriguing finding is that self-attention is not better than the matrix decomposition (MD) model developed 20 years ago regarding the performance and computational cost for encoding the long-distance dependencies. We model the global context issue as a low-rank completion problem and show that its optimization algorithms can help design global information blocks. This paper then proposes a series of Hamburgers, in which we employ the optimization algorithms for solving MDs to factorize the input representations into sub-matrices and reconstruct a low-rank embedding. Hamburgers with different MDs can perform favorably against the popular global context module self-attention when carefully coping with gradients back-propagated through MDs. Comprehensive experiments are conducted in the vision tasks where it is crucial to learn the global context, including semantic segmentation and image generation, demonstrating significant improvements over self-attention and its variants. Code is available.

heading: 1 INTRODUCTION
text: Since self-attention and transformer (Vaswani et al., 2017) showed significant advantages over recurrent neural networks and convolutional neural networks in capturing long-distance dependencies, attention has been widely adopted by computer vision (Wang et al., 2018; Zhang et al., 2019a) and natural language processing (Devlin et al., 2019) for global information mining. However, is hand-crafted attention irreplaceable when modeling the global context?
This paper focuses on a new approach to design global context modules. The key idea is, if we formulate the inductive bias like the global context into an objective function, the optimization algorithm to minimize the objective function can construct a computational graph, i.e., the architecture we need in the networks. We particularize this idea by developing a counterpart for the most representative global context module, self-attention. Considering extracting global information in the networks as finding a dictionary and the corresponding codes to capture the inherent correlation, we model the context discovery as low-rank completion of the input tensor and solve it via matrix decomposition. This paper then proposes a global correlation block, Hamburger, by employing matrix decomposition to factorize the learned representation into sub-matrices so as to recover the clean low-rank signal subspace. The iterative optimization algorithm to solve matrix decomposition defines the central computational graph, i.e., Hamburger’s architecture.
Our work takes advantage of the matrix decomposition models as the foundation of Hamburger, including Vector Quantization (VQ) (Gray & Neuhoff, 1998), Concept Decomposition (CD) (Dhillon & Modha, 2001), and Non-negative Matrix Factorization (NMF) (Lee & Seung, 1999). Additionally, instead of directly applying Back-Propagation Through Time (BPTT) algorithm (Werbos et al., 1990) to differentiate the iterative optimization, we adopt a truncated BPTT algorithm, i.e., one-step gradient, to back-propagate the gradient effectively. We illustrate the advantages of Hamburger in
∗Equal first authorship †Corresponding author
the fundamental vision tasks where global information has been proven crucial, including semantic segmentation and image generation. The experiments prove that optimization-designed Hamburger can perform competitively with state-of-the-art attention models when avoiding the unstable gradient back-propagated through the iterative computational graph of MD. Hamburger sets new state-ofthe-art records on the PASCAL VOC dataset (Everingham et al., 2010) and PASCAL Context dataset (Mottaghi et al., 2014) for semantic segmentation and surpasses existing attention modules for GANs in the large scale image generation on ImageNet (Deng et al., 2009).
The contributions of this paper are listed as follows:
• We show a white-box approach to design global information blocks, i.e., by turning the optimization algorithm that minimizes an objective function, in which modeling the global correlation is formulated as a low-rank completion problem, into the architecture. • We propose Hamburger, a light yet powerful global context module with O(n) complexity,
surpassing various attention modules on semantic segmentation and image generation. • We figure out that the main obstacle of applying MD in the networks is the unstable backward
gradient through its iterative optimization algorithm. As a pragmatic solution, the proposed one-step gradient facilitates the training of Hamburger with MDs.

heading: 2 METHODOLOGY

heading: 2.1 WARM UP
text: Since matrix decomposition is pivotal to the proposed Hamburger, we first review the idea of matrix decomposition. A common view is that matrix decomposition factorizes the observed matrix into a product of several sub-matrices, e.g., Singular Value Decomposition. However, a more illuminating perspective is that, by assuming the generation process, matrix decomposition acts as the inverse of the generation, disassembling the atoms that make up the complex data. From the reconstruction of the original matrices, matrix decomposition recovers the latent structure of observed data.
Suppose that the given data are arranged as the columns of a large matrix X = [x1, · · · ,xn] ∈ Rd×n. A general assumption is that there is a low-dimensional subspace, or a union of multiple subspaces hidden in X . That is, there exists a dictionary matrix D = [d1, · · · ,dr] ∈ Rd×r and corresponding codes C = [c1, · · · , cn] ∈ Rr×n that X can be expressed as
generation←−−−−−−−−− X = X̄ + E = DC + E,
−−−−−−−−−→ decomposition
(1)
where X̄ ∈ Rd×n is the output low-rank reconstruction, and E ∈ Rd×n is the noise matrix to be discarded. Here we assume that the recovered matrix X̄ has the low-rank property, such that
rank(X̄) ≤ min(rank(D), rank(C)) ≤ r min(d, n). (2) Different MDs can be derived by assuming structures to matrices D, C, and E (Kolda & Bader, 2009; Udell et al., 2016). MD is usually formulated as an objective with various constraints and then solved by optimization algorithms, with classic applications to image denoising (Wright et al., 2009; Lu et al., 2014), inpainting (Mairal et al., 2010), and feature extraction (Zhang et al., 2012).

heading: 2.2 PROPOSED METHOD
text: We focus on building global context modules for the networks without painstaking hand-crafted design. Before starting our discussion, we review the representative hand-designed context block self-attention pithily.
The attention mechanism aims at finding a group of concepts for further conscious reasoning from massive unconscious context (Xu et al., 2015; Bengio, 2017; Goyal et al., 2019). As a representative, self-attention (Vaswani et al., 2017) is proposed for learning long-range dependencies in machine translation,
Attention (Q,K,V ) = softmax ( QK>√
d
) V , (3)
where Q,K,V ∈ Rn×d are features projected by linear transformations from the input. Selfattention extracts global information via attending all tokens at a time rather than the typical one-byone processing of recurrent neural networks.
Though self-attention and its variants achieved great success, researchers are confronted with (1) developing new global context modules based on self-attention, typically via hand-crafted engineering, and (2) explaining why current attention models work. This paper bypasses both issues and finds a method to easily design global context modules via a well-defined white-box toolkit. We try to formulate the human inductive bias, like the global context, as an objective function and use the optimization algorithm to solve such a problem to design the module’s architecture. The optimization algorithm creates a computational graph, takes some input, and finally outputs the solution. We apply the computational graph of optimization algorithms for the central part of our context module.
Based on this approach, we need to model the networks’ global information issue as an optimization problem. Take the convolutional neural networks (CNN) as an example for further discussion. The networks output a tensor X ∈ RC×H×W after we feed into an image. Since the tensor can be seen as a set of HW C-dimensional hyper-pixels, we unfold the tensor into a matrix X ∈ RC×HW . When the module learns the long-range dependencies or the global context, the hidden assumption is that the hyper-pixels are inherently correlated. For the sake of simplicity, we assume that hyper-pixels are linearly dependent, which means that each hyper-pixel in X can be expressed as the linear combination of bases whose elements are typically much less than HW . In the ideal situation, the global information hidden in X can be low-rank. However, due to vanilla CNN’s poor ability to model the global context (Wang et al., 2018; Zhang et al., 2019a), the learned X is usually corrupted with redundant information or incompleteness. The above analysis suggests a potential method to model the global context, i.e., by completing the low-rank part X̄ in the unfolded matrix X and discarding the noise part E, using the classic matrix decomposition models described in Eq. (1), which filters out the redundancy and incompleteness at the same time. We thus model learning the global context as a low-rank completion problem with matrix decomposition as its solution. Using the notion of Sec. 2.1, the general objective function of matrix decomposition is
min D,C L(X,DC) +R1(D) +R2(C) (4)
where L is the reconstruction loss,R1 andR2 are regularization terms for the dictionary D and the codes C. Denote the optimization algorithm to minimize Eq. (4) asM.M is the core architecture we deploy in our global context module. To help readers further understand this modeling, We also provide a more intuitive illustration in Appendix G.
In the later sections, we introduce our global context block, Hamburger, and then discuss detailed MD models and optimization algorithms forM. Finally, we handle the gradient issue for back-propagation through matrix decomposition.

heading: 2.2.1 HAMBURGER
text: Hamburger consists of one slice of “ham” (matrix decomposition) and two slices of “bread” (linear transformation). As the name implies, Hamburger first maps the input Z ∈ Rdz×n into feature space with a linear transformation Wl ∈ Rd×dz , namely “lower bread”, then uses matrix decomposition M to solve a low-rank signal subspace, corresponding to the “ham”, and finally transforms extracted signals into the output with another linear transformation Wu ∈ Rdz×d, called “upper bread”,
H(Z) = WuM(WlZ), (5)
where M is matrix decomposition to recover the clear latent structure, functioning as a global nonlinearity. Detailed architectures ofM, i.e., optimization algorithms to factorize X , are discussed in Sec. 2.2.2. Fig. 1 describes the architecture of Hamburger, where it collaborates with the networks via Batch Normalization (BN) (Ioffe & Szegedy, 2015), a skip connection, and finally outputs Y ,
Y = Z + BN(H(Z)). (6)

heading: 2.2.2 HAMS
text: This section describes the structure of “ham”, i.e.,M in Eq. (5). As discussed in the previous section, by formulating the global information discovery as an optimization problem of MD, algorithms to solve MD naturally composeM.M takes the output of “lower bread” as its input and computes a low-rank reconstruction as its output, denoted as X and X̄ , respectively.
M(X) = X̄ = DC. (7) We investigate two MD models forM, Vector Quantization (VQ), and Non-negative Matrix Factorization (NMF) to solve D and C and reconstruct X̄ , while leaving Concept Decomposition (CD) to Appendix B. The selected MD models are introduced briefly because we endeavor to illustrate the importance of the low-rank inductive bias and the optimization-driven designing method for global context modules rather than any specific MD models. It is preferred to abstract the MD part as a whole, i.e.,M in the context of this paper, and focus on how Hamburger can show the superiority in its entirety.
Vector Quantization Vector Quantization (VQ) (Gray & Neuhoff, 1998), a classic data compression algorithm, can be formulated as an optimization problem in term of matrix decomposition:
min D,C ‖X −DC‖F s.t. ci ∈ {e1, e2, · · · , er}, (8)
where ei is the canonical basis vector, ei = [0, · · · , 1, · · · , 0]> ith . The solution to minimize the objective in Eq. (8) is K-means (Gray & Neuhoff, 1998). However, to ensure that VQ is differentiable, we replace the hard arg min and Euclidean distance with softmax and cosine similarity, leading to Alg. 1, where cosine(D,X) is a similarity matrix whose entries satisfy cosine(D,X)ij = d>i xj ‖d‖‖x‖ , and softmax is applied column-wise and T is the temperature. Further we can obtain a hard assignment by a one-hot vector when T → 0.
Algorithm 1 Ham: Soft VQ Input X . Initialize D, C. for k from 1 to K do C ← softmax( 1T cosine(D,X)) D ←XC>diag(C1n)−1
end for Output X̄ = DC.
Algorithm 2 Ham: NMF with MU Input X . Initialize non-negative D, C for k from 1 to K do Cij ← Cij (D >X)ij (D>DC)ij
Dij ←Dij (XC >)ij
(DCC>)ij
end for Output X̄ = DC.
Non-negative Matrix Factorization If we impose non-negative constraints on the dictionary D and the codes C, it leads to Non-negative Matrix Factorization (NMF) (Lee & Seung, 1999):
min D,C ‖X −DC‖F s.t.Dij ≥ 0,Cjk ≥ 0. (9)
To satisfy the non-negative constraints, we add a ReLU non-linearity before putting X into NMF. We apply the Multiplicative Update (MU) rules (Lee & Seung, 2001) in Alg. 2 to solve NMF, which guarantees the convergence.
As white-box global context modules, VQ, CD, and NMF are straightforward and light, showing remarkable efficiency. They are formulated into optimization algorithms that mainly consist of matrix multiplications with the complexity O(ndr), much cheaper than complexity O(n2d) in self-attention as r n. All three MDs are memory-friendly since they avoid generating a large n× n matrix as an intermediate variable, like the product of Q and K of self-attention in Eq. (3). In the later section, our experiments prove MDs are at least on par with self-attention, though the architectures ofM are created by optimization and look different from classic dot product self-attention.

heading: 2.3 ONE-STEP GRADIENT
text: Since M involves an optimization algorithm as its computational graph, a crux to fuse it into the networks is how the iterative algorithm back-propagates gradient. The RNN-like behavior of optimization suggests Back-Propagation Through Time (BPTT) algorithm (Werbos et al., 1990) as the standard choice to differentiate the iterative process. We first review the BPTT algorithm below. However, in practice, the unstable gradient from BPTT does harm Hamburger’s performances. Hence we build an abstract model to analyze the drawbacks of BPTT and try to find a pragmatic solution while considering MD’s nature as an optimization algorithm.
As shown in Fig. 2, x, y and ht denote input, output and intermediate result at time step t, respectively, while F and G are operators. At each time step, the model receives the same input x processed by the underlying networks.
ht+1 = F(ht,x). (10)
The intermediate results hi are all discarded. Only the output of the last step ht is passed through G for output y,
y = G(ht). (11) In the BPPT algorithm, the gradient from output y to input x is given, according to the Chain rule:
∂y ∂x = t−1∑ i=0 ∂y ∂ht  t−1∏ j=t−i ∂hj+1 ∂hj  ∂ht−i ∂x . (12)
A thought experiment is to consider t→∞, leading to a fully converged result h∗ and infinite terms in Eq. (12). We suppose
that both F and G are Lipschitz with constants Lh w.r.t. h, Lx w.r.t. x, and LG , and Lh < 1. Note that these assumptions apply to a large number of optimization or numerical methods. Then we have:
Proposition 1 {hi}t has linear convergence.
Proposition 2 lim t→∞ ∂y ∂x = ∂y ∂h∗ (I − ∂F ∂h∗ ) −1 ∂F ∂x .
Proposition 3 lim t→∞ ‖ ∂y∂h0 ‖ = 0, limt→∞‖ ∂y ∂x‖ ≤ LGLx 1−Lh .
Table 1: One-step Gradient & BPTT
Method One-step BPTT VQ 77.7(77.4) 76.6(76.3) CD 78.1(77.5) 75.0(74.6) NMF 78.3(77.8) 77.4(77.0)
It is easy to incur gradient vanishing w.r.t. h0 when Lh is close to 0 and gradient explosion w.r.t. x when Lh is close to 1. The Jacobian matrix ∂y∂x , moreover, suffers from an ill-conditioned term (I− ∂F∂h∗ )
−1 when the largest eigenvalue of ∂F∂h , i.e., the Lipschitz constant of F w.r.t. h, approaches 1 and its minimal eigenvalue typically stays near 0, thus restricts the capability of the gradient to search the well-generalized solution in the parameter space. The erratic scale and spectrum of the gradient back through the optimization algorithm indicate the infeasibility to apply BPTT to Hamburger directly, corroborated by the experiments in Tab. 1, using the same ablation settings as Sec. 3.1.
The analysis inspires us a possible solution. Note that there are a multiplication of multiple Jacobian matrices ∂h j
∂hj−1 and a summation of an infinite series in BPTT algorithm, leading to uncontrollable scales of gradients. It enlightens us to drop some minor terms in the gradient while preserving its dominant terms to ensure the direction is approximately right. Considering terms of Eq. (12) as a series, i.e., { ∂y∂ht (∏t−1 j=t−i ∂hj+1 ∂hj ) ∂ht−i
∂x }i, it makes sense to use the first term of this series to approximate the gradient if the scale of its terms decays exponentially measured by the operator norm. The first term of the gradient is from the last step of optimization, leading to the one-step gradient,
∂̂y ∂x = ∂y ∂ht ∂ht ∂x . (13)
The one-step gradient is a linear approximation of the BPTT algorithm when t→∞ according to the Proposition 2. It is easy to implement, requiring a no_grad operation in PyTorch (Paszke et al., 2019) or stop_gradient operation in TensorFlow (Abadi et al., 2016) and reducing the time and space complexity from O(t) in BPTT to O(1). We test adding more terms to the gradient but its performance is worse than using one step. According to experimental results, one-step gradient is acceptable to back-propagate gradient through MDs.

heading: 3 EXPERIMENTS
text: In this section we present experimental results demonstrating the techniques described above. Two vision tasks that benefit a lot from global information and attention mechanism attract us, including semantic segmentation (over 50 papers using attention) and deep generative models like GANs (most state-of-the-art GANs adopt self-attention since SAGAN (Zhang et al., 2019a)). Both tasks are highly competitive and thus enough for comparing Hamburger with self-attention. Ablation studies show the importance of MD in Hamburger as well as the necessity of the one-step gradient. We emphasize the superiority of Hamburger on modeling global context over self-attention regarding both performance and computational cost.

heading: 3.1 ABLATION EXPERIMENTS
text: We choose to conduct all ablation experiments on the PASCAL VOC dataset (Everingham et al., 2010) for semantic segmentation, and report mIoU of 5 runs on the validation set in the form of best(mean). ResNet-50 (He et al., 2016) with output stride 16 is the backbone for all ablation experiments. We employ a 3×3 conv with BN (Ioffe & Szegedy, 2015) and ReLU to reduce channels from 2048 to 512 and then add Hamburger, the same location as popular attentions in semantic segmentation. For detailed training settings, please see Appendix E.1.
Breads and Hams We ablate each part of the Hamburger. Removing MD (ham) causes the most severe decay in performance, attesting to the importance of MD. Even if only the parameter-free MD is added (only ham), the performance can visibly improve. Parameterization also helps the Hamburger process the extracted features. Bread, especially upper bread, contributes considerable performance.
Latent Dimension d and r It is worth noting that there is no simple linear relation between d and r with performances measured by mIoU, though d = 8r is a satisfactory choice. Experiments show that even r = 8 performs well, revealing that it can be very cheap for modeling the global context.
Iterations K We test more optimization steps in the evaluation stage. In general, the same K for training and test is recommended. K = 6 is enough for CD and NMF, while even K = 1 is acceptable for VQ. Typically 3∼6 steps are enough since simple MD’s prior is still biased, and full convergence can overfit it. The few iterations are cheap and act as early stopping.

heading: 3.2 A CLOSE LOOK AT HAMBURGER
text: To understand the behavior of Hamburger in the networks, we visualize the spectrums of representations before and after Hamburger on the PASCAL VOC validation set. The input and output tensors are unfolded to RC×HW . The accumulative ratio of squared largest r singular values over total squared singular values of the unfolded matrix has been shown in Fig. 5. A truncated spectrum is usually observed in classic matrix decomposition models’ results due to the low-rank reconstruction. In the networks, Hamburger also promotes energy concentration while preserving informative details via the skip connection. Additionally, we visualize the feature maps before and after Hamburger in Fig. 6. MD helps Hamburger learn interpretable global information by zeroing out uninformative channels, removing irregular noises, and completing details according to the context.
0 20 40 60 80 100 120 r
0.6
0.7
0.8
0.9
1.0
ra tio
before after
Figure 5: Accumulative Ratio
Input image Before Hamburger After Hamburger Ground Truth
Redundancy
Incompleteness
Denoising
Completion
Figure 6: Visualization of feature maps

heading: 3.3 A COMPARISON WITH ATTENTION
text: This section shows the advantages of MD-based Hamburger over attention-related context modules in computational cost, memory consumption, and inference time. We compare Hamburger (Ham) with self-attention (SA) (Vaswani et al., 2017), Dual Attention (DA) module from DANet (Fu et al., 2019), Double Attention module from A2 Net (Chen et al., 2018b), APC module from APCNet (He et al., 2019b), DM module from DMNet (He et al., 2019a), ACF module from CFNet (Zhang et al., 2019b), reporting parameters and costs of processing a tensor Z ∈ R1×512×128×128 in Tab. 3. Excessive memory usage is the key bottleneck of cooperating with attention in real applications. Hence we also provide the GPU load and inference time on NVIDIA TITAN Xp. In general, Hamburger is light in computation and memory compared with attention-related global context modules.

heading: 3.4 SEMANTIC SEGMENTATION
text: We benchmark Hamburger on the PASCAL VOC dataset (Everingham et al., 2010), and the PASCAL Context dataset (Mottaghi et al., 2014), against state-of-the-art attentions. We use ResNet-101 (He et al., 2016) as our backbone. The output stride of the backbone is 8. The segmentation head is the same as ablation experiments. NMF is usually better than CD and VQ in ablation studies (see Tab. 1). Therefore, we mainly test NMF in further experiments. We use HamNet to represent ResNet with Hamburger in the following section.
Results on the PASCAL VOC test set, and the PASCAL Context validation set, are illustrated in Tab. 4, and Tab. 5, respectively. We mark all attention-based models with ∗ in which diverse attentions compose the segmentation heads. Though semantic segmentation is a saturated task, and most contemporary published works have approximate performances, Hamburger shows considerable improvements over previous state-of-the-art attention modules.
3.5 IMAGE GENERATION
Attention presents as the global context description block in deep generative models like GANs. Most state-of-the-art GANs for conditional image generation integrate self-attention into their architectures since SAGAN (Zhang et al., 2019a), e.g., BigGAN (Brock et al., 2018), S3GAN (Lučić et al., 2019), and LOGAN (Wu et al., 2019). It is convincing to benchmark MDbased Hamburger in the challenging conditional image generation task on ImageNet (Deng et al., 2009).
Experiments are conducted to compare Hamburger with self-attention on ImageNet 128×128. Selfattention is replaced by Hamburger with NMF ham in both generator and discriminator at feature resolution 32×32, named as HamGAN-baby. HamGAN achieves an appreciable improvement in Fréchet Inception Distance (FID) (Heusel et al., 2017) over SAGAN. Additionally, we compare Hamburger with a recently developed attention variant Your Local GAN (YLG) (Daras et al., 2020) using their codebase and the same training settings, named HamGAN-strong. HamGAN-strong offers over 5% improvement in FID while being 15% faster for the total training time and 3.6x faster for the module time (1.54 iters/sec of HamGAN, 1.31 iters/sec of YLG, and 1.65 iters/sec without both context modules, averaged from 1000 iterations) on the same TPUv3 training platform.

heading: 4 RELATED WORK
text: General Survey for Attention The last five years have witnessed a roaring success of attention mechanisms (Bahdanau et al., 2015; Mnih et al., 2014; Xu et al., 2015; Luong et al., 2015) in
deep learning. Roughly speaking, the attention mechanism is a term of adaptively generating the targets’ weights to be attended according to the requests. Its architectures are diverse, and the most well-known one is dot product self-attention (Vaswani et al., 2017). The attention mechanism has a wide range of applications, from a single source (Lin et al., 2017) to multi-source inputs (Luong et al., 2015; Parikh et al., 2016), from global information discovery (Wang et al., 2018; Zhang et al., 2019a) to local feature extraction (Dai et al., 2017; Parmar et al., 2019).
Previous researchers attempt to explain the effectiveness of attention mechanisms from numerous aspects. Capturing long-range dependencies (Wang et al., 2018), sequentially decomposing visual scenes (Eslami et al., 2016; Kosiorek et al., 2018), inferring relationships between the part and the whole (Sabour et al., 2017; Hinton et al., 2018), simulating interactions between objects (Greff et al., 2017; van Steenkiste et al., 2018), and learning the dynamics of environments (Goyal et al., 2019) are often considered as the underlying mechanisms of attention.
One common idea from biology is that attention simulates the emergence of concerns in many unconscious contexts (Xu et al., 2015). Some work tries to interpret the attention mechanism by visualizing or attacking attention weights (Serrano & Smith, 2019; Jain & Wallace, 2019; Wiegreffe & Pinter, 2019), while others formulate attention into non-local operation (Wang et al., 2018) or diffusion models (Tao et al., 2018; Lu et al., 2019) or build attention-like models via Expectation Maximization (Greff et al., 2017; Hinton et al., 2018; Li et al., 2019) or Variational Inference (Eslami et al., 2016) on a mixture model. A connection between transformer and graph neural network is discussed as well (Liang et al., 2018; Zhang et al., 2019c). Overall, discussions towards attention are still far from reaching agreements or consistent conclusions.
Efficient Attention Recent works develop efficient attention modules via low-rank approximation in both computer vision (Chen et al., 2018b; Zhu et al., 2019; Chen et al., 2019; Li et al., 2019) and natural language processing (Mehta et al., 2019; Katharopoulos et al., 2020; Wang et al., 2020; Song et al., 2020). Technically, the low-rank approximation usually targets at the correlation matrix, i.e., the product of Q and K after the softmax operation, using a product of two smaller matrices to approximate the correlation matrix and applying the associative law to save the memory cost and computation, where the approximation involves kernel functions or other similarity functions. Other works (Babiloni et al., 2020; Ma et al., 2019) make efforts to formulate attention into tensor form but may generate large intermediate variables. In this paper, we do not approximate attention or make it efficient. This paper formulates modeling the global context as a low-rank completion problem. The computation and memory efficiency is a by-product of the low-rank assumption on the clean signal subspace and optimization algorithms as architectures.
Matrix Decomposition in Deep Learning There is a long history of combining MD with deep learning. Researchers focus on reducing the parameters in the networks via factorization on the weights, including the softmax layer (Sainath et al., 2013), the convolutional layer (Zhong et al., 2019), and the embedding layer (Lan et al., 2019). Tariyal et al. (2016) attempts to construct deep dictionary learning for feature extraction and trains the model greedily. This paper tries to factorize the representations to recover a clean signal subspace as the global context and provide a new formulation for modeling the long-range dependencies via matrix decomposition.

heading: 5 CONCLUSION
text: This paper studies modeling long-range dependencies in the networks. We formulate learning the global context as a low-rank completion problem. Inspired by such a low-rank formulation, we develop the Hamburger module based on well-studied matrix decomposition models. By specializing matrix decomposition’s objective function, the computational graph created by its optimization algorithm naturally defines ham, Hamburger’s core architecture. Hamburger learns interpretable global context via denoising and completing its input and improves the spectrum’s concentration. It is startling that, when prudently coped with the backward gradient, even simple matrix decomposition proposed 20 years ago is as powerful as self-attention in challenging vision tasks semantic segmentation and image generation, as well as light, fast, and memory-efficient. We plan to extend Hamburger to natural language processing by integrating positional information and designing a decoder like Transformer, build a theoretical foundation for the one-step gradient trick or find a better method to differentiate MDs, and integrate advanced MDs in the future.

heading: ACKNOWLEDGMENTS
text: Zhouchen Lin is supported by NSF China (grant no.s 61625301 and 61731018), Major Scientific Research Project of Zhejiang Lab (grant no.s 2019KB0AC01 and 2019KB0AB02), Beijing Academy of Artificial Intelligence, and Qualcomm. We thank Google’s Tensorflow Research Cloud (TFRC) for providing us Cloud TPUs.

heading: A TABLE OF NOTION

heading: B HAMS
text: Additionally, we introduce another type of ham adopted by Hamburger, Concept Decomposition.
Concept Decomposition We first enhance Concept Decomposition (Dhillon & Modha, 2001) to the following form:
min D,C ‖X −DC‖2F + β‖C‖2F
s.t.D ∈ arg max D
Q (D,X) . (14)
This problem has a closed solution w.r.t. C under a given D, i.e., C = (D>D + βI)−1D>X . Since D>D + βI is a positive definite matrix with a regularized conditional number, the inverse can be more numerically stable than the original one where a semi-positive definite matrix D>D is given under β = 0. In practice, 0.01 or 0.1 makes no difference for β.
Algorithm 3 Ham: Soft CD Input X . Initialize D, C for k from 1 to K do C ← softmax( 1T cosine(D,X)) D ← normalize(XC>)
end for C ← (D>D + βI)−1D>X Output X̄ = DC.
The dictionary in CD is given by spherical K-means (Dhillon & Modha, 2001) with objective Q (D,X), as mentioned in Eq. (14).
arg max D,{πj}r
∑r j=1 ∑ x∈πj cosine (x,dj)
s.t. ‖dj‖ = 1. (15)
The same strategy as VQ is adopted to make the whole algorithm differentiable, however, in which each column of D is normalized to be a unit vector and thus differs from VQ.

heading: C PROOF OF PROPOSITIONS
text: We investigate an abstract RNN model inspired by numerical methods to understand the drawbacks of BPTT algorithm in differentiating the optimization algorithm of MDs,M. We show the propositions in Sec. 2.3 to illustrate the unstable gradient fromM when using BPTT algorithm, considering MDs’ nature as optimization algorithms.
Proposition 1 The iterations of F have linear convergence. Proof. It is obvious that F is a contraction mapping w.r.t. h under arbitrary given x. We can then conclude {ht} is a Cauthy sequence and F(∗,x) admits a unique fixed point h∗ due to Banach Fixed Point Theorem.
‖ht+1 − h∗‖ = ‖F(ht,x)−F(h∗,x)‖ ≤ Lh‖ht − h∗‖
(16)
Eq. (16) shows the linear convergence.
Proposition 2 lim t→∞ ∂y ∂x = ∂y ∂h∗ (I − ∂F ∂h∗ ) −1 ∂F ∂x .
Proof. Note that F(∗,x) admits a unique fixed point h∗ under arbitrary given x, i.e., h∗ = F(h∗,x) =⇒ h∗ −F(h∗,x) = 0 (17)
By differentiating the above equation, we can obtain
(I − ∂F ∂h∗ ) ∂h∗ ∂x = ∂F ∂x
(18)
The Jacobian matrix I − ∂F∂h∗ is invertible, which implies the existence of the implicit function h ∗(x). Immediately, we have
lim t→∞
∂y ∂x = ∂y ∂h∗ ∂h∗ ∂x = ∂y ∂h∗ (I − ∂F ∂h∗ )−1 ∂F ∂x , (19)
which completes the proof.
Proposition 3 lim t→∞ ‖ ∂y∂h0 ‖ = 0, limt→∞‖ ∂y ∂x‖ ≤ LGLx 1−Lh .
Proof.
‖ ∂y ∂h0 ‖ = ‖ ∂y ∂ht t∏ i=1 ∂hi ∂hi−1 ‖ ≤ ‖ ∂y ∂ht ‖ t∏ i=1 ‖ ∂h i ∂hi−1 ‖ ≤ LGLth (20)
Then we have: lim t→∞ ‖ ∂y ∂h0 ‖ = 0. (21)
‖∂y ∂x ‖ = ‖ t∑ i=0 ∂y ∂ht t∏ j=i+1 ∂hj ∂hj−1 ∂hi ∂x ‖
≤ t∑ i=0 ‖ ∂y ∂ht ‖ t∏ j=i+1 ‖ ∂h j ∂hj−1 ‖‖∂h i ∂x ‖ ≤ LG( t−1∑ i=0 Lih)Lx
= LGLx(1− Lth)
1− Lh
(22)
Then we have: lim t→∞ ‖∂y ∂x ‖ ≤ LGLx 1− Lh . (23)

heading: D DATASETS
text: PASCAL VOC The PASCAL VOC dataset (Everingham et al., 2010) is a widely used dataset in both semantic segmentation and detection. For segmentation, it contains 10,582 images for training, 1,449 images for validation and 1,456 images for testing. PASCAL VOC dataset involves 20 foreground object classes and a background class for segmentation and detection.
PASCAL Context The PASCAL Context dataset (Mottaghi et al., 2014) is a challenging dataset in semantic segmentation, which provides detailed labels and involves 59 foreground object classes and a background class for segmentation. It consists of 4,998 and 5,105 images in training and validation set, respectively.
ILSVRC 2012 The ILSVRC 2012 (ImageNet) (Deng et al., 2009) dataset contains 1.3M training samples and 50k test images, categorized into 1000 object classes. We resize images to resolution 128 × 128, as done in SNGAN with projection (Miyato & Koyama, 2018) and SAGAN (Zhang et al., 2019a).

heading: E DETAILS OF EXPERIMENTS
text: E.1 ABALATION EXPERIMENTS
We use dilated ResNet-50 (He et al., 2016) with the output stride 16 as the backbone. The backbone is pre-trained on ImageNet (Deng et al., 2009). We apply a poly-learning rate policy under batch size 12 and 30k iterations (about 35 epochs) for fast experiments (less than 12 hours using 1 NVIDIA TITAN Xp GPU). The initial learning rate is set to 0.009, multiplied by (1− iteritermax )
0.9 after each iteration, with momentum 0.9 and weight decay 0.0001. Hyperparameters of Hamburger are the same as Appendix E.3.
E.2 A COMPARISON WITH ATTENTION MECHANISM
We report MACs according to Molchanov et al. (2016), using torchprofile1, a more accurate profiler for Pytorch. Real-time cost is measured by built-in Pytorch memory tools on NVIDIA TITAN Xp GPU with a input tensor Z ∈ R1×512×128×128. Inference times are averaged results from 20 repeats of 100 runs.
E.3 SEMANTIC SEGMENTATION
Architectures We use ResNet-101 (He et al., 2016) with the ouptput strid 8 as our backbone. We adopt dilated convolution (Chen et al., 2018a) to preserve more detail spatial information and enlarge receptive field as done in the backbone of state-of-the-art attention models (Fu et al., 2019; Li et al., 2019; Zhang et al., 2019b). We employ a 3×3 convolution layer with BN and ReLU to reduce channels from 2048 to 512 and then add Hamburger on the top of the backbone. Note that the input of Hamburger is a tensor Z ∈ RC×H×W . We unfold Z to a matrix Z ∈ RC×HW and set dz = C and n = HW for Hamburger. Latent dimension d and r, i.e., the column vectors’ dimension of the input matrix X ∈ Rd×n toM and the number of atoms in the dictionary D ∈ Rr×d, are set to 512 and 64. The iterations of MD’s optimization algorithm, K, are set to 6. Non-negative Matrix Factorization (NMF) is our default ham for semantic segmentation.
Data augmentation In the training stage, we apply random left-right flipping, random scaling (from 0.5 to 2), and cropping to augment the training data. Images are resized to 513×513 for the PASCAL VOC dataset and the PASCAL Context dataset. In the test stage, the multi-scale and flipping strategy is applied as other state-of-the-art attention-based models (Fu et al., 2019; Yuan & Wang, 2018; Yuan et al., 2020).
1https://github.com/zhijian-liu/torchprofile
Optimization We use mini-batch SGD with momentum 0.9 to train HamNet. Synchronized Batch Normalization is adopted in experiments on semantic segmentation. All backbones are fine-tuned from ImageNet (Deng et al., 2009) pre-training. Following previous works (Zhao et al., 2017; Chen et al., 2018a), we apply a poly-learning rate policy. The initial learning rate is multiplied by (1− iteritermax )
0.9. For the PASCAL VOC dataset, learning rate, weight decay, batch size, iterations are set to 0.009, 0.0001, 16, and 60k, respectively. We fine-tune HamNet on the PASCAL VOC trainval set with the learning rate down to a tenth. The learning rate, weight decay, batch size, iterations are 0.002, 0.0001, 16, and 25k for the PASCAL-Context dataset.
E.4 IMAGE GENERATION
We use the official GAN codebase2 from Tensorflow (Abadi et al., 2016) and TF-GAN to train HamGAN and evaluate FID.
Architectures Experiments on ImageNet are conducted using the same architecture as SAGAN (Zhang et al., 2019a), and YLG (Daras et al., 2020), including Spectral Normalization (Miyato et al., 2018) in both the generator and the discriminator, conditional Batch Normalization in the generator, and class projection in the discriminator (Miyato & Koyama, 2018). Hamburger with NMF ham is placed at feature resolution 32×32 in both the generator and the discriminator where self-attention can obtain the best FID according to Zhang et al. (2019a). We use d = 8r for Hamburger, and d is the same as the input channels, while the optimization steps K are 6. Restricted to expenditures of training GANs on ImageNet, d, r, and K are decided according to the ablation experiments on semantic segmentation without new ablation experiments.
Optimization For all models, we use Adam (Kingma & Ba, 2015) optimizer with TTUR (Heusel et al., 2017). HamGAN employs the same training settings as SAGAN (Miyato et al., 2018) and YLG (Daras et al., 2020), respectively.
Evaluation metrics The quality of images generated by GANs are evaluated by Fréchet Inception Distance (FID) (Heusel et al., 2017). Lower FID indicates that the model can generate higher-fidelity images. In our experiments, 50k images are sampled from the generator to compute FID. We evaluate HamGAN for 6 runs and report the best FID to approximately match the convention in the modern GAN research like Kurach et al. (2019) and CR-GAN (Zhang et al., 2020), reporting top 5%/15% results in the experiments.

heading: F FURTHER RESULTS FROM ABLATION EXPERIMENTS
text: Initialization We test four types of initialization for the dictionary D, including fixed initialization, learned initialization, random initialization, and warm start with online update. Usually, random initialization is the best choice that means we can sample each entry of D from a given distribution like Uniform(0, 1) as the initialization of the optimization algorithmM. For NMF, after initializing D, we initialize C = softmax( 1T cosine(D,X)) since K-means is usually applied for initializing NMF and this initialization for C is equivalent to a single update in Spherical K-means. A special reminder is that it is not suitable to initialize either D or C to values too close to 0 due to the property of the MU rule. So the temperature T is recommended to be a higher value like 1 in this
2https://github.com/tensorflow/gan
initialization for C. Random initialization also works for C in NMF with scores 77.8(77.6) when sampling Cij ∼ Uniform(0, 1). Note that learned initialization is always the worst one since the BPTT algorithm is employed to learn the initialization that the gradient fromM may impede the training of the backbone, instead of the one-step gradient. Warm start benefits MD with unit vectors in the dictionary D like CD. In general, random initialization is good enough for all three selected MD models. A possible reason is that it can enforce the network to adapt to the results solved by different initializations during the training process, acting like an inner augmentation.
Temperature T As we have claimed, when T approaches 0, we can get a solution close to the original problem in both VQ and CD. In VQ and CD experiments, a relatively low temperature T is more recommended to solve a better D for MD. However, it will not receive more gains but increase the variance during training if we further lower T .
Iterations K We take the iterations K of optimization algorithmsM for all three MD models, NMF, CD, and VQ, into our consideration. More iterations and even fully converged results forM are tested in the evaluation stage but worse than little optimization steps. The smaller K, ranging from 1 to 8, can be treated as early stopping for the optimization algorithmM, obtaining satisfactory performances. For a detailed visualization, see Fig. 7, Fig. 8, Fig. 9.
1 2 3 4 5 6 7 8 9 10 12 15 20 30 eval
NMF_MEAN
76.50
76.75
77.00
77.25
77.50
77.75
1 2 3 4 5 6 7 8 9 10 12 15 20 tra in
CD_MEAN

heading: G AN INTUITIVE ILLUSTRATION
text: In this section, we hope to give an example to help our readers develop insight into why the low-rank assumption is useful for modeling the representations’ global context.
The low-rank assumption helps because it represents the inductive bias that the low-level representations contain limited and much less high-level concepts than the scale of the representations themselves. Imagine an image in which a person works on the road. Many hyper-pixels extracted by the backbone CNN will describe the road. Note that the road can be considered as repeats of small road patches, which means that we can represent the road via modeling the basic road patches and repeat them. Mathematically, it is equivalent to finding a small set of bases D corresponding to different road patches and a coefficient matrix C that captures the relation between the elementary road patches and the hyper-pixels. This example illustrates that the high-level concepts, i.e., the global context, can be low-rank in the ideal situation.
The hyper-pixels describing the road patches have close semantic attributes. However, due to the vanilla CNN’s inefficiency for modeling the long-range dependencies, the learned representation contains too many local details and incorrect information, lacking global guidance. Imagine that the person in the image wears gloves. When we see the gloves patch locally, we think that this patch describes gloves. When we consider the global context, we can understand that this patch is a part of a person. The semantic information is hierarchical, depending on at which level we hope to comprehend. This work aims at enabling the networks to understand the context globally via the low-rank completion formulation. We thus model the incorrect information, namely the redundancies and incompleteness, as a noise matrix. To emphasize the global context, we decompose the representations into two parts, a low-rank global information matrix and a noise matrix, by employing the optimization algorithm to recover the clean signal subspace, discard the noises, and enhance the global information via the skip connection. It could be learned from the data on how much global information the networks need for a specific task.

Review summaries:
The paper presents a method based on matrix decomposition (MD) for encoding global context in computer vision tasks. In particular, a "Hamburger" block is proposed encompassing matrix decomposition as its central part, between two linear projection layers. Direct comparison and relations are drawn between the proposed method and the widely adopted self-attention paradigm. The proposed method leads to improved results when Hamburger blocks are used instead of self-attention blocks, leading at the same time to reduced number of parameters, memory footprint and inference time.

This paper proposes to use matrix decomposition to construct low-rank representations to find the long-distance correlations in context, which is demonstrated more effective than popular self-attention mechanism. Combining linear transformation and matrix decomposition (core part), authors design Hamburger block to model global dependencies from input as residual output. The authors propose differentiable modified Vector Quantization and Non-negative Matrix Factorization to perform matrix decomposition. They propose one-step gradient, an approximation of Back-Propagation Through Time (BPTT) algorithm, to back-propagate gradient of matrix decomposition. They conduct experiments on semantic segmentation and image generation to demonstrate the superiority of their methods regarding modelling global dependencies and computational cost.