PaperlayerView exact revision on arXiv

Source-linked AI summary

A Nuclear-Norm Lower Bound for Dithered Scalar Quantization of Matrix Products

Piyush Sao, Narasinga Miniskar, Pedro Valero-Lara, Keita Teranishi, Sudip Seal

arXiv:2609.05641v1cs.ITcs.LGcs.NAmath.ITmath.NA

TL;DR

The paper asks how small leading quantization error can become under product-preserving changes to a matrix factorization. It analyzes the full gauge and finds an SVD-aligned construction attaining the lower bound at Hadamard dimensions and within a factor of two for every K.

  • Problem

    The leading quantization error depends on how the output matrix is factorized, so the paper asks for the smallest error achievable over product-preserving transformations.

    Source: §1 · p. 1

  • Method

    The paper analyzes product-preserving gauges, using Gram-matrix balancing and SVD-aligned constructions to control factorization energy and factor ranges.

    Source: §2.4 · p. 4, §11 · p. 16

  • Results

    At Hadamard dimensions the SVD-aligned construction attains the lower bound, and for every K it comes within a factor of two.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results distinguish full-gauge optimization, which is tightly characterized, from inner-only transforms, which have a logarithmic-factor guarantee.

    Source: §1 · p. 2, §11 · p. 16

    The high-rate ordering need not hold uniformly over eta-dependent ill-conditioned gauges, so the remainder term cannot be discarded before taking an infimum.

    Source: §3.3 · p. 6

Abstract

