Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper proposed a matrix decomposition-based method to capture spatial long range correlation in the neural network. The proposed method employs an optimization method, i.e. non-negative matric factorization, to reconstruct a low-rank embedding of the input data. The experimental results show that the proposed method outperforms various popular attention-based methods in recent years for various vision tasks, i.e. semantic segmentation and image generation. This paper is basically well written and easy to follow what they have done.

However, I have several concerns that I listed as follows.
- According to experimental results, I find the proposed matrix decomposition based method outperforms several attention based methods in mIoU for semantic segmentation and FIN for image generation. Nevertheless, the Parameters, FLOPs, memory and running time are only compared with Dual attention network. Please compare more attention based methods to verify the proposed method is more efficient attention based methods.
- The proposed method is similar with EMA-Net, especially for employing concept decomposition as the optimization algorithm. Please discuss the relation and difference between the proposed method and EMA-Net.
- I am very interested in the initialization of matrix decomposition. In the supplementary, authors only discuss the initialization of D, so what is the best initialization of C for non-negative matrix factorization? Besides, what is the warm start with online update?
- The figures 3 and 4 are low quality, the text of coordinate is too small.

After rebuttal:
I appreciate the authors' detailed response to my questions, which largely addresses my previous concerns. 
It's very pleasure to reviewing this interesting, innovative and well-written paper.
A clear accept.
review_title: An honest work

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: # Summary:
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.


# Strengths:
The paper presents a novel and simple method for capturing global context, demonstrated on two challenging computer vision tasks, namely semantic segmentation and image generation. Important advantages of the proposed method, with respect to the self-attention method which is usually employed in such tasks, are the fact that it can be easily adapted to a wide range of models and problems, it is more efficient and has reduced memory requirements.

A one-step gradient method is proposed for propagating the gradients through the MD optimization algorithm during training. One-step gradient is shown to overcome the unstable gradient problems of the back-propagation through time (BPTT) algorithm, leading to improved performance. A detailed analysis is provided comparing the two methods (one-step vs BPTT).

The evaluation is quite comprehensive comparing the proposed hamburger block with respect to similar self-attention blocks under several aspects (accuracy/FID score, GPU load, GPU time, FLOPs, nr. of parameters). A detailed ablation study is also presented showing the effect of the most important factors of the proposed contribution in the final performance.

Regarding writing quality, the paper is clear and easy to read. The main ideas and contributions are clearly stated and presented. Some issues regarding the structure of the sections is discussed below.

# Weaknesses:
The paper makes the more general claim that the proposed approach can be used for including any human inductive bias expressed through an optimization problem, however, only the problem of capturing global context, in place of self-attention, is explored. To support this more general claim it would be important to include some representative examples (even without providing a detailed evaluation on those).

Possibly related to the previous point is the observation that non-negative matrix factorization (NMF) seems to always perform better than the other two matrix decomposition methods, Vector Quantization (VQ) and Concept Decomposition (CD). This leads to certain questions, as for example:
* are there any problems that lend themselves better to the other types of MD?
* is the performance of VQ and CD degraded because they are rendered soft?
* what is the divergence of soft with original MD as far as the original optimization problem is concerned? The results of the ablation on temperature T provided in Appendix G partially show that the "softening" of the algorithm might negatively affect the accuracy.

I find it also strange and possibly nearly violating formatting that the related work section is provided in the appendix. Some directly related work is discussed in the main text, yet a more detailed discussion considering a broader set of works only appears in the appendix. Also regarding related work, other works employing matrix decomposition in the context of deep learning, are not covered (e.g. (Sainath et al., 2013; Tariyal et al., 2016)).

Sainath, T. N., Kingsbury, B., Sindhwani, V., Arisoy, E., & Ramabhadran, B. (2013). Low-rank matrix factorization for deep neural network training with high-dimensional output targets. In 2013 IEEE international conference on acoustics, speech and signal processing (pp. 6655-6659).

Tariyal, S., Majumdar, A., Singh, R., & Vatsa, M. (2016). Deep dictionary learning. IEEE Access, 4, 10096-10109.

## Minor Comments
* Table 1, no details are provided for the metric used for the results
* Table 6, it would be better to specify the difference between the two entries of HamGAN
* The text in almost all figure is quite small and very hard to read on typical zoom factors (~100%).
 
# Rating Justification
Overall, I think that the idea of using matrix decomposition as architectural element to capture global context is quite interesting and novel. Also the method shows advantages with respect to self-attention as far as efficiency and memory requirements are concerned. There are some issues regarding the generality of the proposed approach and the paper's structure, however, I think that the paper strengths exceed its weaknesses.

# Rating and comments after the rebuttal
The authors addressed my concerns in their feedback and the revised manuscript they have provided. In particular, I find the claimed contributions much clearer now. In my view, they have also suitably addressed the concerns raised in the other reviews. As a result, I increase my rating to 8 as I think that this work is interesting, novel and impactful.

review_title: Matrix decomposition can help to capture global context more efficiently and with less overhead with respect to self-attention

final_score: rating: 7: Good paper, accept
review_content: 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.

I believe that there is clear novelty in the proposed method. The paper is well written. One weakness is that the experiment analysis is a little weak. It will be great to see stronger experiments in the final.

review_title: overall this is a good submission

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary
1. This paper finds that matrix decomposition (MD) performs well as well as the self-attention.
2. According to the paper, MD approximate the given matrix with low-rank, and it might be helpful inductive bias
3. MD can be implemented with vanilla matrix factorization or non-negative matrix factorization.
4. For stable learning, this paper proposes an additional technique, one-step gradient instead of back-propagation through time (BPTT)
5. To validate the performance, they experiment on semantic segmentation and image generation.

Please reply to the below questions.
1. What is the advantage of MD over attention? According to the paper, the main advantage of MD is a less computational burden, but there are several works for linear time attention. Furthermore, it is hard to find sufficient reasons that MD performs better than attention-based models. 
2. There is no description for Table 1. Could you explain the table 1?
3. Are there results for MD with BPTT instead of a one-step gradient on segmentation or image generation task?
4. What is the "human priors" in the conclusion section? Does it denote the "low-rank"?
It is hard to understand that low-rank will be helpful.
If MD set r as same as min(d,n) instead of small r, does MD have lower performance?
5. There are several works about 1) analyzing the low-rank problems in multi-head attention and 2) incorporating the low-rank approximation into attention. The discussion between this paper and related works is not enough.
6. The title is "Is Attention Better Than Matrix Decomposition?", but the paper is only for the "self"-attention and MD.
Are there results for Encoder-Decoder structured tasks (such as Translation)?

I suggest that this paper discusses the relationship between MD and the below papers.

a) Factorization and Attention
1. A Tensorized Transformer for Language Modeling

b) Low-rank problems and attention
1. Low-Rank Bottleneck in Multi-head Attention Models

c) Low-rank attention
1. Transformers are rnns: Fast autoregressive transformers with linear attention
2. Linformer: Self-Attention with Linear Complexity
3. Implicit Kernel Attention
4. Compact Multi-Head Self-Attention for Learning Supervised Text Representations

-----
I read a valuable author's response, and I keep my positive score.
review_title: MD could be an alternative for "self"-attention.

Meta-review: This paper introduces an alternative to self-attention, based on matrix factorization, and apply it to computer vision problems such as semantic segmentation. The method is simple and novel and obtains competitive results compared to existing approaches. The reviewers found the paper well written and easy to understand. For these reasons, I recommend to accept the paper.
Decision: Accept (Poster)