Quantization can mathematically be defined as a process of mapping a continuous set of values (X ⊆ R) to a discrete set (Q ⊂ R) with a finite number of values |Q|. It can be expressed as the following function:

$$,$$where each subset S_i​ (called a ‘quantization bin’) corresponds to a discrete value q_i in Q.

The goal of quantization is to find a mapping that minimizes error while representing X with a minimal number of discrete levels. Depending on the method of discretization, it is classified into various types, such as uniform quantization (the range of X is divided into equally spaced intervals), non-uniform quantization (intervals of varying size are used to adapt to the distribution of X), scalar quantization (each scalar value is mapped independently), and vector quantization (groups of values are mapped jointly to discrete values, allowing for complex patterns and dependencies in the data.) The quantization complexity, especially in the case of non-linear quantization, grows exponentially with dimensionality, so practical implementations often rely on heuristics to keep the computational complexity (costs) under control.

Uniform Quantization

Uniform quantization is commonly followed due to its simplicity, and ease of implementation. The quantization step size is created by dividing the input range [a,b] into N equal intervals of width Δ, i.e., Δ = (b−a) / N. Each interval S_i is represented by a midpoint or reconstruction level q_i. For any x ∈ S_i​, Q(x) = q_i ≈ x.

The quantization error, e(x) = x−Q(x), is the deviation resulting from approximating x with q_i. The Mean Squared Error (MSE) is given by: E [e(x)²] = ∫_a^b (x− Q(x)²).p(x)dx, where p(x) is the probability density function of X. In uniform quantization, The MSE is approximately Δ²/12. The quantization noise (error) is inversely proportional to the number of quantization levels (N) since reducing the quantization interval Δ reduces the error.

Lloyd-Max Quantization

In many real-world applications, data is seldom uniformly distributed. As such, applying uniform quantization introduces the risk of large errors in regions with high variance. Non-uniform quantization is more suited for such use cases where the allocation of quantization levels is optimized based on the probability distribution of X. One of the most commonly used non-uniform methods is Lloyd-Max quantization, an iterative algorithm for minimizing quantization error by finding an optimal set of reconstruction levels and decision boundaries. It involves four main steps:

1. Initialization: Selecting the initial quantization levels {q_i}^N_i=1
2. Partitioning: Setting the decision boundaries {d_i}^N−1_i=1such that each boundary is the midpoint between two adjacent reconstruction levels: d_i = (q_i+q_i+1) / 2
3. Updating Reconstruction Levels: For each interval S_i = [d_i−1, d_i], q_i is updated as the mean of X over S_i
4. Repeating steps 2 and 3 until convergence.

Furthermore, in high-dimensional spaces (e.g., images and videos), Lloyd-Max and other non-uniform quantization methods are generally extended to minimize vector quantization errors.

Other Key Elements of Mathematical Quantization

Rate-Distortion function: It is useful in deciding on the trade-off between the quantization error and the bit rate. It helps to capture the minimum bit rate needed to achieve a specific level of distortion.

Signal-to-Quantization-Noise Ratio (SQNR): It measures the signal quality relative to the noise in that signal that gets introduced due to the quantization steps. For uniform quantization of a signal X with zero mean and variance σ², it is expressed as $$.$$

Stochastic quantization: It uses probabilistic mappings, i.e., each value x is mapped to q_i​ with probability p_i proportional to proximity. It reduces systematic quantization errors by using stochasticity as regularization.

Quantization is mathematically grounded in approximation theory, information theory, linear algebra, optimization, and probability theory. Its application spans critical fields like machine learning, quantum computing, and signal processing. It is critical for converting analog signals (e.g., sound waves) into digital data, thereby enabling efficient analysis, faster processing, robust storage, and transmissions without data loss. that can be stored, processed, and analyzed by computers. It is particularly useful in machine learning (e.g., model compression, pruning, and low-precision training) to reduce the model sizes and computational needs with minimal loss in model performance.

PS: 10 – 20% of this paper was written with the help of Generative AI.