# Denoising Diffusion Models on Model-Based Latent Space
## 3 Proposed Method
### Latent-Space Encoding
#### 3.1.2 (Optimized) Product Quantization  
The base vector quantizer described in Section 3.1.1, while being a powerful tool, implies some major drawbacks. The number of codewords \(|\mathcal{C}|\) required to represent a code \(E(x)=i\) using \(b_{\mathcal{C}}\) bits is proportional to the cardinality of the codebook as \(|\mathcal{C}|=2^{b_{\mathcal{C}}}\). For moderately large \(x\) (i.e., an \(8\times 8\) 8-bit grayscale image patch), a reasonably high compression rate of \(1:16\) would imply encoding the block with \(512/16=32\) bits, which would lead to a codebook with \(|\mathcal{C}|=2^{32}\simeq 4B\) possible codewords! Clearly, such a large codebook would be hard to obtain and require large memory usage and intense computation cost; hence, more sophisticated quantizers are needed.  
Product Quantization (PQ) [19], schematized in Figure 2, is an upgrade in this direction. Instead of processing the input vector \(x\) as a whole, it is possible to split it into \(m\) subvectors \(x^{(1)},x^{(2)},\ldots,x^{(m)}\) and consider a subcodebook for each of them. For simplicity, it is common to have subvectors with equal length of \(n^{\prime}=\frac{n}{m}\): \(x^{(j)}=(x_{m*(j-1)+1},\ldots,x_{m*j})\), where \(m\) is a divisor of \(n\). At this point, the quantizer is the Cartesian product of \(m\) subquantizers that act on each subvector:  
\[q\colon X \longrightarrow\mathcal{C}=\mathcal{C}_{1}\times\ldots\times \mathcal{C}_{m} \tag{11}\] \[x \longmapsto c=(c_{1},\ldots,c_{m})=(q_{1}(x^{(1)}),\ldots,q_{m}(x^{(m)})) \tag{12}\]  
Since each subquantizer \(q_{j}\) is a separate vector quantizer, defined by its codebook \(\mathcal{C}_{j}\), the code for \(x\) can be obtained by independently encoding each subvector:  
\[E(x)=(E_{1}(x^{(1)}),\ldots,E_{m}(x^{(m)}))=(i^{1},\ldots,i^{m}) \tag{13}\]  
The fundamental difference is that the resulting code \((i^{1},\ldots,i^{m})\) is a vector; therefore, the total number of bits required to represent it corresponds to the sum of the bitrates of the subcodebooks. Hence, encoding \(x\) with a 32-bit code will require just 4 8-bit codebooks, for a total of only 1024 possible codewords.  
Optimized Product Quantization (OPQ) [20] offers further improvement. Instead of directly encoding the vector \(x\) as it is, it first applies an orthogonal matrix \(R\) (i.e., a change in basis). This operation is particularly useful in our case, as image pixels have correlations between them that are dictated by the structures present in the images subjects. Hence, simply splitting the images at fixed intervals may not be the best course of action, but it may be necessary to first reorder their pixels, so that correlated pixels end up in the same subvector. The problem of finding an optimal quantizer involves finding both the \(\mathcal{C}_{1},\ldots,\mathcal{C}_{m}\) codebooks and the matrix \(R\) subject to \(RR^{T}=\text{Id}\). In [20], the authors derive a nonparametric solution as an alternating minimization scheme, where in one step \(R\) is given, and the codebook is learned; in the other, the optimization of the MSE is carried out with respect to \(R\), while the codebook is fixed. The former step can simply be carried out via k-means in the transformed domain. For the latter, considering Equation (10), the problem can be written as  
\[\underset{s.t.\ RR^{T}=\text{Id}}{\text{argmin}}\ \sum_{x\in X}\|Rx-Rc\|_{2}^{2}= \underset{s.t.\ RR^{T}=\text{Id}}{\text{argmin}}\ \|RX-Y\|_{F}^{2} \tag{14}\]  
where, in the last formulation, with a slight abuse of notation, \(X\) is the matrix containing the practical data samples from the space, and \(Y\) is the reconstruction of \(X\) in the transformed domain according to the current codewords estimates (i.e., \(Y=D(E(X))\)). This problem is known as Generalized Procrustes Alignment [21] and has a closed-form solution in \(R=VU^{T}\), with \(V\) and \(U\) being the orthogonal matrices of the Singular Value Decomposition of \(XY^{T}\).