A Nuclear-Norm Lower Bound for Dithered Scalar Quantization of Matrix Products
Abstract
We consider the problem of minimizing error in quantized matrix multiplication C=AB. Scalar quantization of the factors introduces rounding errors whose scale depends on the maximum absolute entries -- the ranges -- of their rows and columns. These ranges determine the quantization grid steps. To reduce the error, we optimize over product-preserving transformations that alter the factor ranges and grid steps without changing C. Specifically, we seek the smallest leading expected squared error over invertible inner changes of basis and orthogonal outer rotations. Under independent, zero-mean subtractive dither noise on an unbounded lattice, we prove the output-only bound Elead ≥ (cA+cB)/K ‖ AB‖*2, where K is the inner dimension, cA and cB are normalized noise variances, and ‖ AB‖* is the nuclear norm. The bound is tight: an SVD-aligned Hadamard construction attains the infimum whenever a Hadamard matrix of order K exists, including every power of two, while an SVD-aligned DCT construction is within a factor of two for every K. Without outer rotations, Gram-matrix balancing minimizes factorization energy, and finite-set flattening achieves the bound within Clog(K(m+n)). For power-of-two K, conditional expectations deterministically select the Hadamard signs in O((m+n)K2) exact-real operations. Synthetic experiments verify both constructions and illustrate the tradeoff between regularization and conditioning. These results characterize the full-gauge optimum and quantify the cost of preserving row and column indices.
Related
- Beyond Scalar Sensitivity: Activation-Aware Mixed-Precision LLM Quantization with Cross-Layer Refinement
- Positive scalar curvature on products of noncompact manifolds
- Classification of reduced free products of nuclear C*-algebras
- Pointwise Hölder continuity of Lyapunov exponents of random matrix products
- Hölder regularity of the top Lyapunov exponent for random matrix products with low-dimensional equator
BibTeX
@misc{sao2026nuclearnorm,
title = {{A Nuclear-Norm Lower Bound for Dithered Scalar Quantization of Matrix Products}},
author = {Piyush Sao and Narasinga Miniskar and Pedro Valero-Lara and Keita Teranishi and Sudip Seal},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05641},
eprint = {2609.05641},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05641},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Nuclear-Norm Lower Bound for Dithered Scalar Quantization of Matrix Products
AU - Piyush Sao
AU - Narasinga Miniskar
AU - Pedro Valero-Lara
AU - Keita Teranishi
AU - Sudip Seal
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05641
UR - https://arxiv.org/abs/2609.05641
AB - We consider the problem of minimizing error in quantized matrix multiplication C=AB. Scalar quantization of the factors introduces rounding errors whose scale depends on the maximum absolute entries -- the ranges -- of their rows and columns. These ranges determine the quantization grid steps. To reduce the error, we optimize over product-preserving transformations that alter the factor ranges and grid steps without changing C. Specifically, we seek the smallest leading expected squared error over invertible inner changes of basis and orthogonal outer rotations. Under independent, zero-mean subtractive dither noise on an unbounded lattice, we prove the output-only bound E_lead ≥ (c_A+c_B)/K ‖ AB‖_*^2, where K is the inner dimension, c_A and c_B are normalized noise variances, and ‖ AB‖_* is the nuclear norm. The bound is tight: an SVD-aligned Hadamard construction attains the infimum whenever a Hadamard matrix of order K exists, including every power of two, while an SVD-aligned DCT construction is within a factor of two for every K. Without outer rotations, Gram-matrix balancing minimizes factorization energy, and finite-set flattening achieves the bound within Clog(K(m+n)). For power-of-two K, conditional expectations deterministically select the Hadamard signs in O((m+n)K^2) exact-real operations. Synthetic experiments verify both constructions and illustrate the tradeoff between regularization and conditioning. These results characterize the full-gauge optimum and quantify the cost of preserving row and column indices.
ER -