Why is the input of the algorithm in "Linear-Time Self Attention with Codeword Histogram for Efficient Recommendation" a matrix?

Question

My question is about the algorithm in the article Linear-Time Self Attention with Codeword Histogram for Efficient Recommendation, as described in the picture below.

It is written at beginning section 3.1 in the article $X$ is a matrix but It is seen the figure 2 a sequence of codeword indices represented as a vector and in figure 3 a sequence of codeword indices is represented as a matrix, so I don't understand these details.

Please explain why the codeword indices are depicted as a vector in figure 2 and as a matrix in Figure 3.

Answer 1

Because Figure 2 shows the case with only 1 codebook. In Figure 3, the $B$-dimension represents the codeword indices of an item in the $B$ codebooks.

By the way, the "matrix" mentioned at the beginning of Section 3.1 is different from the "matrix" in Figure 3. the former is in $\mathbb{R}^{L\times D}$ and is the original input. Since Section 3.1.2, $B$ codebooks are introduced, and the input is then encoded as a matrix in $\{1,\ldots,W\}^{L\times B}$. Please refer to Section 3.1.2 for details.