Local redundancy - Product Quantization and global redundancy - Residual Quantization connection

Question

I am currently reading Compressing Deep Convolutional Networks using Vector Quantization paper. The paper states in section 3.2.5 that Product Quantization explores some local redundancy and Residual Quantization explores global redundancy structure between weight vectors.

My general question is what is the connection between product quantization and local redundancy, and between residual quantization and global redundancy?

To make the answer clearer for me, I have more detail questions behind that general question:

1. What do local redundancy and global redundancy mean? I tried to search, and found this Wikipedia article, but I don't understand it. Can someone explain it to me in an easy and intuitive way?

2. I am still not fully understand the product quantization technique in this paper. This is my current understanding:

   • The weight matrix size is mxn. And the n is divided by s number of partition. For example, n = 8 ; s = 2. So it partition to 4.
   • The codebook (for saving centroid) for each partition is a kx(n/s) matrix. k is number of codebook. n/s is column size of each partition. So, the 1 centroid has n/s member? I don't understand this. I always think that 1 centroid is 1 number / value.

3. I know how to count the residual quantization. But, I don't understand what it does intuitively, i.e., what can make the quantization result become similar with original; and what does the quantization of residual do?

I prefer as easy an explanation as possible (with words and intuitively). Some mathematics is okay to support the explanation if necessary.

Answer 1

if we think of a neuron $w$ as a matrix

K-Means is doing element-wise clustering,
Product Quantization is doing submatrix-wise clustering for submatrices of the same index ,
Residual Quantization is doing matrix-wise clustering recursively.

that's why the author states that KM maintains no structure, PQ maintains local structure and RQ maintains global structure.

hope that helps with your questions.