from arXiv · show

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_{\rm lead} \ge (c_A+c_B)/K \Vert AB\Vert_*^2$, where $K$ is the inner dimension, $c_A$ and $c_B$ are normalized noise variances, and $\Vert AB\Vert_*$ 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 $C\log(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.

1 Introduction

Scalar quantization error depends on how a matrix product is factorized, so the paper seeks the smallest leading error over product-preserving transformations. It establishes an output-dependent lower bound and constructions that attain or approach it, then characterizes the additional cost when outer rotations are unavailable.

1 Introduction

  • The paper frames the problem around product-weighted error: each factor’s perturbation is weighted by the corresponding row or column of the other factor, while scalar grid steps depend on vector ranges.The related transform study [14] addresses practical transform families; this work instead seeks a lower bound over product-preserving transformations.Source: §1 · p. 1
  • The lower bound is gauge-invariant and depends on the output nuclear norm, composing a grid-range versus average-energy inequality with a Frobenius-product versus nuclear-norm inequality.The bound applies under independent, zero-mean per-vector noise.Source: §1 · p. 2
  • Gram-matrix balancing closes the factorization-energy loss, with an explicit balancing transform for positive-definite Gram matrices.The factorization-energy infimum equals the squared nuclear norm of AB.Source: §1 · p. 2
  • At Hadamard dimensions, an SVD-aligned construction attains the lower bound, and for every K an SVD-aligned DCT-II construction is within a factor of two.The Hadamard result includes every power-of-two K.Source: §1 · p. 2
  • For inner-only transforms, finite-set flattening gives an O(log(K(m + n))) upper factor, and conditional expectations select Hadamard signs deterministically in O((m + n)K^2) exact-real operations when K is a power of two.The finite-set guarantee concerns the observed rows and columns.Source: §1 · p. 2
  • The resulting lower bound and constructions provide a transform-design certificate: the nuclear floor measures unavoidable leading error, while finite-set flatness measures the added cost of preserving visible indices.The paper distinguishes this setting from related coding limits and practical transforms under different finite-rate constraints.Source: §1 · pp. 2–3

2 Background and related work

This background motivates a product-aware error analysis and defines the product-preserving transformations used to study quantization. It connects factorization energy to the nuclear norm, range-driven error to peak-to-average flattening, and the paper’s guarantees to related quantization approaches.

2 Background and related work

  • The proof combines product-weighted error, product-preserving transformations, the nuclear-norm factorization identity, and peak-to-average flattening to obtain a Hadamard-dimension characterization, a constant-factor construction for every K, and an inner-only logarithmic bound.These ingredients and guarantees are presented as the paper’s contribution.Source: §2 · p. 3

2.1 Product-weighted error

  • The first two terms show why an entrywise error metric is insufficient: each perturbation is weighted by the other factor; the final term is the exact bilinear contribution from perturbing both factors.Source: §2.1 · p. 3

2.2 Gauge invariance

  • The full gauge combines orthogonal transformations on the free indices with an invertible inner transformation; outer rotations close the logarithmic gap left by inner transforms alone.The transformations preserve the product while changing factor ranges.Source: §2.2 · p. 3

2.3 Nuclear-norm factorization

  • The infimum of the product of factor Frobenius norms over the inner orbit is the nuclear norm of AB, including when rank(C) < K via regularized gauges.The Gram-matrix equalization resembles balanced state-space realizations, but here it optimizes a multiplicative trace objective for a factorized product.Source: §2.2 · p. 3, §2.3 · p. 4

2.4 Range versus energy

  • A grid step set by the largest absolute coordinate lets one large coordinate coarsen resolution for all others, while peak-to-average ratio measures the gap from average energy.Flattening seeks to prevent any coordinate from dominating; random rotations lose only a logarithmic factor on the finite set, whereas uniform all-input control is separate.Source: §2.4 · p. 4

2.5 Relation to quantization methods

  • Ordentlich and Polyanskiy’s coding bounds and practical quantizer analyses address different rate and setting constraints from this fixed-pair scalar row/column-grid lower bound.Their Part II treats a distinct covariance-informed, weight-only setting [11].Source: §2.5 · p. 4
  • WUSH optimizes a distributional first-order surrogate for RTN AbsMax-scaled block quantizers, whereas this finite-set construction uses one fixed collection of rows and columns.The nuclear norm supplies a factorization-independent lower bound rather than another transform recipe.Source: §2.5 · p. 4
  • Practical methods including SmoothQuant, QuaRot, SpinQuant, and AffineQuant [1] [6] [8] generally omit outer rotations because free indices can encode tokens, batch elements, or output channels.The inner-only theorem is the closer comparison when those indices must remain fixed.Source: §2.5 · p. 4

3 Noise model and second-moment identity

The section specifies independent subtractive-dither noise and per-vector scalar grids, then derives an exact second-moment identity for product error. It distinguishes the first-order transform objective from the exact error’s higher-order bilinear term, with a caveat for ill-conditioned gauges.

3.1 Transformed factors and scalar grids

  • Each transformed row of A and column of B gets its own range and grid step; the normalized noise variances are cA = 1/[12(2^(bA−1)−1)^2] and cB = 1/[12(2^(bB−1)−1)^2].The 1/12 factor is the variance of unit-width uniform dither; the step is the relevant quantity in the exact model.Source: §3.1 · pp. 4–5
  • Independent, zero-mean subtractive dither on an unbounded lattice is the exact model; finite-grid use is an approximation when a guard band makes clipping negligible.Deterministic round-to-nearest with clipping and correlated errors are excluded.Source: §3.1 · p. 5

3.2 Per-vector second-moment identity

  • The second-moment identity splits expected product error into two leading terms driven by grid ranges and opposite-factor energies, plus a higher-order bilinear correction.This multiplicative structure motivates bounding the product of factor energies by an output-only quantity.Source: §3.2 · p. 5

3.3 High-rate ordering

  • At fixed gauges, Elead is first order in the common variance scale and Ebil is second order, but this ordering need not hold uniformly for ill-conditioned η-dependent gauges.A fixed-gauge sandwich establishes Elead as the sharp first-order transform objective, while Ebil remains part of exact error at fixed grid steps.Source: §3.3 · p. 6

4 A gauge-invariant nuclear lower bound

The section establishes an output-only nuclear lower bound on leading error that holds for every gauge. Its proof combines range–energy and Frobenius–nuclear inequalities; the constructions make the bound tight at Hadamard dimensions and within a factor of two for every K.

4 A gauge-invariant nuclear lower bound

  • The leading error cannot fall below an output-only threshold determined by the nuclear norm of AB, regardless of the product-preserving gauge.The bound applies under the stated stochastic model.Source: §4 · p. 6
  • The proof combines squared range–energy bounds for the factors with a Frobenius–nuclear product inequality, and both component inequalities can be sharp.Simultaneous tightness is established by the later construction, rather than by either inequality alone.Source: §4 · pp. 6–7
  • At Hadamard dimensions the construction makes the leading bound equal at full rank and asymptotically tight below full rank; the normalized DCT-II matches within a factor of two for every K.The complete expected error also has a nonasymptotic lower bound.Source: §4 · p. 7

5 Balancing the Gram matrices

Gram-matrix balancing minimizes factorization energy over invertible inner transformations, attaining the nuclear norm of AB as an infimum. It does not remove coordinate spikes in scalar ranges, and singular Gram matrices can prevent finite-condition-number attainment.

5 Balancing the Gram matrices

  • Gram-matrix balancing compensates for latent directions that carry mismatched energy across the two factors, reducing factorization-energy cost without changing the product.The remaining source of excess error is coordinate concentration that widens scalar grids.Source: §5 · p. 7
  • For arbitrary factors, the infimum of ∥AT∥F ∥T−1B∥F over invertible T equals ∥AB∥*, with attainment in the positive-definite Gram case.The equality condition follows from the trace Cauchy–Schwarz argument and the singular values of AB.Source: §5 · pp. 7–8
  • When either Gram matrix is singular, the balancing value remains an infimum but may not be attained at finite condition number.The regularized transforms that approach the infimum may become ill-conditioned.Source: §5 · pp. 7–8
  • Balancing fixes factorization energy, not scalar range: coordinate spikes can still inflate squared grid steps by as much as K and leave the leading objective above the floor.In the two-by-two example, balanced factors attain the factorization-energy infimum yet the leading objective remains twice the floor.Source: §5 · p. 8

6 Full-gauge and inner-only achievability

Outer rotations make the nuclear lower bound an exact or constant-factor characterization, while inner-only transforms achieve a logarithmic bound through balancing and finite-set flattening.

6 Full-gauge and inner-only achievability

  • The full-gauge construction uses outer rotations to align free indices with output singular vectors and an inner orthogonal matrix to spread retained singular directions.When free indices have application-specific meaning, those outer rotations may be unavailable.Source: §6 · p. 8, §6.1 · p. 8

6.1 Constant achievability over the full gauge

  • At Hadamard dimensions the full-gauge infimum equals the lower bound; a normalized DCT-II gives a factor-at-most-two bound for every K.Finite-gauge attainment is guaranteed when rank(AB) = K; for lower rank, the bound may hold only as an infimum.Source: §6.1 · pp. 8–9

6.2 Logarithmic achievability by inner transforms

  • With outer rotations fixed to the identity, Gram-matrix balancing followed by finite-set flattening gives an inner-only upper bound within C log(K(m+n)) of the nuclear floor.The construction can use a Haar-random or randomized Hadamard rotation; for power-of-two K, the deterministic construction supplies an explicit flattening guarantee.Source: §6.2 · p. 10

7 Deterministic finite-set flattening

For power-of-two dimensions, conditional expectations deterministically choose Hadamard signs that flatten a finite set while retaining the logarithmic guarantee.

Theorem 7.1

  • Theorem 7.1 deterministically selects Hadamard signs so every vector in a finite set satisfies the stated flattening guarantee.The theorem applies to N vectors in dimension d, where d is a power of two.Source: §7 · p. 11

Conditional-expectation construction

  • Conditional expectations choose each sign without increasing an exponential-moment pessimistic estimator, yielding a successful assignment.At a complete assignment, an estimator below one certifies that no coordinate exceeds the threshold.Source: §7 · p. 11

Runtime and scope

  • For N = m+n vectors in dimension K, sign selection takes O((m+n)K^2) exact-real arithmetic operations.The operation count treats exponential evaluations and comparisons as unit-cost; it is not a bit-complexity bound.Source: §7 · p. 11

8 Range-to-energy equivalence and finite-set flatness

Finite-set flatness measures the peak-to-average loss of an inner rotation on a particular product's rows and columns; uniform control of every input instead requires redundancy.

8.1 A finite-set flatness constant

  • The finite-set flatness constant measures the worst peak-to-average loss over the realized vectors, ranging from 1 to K.At 1, each transformed nonzero vector distributes its energy uniformly; this quantity is not leverage score or mutual coherence.Source: §8.1 · p. 12
  • Along the balanced sequence, bounded effective flatness is equivalent to an inner-only construction reaching the nuclear lower bound within a constant factor.The leading error separates factorization energy from the aggregate range-to-energy loss.Source: §8.1 · p. 12

8.2 Why uniform control needs redundancy

  • A square orthogonal transform cannot flatten every input uniformly; suitable redundant frames can provide dimension-independent control at fixed redundancy ratio.Finite-set flattening is instance-specific, whereas uniform control requires redundancy.Source: §8.2 · pp. 12–13

9 Reproducible numerical evaluation

Synthetic evaluations test the predicted full-gauge and inner-only behavior, the output invariance of the lower bound, and a regularized singular limit. The full-gauge reference stays at one, while inner-only ratios depend on the instance and dimension.

9 Reproducible numerical evaluation

  • The evaluation computes expected errors from the analytic leading objective, so sampled dither is unnecessary.The study uses 50 trials per full-rank family and records seeds, environment versions, and artifact hashes for reproduction.Source: §9 · p. 13, §9.1 · p. 13, §9.4 · p. 14

9.2 Generated results

  • The full-gauge baseline has median ratio 1.000 in every family; spiky-instance balancing and deterministic Hadamard flattening reduce the median from 4.538×10^4 to 1.000.For dense diagonal gauges, the original and general-inner-balancing ratios are 1.141×10^4 and 6.307; for dense general gauges, they are 355.643 and 6.389.Source: §9.2 · pp. 13–14, Table 3 · p. 14
  • Across independently refactorized copies of the same output, the nuclear lower bound's maximum relative spread is 9.442 × 10^-16.This is a numerical invariance check, not a statistical estimate.Source: §9.2 · p. 14

9.3 Dimension scaling and conditioning

  • The median inner-Haar ratio rises from 4.480 to 11.933 across the tested dimensions, while the full-gauge baseline remains one.Randomized Hadamard follows the same trend.Source: §9.3 · p. 14
  • At ε = 1.000 × 10^-10, the rank-deficient instance has κ2(Tε) = 8.125 × 10^4 and relative energy-objective excess 2.991 × 10^-5.The sweep illustrates the limiting construction for this instance; dense outer rotations also have substantial application cost unless fused or replaced by structured maps.Source: §9.3 · p. 14

10 Open problems

The remaining questions are theoretical: how tightly inner-only transforms can approach the nuclear-norm floor, how efficiently flattening can be certified, and whether partial-Fourier and broader quantization settings admit sharper guarantees.

Open problems

  • Experiments numerically validate the proved invariants, while the remaining gaps are theoretical.The open questions cover inner-only flatness, faster certification, uniform frames, and the boundary of the stochastic scalar model.Source: §10 · p. 15
  • The inner-only range gap obeys 1 ≤ Γ(A, B) ≤ C log(K(m + n)), but its sharp dimension dependence remains open.The question also asks whether nonorthogonal constructions can improve the finite-set logarithmic bound.Source: §10 · p. 15
  • Deterministic flattening with the guarantee of Theorem 7.1 is open at eO(Nd) time, versus the current O(Nd^2) target.The proposed speedup would narrow the preprocessing gap with randomized Hadamard flattening.Source: §10 · p. 15
  • It remains open whether selected rows of a normalized discrete Fourier matrix yield partial-Fourier frames with dimension-independent Kashin level.This is identified as the classical partial-Fourier Λ1 problem in the Kashin-frame literature.Source: §10 · p. 16
  • The paper leaves open which instance invariant governs finite-rate error with clipping, correlated rounding, or vector and nested-lattice quantization.It also asks whether the nuclear norm remains part of a sharp converse and what dependence on codebook geometry, overload, or factor reuse is needed.Source: §10 · p. 16

11 Conclusion

The conclusion identifies the output nuclear norm as an invariant lower bound and a constructive target for leading product error. Full-gauge constructions approach that floor within a factor of two, while inner-only transforms retain a logarithmic gap.

Conclusion

  • The output nuclear norm is a gauge-invariant lower bound on leading expected squared product error, and full-gauge constructions attain it at Hadamard dimensions or approach it within a factor of two.With inner transforms only, finite-set flattening reaches the bound within a logarithmic factor; deterministic Hadamard sign selection gives the same guarantee for power-of-two K.Source: §11 · p. 16
  • Balancing Gram matrices closes the factorization-energy loss, while regularization covers singular factors.The exact bilinear term also yields the nonasymptotic complete-error lower bound (13).Source: §11 · p. 16
  • Comparing a candidate transform with the nuclear floor separates residual error into factorization energy and finite-set flatness, without simulated quantization.The Kashin interpretation connects uniform control over every possible input with redundant representations; extensions to clipping, correlated errors, and application-constrained transforms remain future work.Source: §11 · p. 16

A Kashin duality and the weak uncertainty principle

The appendix uses polarity to make the geometry behind the Λ1 condition explicit, then connects Kashin representations to a weak uncertainty principle and iterative truncation.

A Kashin duality and the weak uncertainty principle

  • Polarity makes the convex-body geometry behind equation (30) explicit through the bodies' support functions.The passage characterizes polarity as the duality between a convex body and linear functionals bounded by one on it.Source: A Kashin duality and the weak… · p. 17
  • The duality steps reduce equation (30) to the condition Λ1(E) ≤ λ0.The argument uses that F^T is an isometry onto E = range(F^T).Source: A Kashin duality and the weak… · p. 17
  • Lyubarskii and Vershynin obtain such representations from a weak uncertainty principle by iteratively truncating large coefficients and representing the residual.The residual contracts geometrically, yielding Kashin level λ0 = (1 − η)^−1 δ^−1/2 under the stated support-to-norm condition.Source: A Kashin duality and the weak… · p. 17
Loading 2609.05641v1…