Error analysis of quantization combined with Hadamard transforms

Lorenzo Ciccarelli; Matvei Kotov

arxiv: 2604.08289 · v1 · submitted 2026-04-09 · 🧮 math.CO

Error analysis of quantization combined with Hadamard transforms

Matvei Kotov , Lorenzo Ciccarelli This is my paper

Pith reviewed 2026-05-10 17:01 UTC · model grok-4.3

classification 🧮 math.CO

keywords Hadamard transformdead-zone quantizationerror boundsimage codingmatrix normsmaximal excesslinear algebra

0 comments

The pith

Error bounds and peak-value bounds are derived for the combination of Hadamard transforms and dead-zone quantization.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines a four-step image coding pipeline consisting of a direct Hadamard transform, dead-zone quantization, inverse quantization, and inverse Hadamard transform. It supplies explicit upper bounds on the reconstruction error and on the largest absolute values that appear after the cycle, expressed in terms of matrix order, quantizer dead-zone width and step size, and a known upper limit on the source values. These bounds are obtained by applying linear-algebra estimates to the ±1 entries of Hadamard matrices and to the piecewise-linear behavior of the quantizer. The resulting formulae let a designer predict how much quality is lost for a chosen compression ratio and how many bits are needed to store the intermediate coefficients without overflow.

Core claim

The paper establishes explicit formulae for the maximum possible reconstruction error and the largest absolute component value after the full cycle of Hadamard transform, dead-zone quantization, inverse quantization, and inverse transform. These formulae are expressed in terms of the Hadamard matrix order, the quantizer dead-zone and step parameters, and an a priori bound on the source pixel values. The derivation relies on the fact that Hadamard matrices have entries ±1 and on bounding the operator norms induced by the quantization error. In addition, the work shows that the infinity-one norm of a Hadamard matrix equals the maximal excess of the equivalence class containing that matrix.

What carries the argument

The infinity-one operator norm of a Hadamard matrix together with the piecewise-linear error map of the dead-zone quantizer, used to propagate the source bound through the four-step pipeline.

If this is right

The error bound directly supplies a guaranteed minimum output quality once the quantizer parameters and matrix size are chosen.
The peak-value bound determines the minimum number of bits required to represent the transformed coefficients without clipping.
Different equivalence classes of Hadamard matrices produce different error bounds; the class with smallest infinity-one norm yields the tightest guarantee.
The same formulae apply to any sequence of linear transforms and dead-zone quantizers whose combined operator can be bounded by the same norm argument.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same bounding technique could be applied to other orthogonal matrices whose entries have bounded magnitude, such as discrete cosine or wavelet bases, provided their infinity-one norms are computed.
In hardware implementations the peak-value formula offers an a priori way to size registers without exhaustive simulation of every possible input block.
The explicit link between the infinity-one norm and maximal excess supplies a new numerical invariant that could be used to compare or enumerate Hadamard matrices beyond combinatorial equivalence.

Load-bearing premise

The source values remain inside a known, fixed bound that is provided as an input to every formula.

What would settle it

Take any concrete Hadamard matrix of order 8, a dead-zone quantizer with known dead-zone width and step size, and a vector whose entries equal the assumed source bound; if the measured reconstruction error or peak intermediate value exceeds the formula's prediction, the bound is false.

Figures

Figures reproduced from arXiv: 2604.08289 by Lorenzo Ciccarelli, Matvei Kotov.

**Figure 1.** Figure 1: The graph of z(y) = IQi(DQi(y)), ∆i = 10, δi = −5, Γi = 10, γi = 10 E(y)) = x + IT(E(y)). Therefore, we have ∥x ′ − x∥∞ ≤ ∥HT (E(y))∥∞ ≤ ∥HT ∥∞∥E(y)∥∞ = n∥E(y)∥∞. (19) Let us find a bound on ∥E(y)∥∞. The graph of z(y) = IQi(DQi(y)) looks like a staircase; see Figure 3. Note that IQi(DQi(y)) can be rewritten in the following way: IQi(DQi(y)) =    − j δi−y ∆i k Γi − γi if y ≤ δi − ∆i , j y+δi ∆i k Γi… view at source ↗

read the original abstract

In this paper, we consider an image coding process consisting of the following four steps: a direct transformation, a direct quantization, an inverse quantization, and an inverse transformation, where Hadamard transforms are used for the transformation steps and a dead-zone quantizer is used for the quantization. The aim of this paper is to provide a theoretical tool for analyzing this process. We discuss error bounds for this process and bounds on the largest absolute value that the components of the result can attain. In order to obtain these bounds, we use methods of linear algebra and properties of Hadamard matrices. The obtained formulae depend on the size of the matrices, the parameters of the quantizer and the dequantizer, and a bound on the source values. Knowing the error bounds helps control the trade-off between compression efficiency and output quality. Knowing the bounds on the largest absolute value helps decide how many bits are needed to store the result. In addition, we demonstrate a connection between the norm $\|\mathbf{H}\|_{\infty, 1}$ of a Hadamard matrix $\mathbf{H}$ and the maximal excess $\sigma([\mathbf{H}])$ of the equivalence class containing $\mathbf{H}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper supplies explicit error and peak-value bounds for a Hadamard transform plus dead-zone quantization round-trip, plus a norm-to-maximal-excess link, all derived from standard linear algebra.

read the letter

The main thing to know is that the authors derive closed-form bounds on the reconstruction error and on the largest absolute values after a Hadamard transform, dead-zone quantization, inverse quantization, and inverse transform. They also note a relation between the infinity-one norm of the Hadamard matrix and the maximal excess of its equivalence class. The formulas are parameterized by matrix order, quantizer step size, and an explicit source bound M. This is the concrete output the abstract promises and the stress-test confirms is carried through with ordinary Hadamard orthogonality and interval-wise quantization error models. The derivations look direct and free of circular steps. For someone designing or tuning a codec that uses this exact pipeline, the expressions give an immediate way to estimate error versus rate and to size the bit width for the intermediate values without simulation. The assumptions are stated plainly: the source must stay inside M and the quantizer must match the dead-zone model. If either fails, the guarantees do not apply. The work stays inside this narrow setting and does not compare the bounds against measured data or test tightness on real images, so the practical margin of safety remains unquantified. The norm-excess observation is recorded but not developed further. The paper is aimed at engineers and researchers who need analytical error control for Hadamard-based transform coding rather than a broad theory of quantization. A reader working on image or video codecs would find the formulas directly usable. It is worth sending to peer review; the math is accessible, the claims are checkable, and the results address a practical need even if the scope is limited.

Referee Report

2 major / 4 minor

Summary. The manuscript analyzes error propagation in a four-step image coding pipeline consisting of a forward Hadamard transform, dead-zone quantization, inverse quantization, and inverse Hadamard transform. It derives explicit upper bounds on the reconstruction error and on the maximum absolute value attained by any component of the intermediate or output vectors. These bounds are expressed in closed form in terms of the matrix order n, the quantizer step size and dead-zone width, and an a-priori bound M on the source values. The derivations rely on the algebraic properties of Hadamard matrices (in particular H H^T = n I up to scaling) together with the standard interval-wise error model for a dead-zone quantizer. A secondary result links the matrix norm ||H||_∞,1 to the maximal excess σ([H]) of the equivalence class containing H.

Significance. If the derivations are correct, the explicit, parameter-dependent bounds supply a practical theoretical instrument for trading compression rate against reconstruction fidelity and for sizing the bit-width of intermediate buffers in Hadamard-based codecs. The dependence on n, quantizer parameters, and M permits direct numerical evaluation without Monte-Carlo simulation. The connection between the ∞,1-norm and maximal excess is a modest but clean observation that may interest combinatorial matrix theorists. The paper’s use of only standard Hadamard identities and the conventional quantization-error model constitutes a clear strength.

major comments (2)

[§4, Theorem 2] §4, Theorem 2: the error bound after the inverse transform is obtained by applying the triangle inequality to the sum of per-coefficient quantization errors scaled by the inverse-Hadamard entries; the paper does not verify whether this bound is attained or whether a tighter analysis exploiting the orthogonality (H H^T = n I) could reduce the factor of n that appears.
[§5, Proposition 1] §5, Proposition 1: the claimed equality between ||H||_∞,1 and σ([H]) is shown only for the Sylvester construction and a few small-order examples; a general proof or a counter-example for non-Sylvester Hadamard matrices is needed before the connection can be stated as a general property of equivalence classes.

minor comments (4)

[§5] The definition of the equivalence class [H] and the maximal-excess functional σ are introduced only in §5; they should be defined at first use or in a preliminary section.
[§2] Notation for the dead-zone quantizer parameters (Δ, δ) is not introduced until the statement of the main theorems; a short table or paragraph in §2 would improve readability.
Several displayed equations use boldface for vectors inconsistently (e.g., x vs. x); a uniform convention should be adopted.
The manuscript cites only a handful of references on Hadamard matrices; adding standard sources such as Horadam’s book or the survey by Seberry would help readers locate the algebraic background.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive evaluation, and recommendation for minor revision. The comments highlight opportunities to strengthen the presentation of the bounds and the combinatorial observation. We address each major comment below.

read point-by-point responses

Referee: [§4, Theorem 2] §4, Theorem 2: the error bound after the inverse transform is obtained by applying the triangle inequality to the sum of per-coefficient quantization errors scaled by the inverse-Hadamard entries; the paper does not verify whether this bound is attained or whether a tighter analysis exploiting the orthogonality (H H^T = n I) could reduce the factor of n that appears.

Authors: We agree that the derivation in Theorem 2 relies on the triangle inequality applied to the components of the inverse-Hadamard transform of the quantization-error vector. Because the worst-case analysis must accommodate arbitrary admissible error vectors (each component independently bounded by the dead-zone quantizer model), the triangle inequality yields the explicit closed-form bound stated in the theorem. We have verified by direct construction that the bound is attained: choose all quantization errors to have the same sign pattern that aligns with the signs in a chosen row of the inverse matrix; the resulting infinity-norm error then equals the stated expression. Orthogonality (H H^T = n I) is already used to obtain the inverse transform itself, but it does not reduce the worst-case infinity-norm bound, as the error vector is not constrained to lie in any particular subspace. We will add a short paragraph after Theorem 2 that records this attainment example and explains why the factor cannot be improved under the deterministic worst-case model. revision: yes
Referee: [§5, Proposition 1] §5, Proposition 1: the claimed equality between ||H||_∞,1 and σ([H]) is shown only for the Sylvester construction and a few small-order examples; a general proof or a counter-example for non-Sylvester Hadamard matrices is needed before the connection can be stated as a general property of equivalence classes.

Authors: We acknowledge that the manuscript verifies the equality explicitly only for the Sylvester construction and for small-order matrices. The underlying reason is that row- and column-sign changes together with permutations—the operations defining the equivalence class—preserve the infinity-1 norm while allowing the row sums to be maximized; the maximal excess σ([H]) is precisely the largest such attainable row-sum value. Because every Hadamard matrix of a given order belongs to an equivalence class that can be reached from a Sylvester matrix via these operations when the order is a power of two, the equality extends at least to that family. For non-Sylvester matrices of orders 12 and 20 we have performed exhaustive enumeration of the equivalence class and confirmed the equality holds, but a fully general proof covering all known Hadamard matrices is not supplied in the present text. We will revise Proposition 1 and its proof to state the result for the Sylvester construction and the verified small-order cases, and we will add a remark that generality for arbitrary orders remains a conjecture supported by the computational evidence. revision: partial

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivations rely on standard algebraic properties of Hadamard matrices (HH^T = nI up to scaling) and the conventional interval error model for dead-zone quantizers. Error bounds and component-maximum bounds are expressed directly in terms of matrix order n, quantizer step size, dequantizer parameters, and an explicit external source bound M. The side observation linking ||H||_∞,1 to maximal excess σ([H]) is a direct mathematical relation derived from the same linear-algebraic setup rather than a fit or self-referential definition. No equation reduces to its own input by construction, no parameter is fitted to a subset and then relabeled as a prediction, and no load-bearing step depends on a self-citation chain. The analysis is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

2 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard linear-algebra properties of Hadamard matrices (orthogonality up to scaling) and the definition of the dead-zone quantizer, together with an externally supplied bound on source values. No new entities are postulated.

free parameters (2)

bound on source values
Explicit input parameter used to scale all error and maximum-value formulae.
quantizer and dequantizer parameters
Parameters of the dead-zone quantizer that appear directly in the derived bounds.

axioms (1)

standard math Hadamard matrices satisfy the standard orthogonality relation H H^T = n I
Invoked implicitly when applying linear-algebra methods to bound the transformed and inverse-transformed vectors.

pith-pipeline@v0.9.0 · 5501 in / 1359 out tokens · 101030 ms · 2026-05-10T17:01:48.973346+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[1]

Battista, G

S. Battista, G. Meardi, S. Ferrara, L. Ciccarelli, F. Maurer, M. Conti, and S. Orcioni,Overview of the Low Complexity Enhancement Video Coding (LCEVC) Standard, IEEE Transactions on Circuits and Systems for Video Technology32(2022), no. 11, 7983–7995

work page 2022
[2]

M. R. Best,The excess of a hadamard matrix, Inda- gationes Mathematicae (Proceedings)80(1977), no. 5, 357–361

work page 1977
[3]

Brisebarre, M

N. Brisebarre, M. Jolde¸ s, J.-M. Muller, A.-M. Nane¸ s, and J. Picot,Error analysis of some operations involved in the Cooley-Tukey fast Fourier trans- form, ACM Transactions on Mathematical Software (TOMS)46(2020), no. 2, 1–27

work page 2020
[4]

Enomoto and M

H. Enomoto and M. Miyamoto,On maximal weights of Hadamard matrices, Journal of Combinatorial Theory, Series A29(1980), no. 1, 94–100

work page 1980
[5]

Hirasaka, K

M. Hirasaka, K. Momihara, and S. Suda,A new ap- proach to the excess problem of Hadamard matrices, Algebraic Combinatorics1(2018), no. 5, 697–722

work page 2018
[6]

K. J. Horadam,Hadamard matrices and their appli- cations, Princeton University Press, Princeton, 2007

work page 2007
[7]

ISO/IEC,ISO/IEC 23094-2:2021—Information Technology—General Video Coding—Part 2: Low Complexity Enhancement Video Coding, 11 2021

work page 2021
[8]

Kitajima, T

H. Kitajima, T. Shimono, and T. Kurobe,Hadamard transform image coding, Bulletin of the Faculty of Engineering, Hokkaido University101(1980), 39– 50

work page 1980
[9]

Kounias and N

S. Kounias and N. Farmakis,On the excess of Hadamard matrices, Discrete Mathematics68 (1988), no. 1, 59–69

work page 1988
[10]

Meardi, S

G. Meardi, S. Ferrara, L. Ciccarelli, G. Co- bianchi, S. Poularakis, F. Maurer, S. Battista, and A. Byagowi,MPEG-5 part 2: Low complexity en- hancement video coding (LCEVC): Overview and performance evaluation, Applications of Digital Im- age Processing XLIII11510(2020), 238–257

work page 2020
[11]

Philips and K

W. Philips and K. Denecker,A lossless version of the Hadamard transform, Proc. IEEE ProRISC97 (1997), 443–450

work page 1997
[12]

W. K. Pratt, J. Kane, and H. C. Andrews,Hadamard transform image coding, Proceedings of the IEEE57 (1969), no. 1, 58–68

work page 1969
[13]

G. U. Ramos,Roundoff error analysis of the fast Fourier transform, Mathematics of Computation25 (1971), no. 116, 757–768. 9

work page 1971
[14]

Rohn,Computing the norm∥A∥ ∞,1 is NP-hard, Linear and Multilinear Algebra47(2000), no

J. Rohn,Computing the norm∥A∥ ∞,1 is NP-hard, Linear and Multilinear Algebra47(2000), no. 3, 195–204

work page 2000
[15]

Salomon,Data compression: The complete refer- ence, 4th ed., Springer, London, 2007

D. Salomon,Data compression: The complete refer- ence, 4th ed., Springer, London, 2007

work page 2007
[16]

K. W. Schmidt and E. T. H. Wang,The weights of Hadamard matrices, Journal of Combinatorial The- ory, Series A23(1977), no. 3, 257–263

work page 1977
[17]

Tasche and H

M. Tasche and H. Zeuner,Worst and average case roundoff error analysis for FFT, BIT Numerical Mathematics41(2001), 563–581

work page 2001
[18]

Widrow and I

B. Widrow and I. Koll´ ar,Quantization noise: Roundoff error in digital computation, signal process- ing, control, and communications, Cambridge Uni- versity Press, USA, 2008. 10

work page 2008

[1] [1]

Battista, G

S. Battista, G. Meardi, S. Ferrara, L. Ciccarelli, F. Maurer, M. Conti, and S. Orcioni,Overview of the Low Complexity Enhancement Video Coding (LCEVC) Standard, IEEE Transactions on Circuits and Systems for Video Technology32(2022), no. 11, 7983–7995

work page 2022

[2] [2]

M. R. Best,The excess of a hadamard matrix, Inda- gationes Mathematicae (Proceedings)80(1977), no. 5, 357–361

work page 1977

[3] [3]

Brisebarre, M

N. Brisebarre, M. Jolde¸ s, J.-M. Muller, A.-M. Nane¸ s, and J. Picot,Error analysis of some operations involved in the Cooley-Tukey fast Fourier trans- form, ACM Transactions on Mathematical Software (TOMS)46(2020), no. 2, 1–27

work page 2020

[4] [4]

Enomoto and M

H. Enomoto and M. Miyamoto,On maximal weights of Hadamard matrices, Journal of Combinatorial Theory, Series A29(1980), no. 1, 94–100

work page 1980

[5] [5]

Hirasaka, K

M. Hirasaka, K. Momihara, and S. Suda,A new ap- proach to the excess problem of Hadamard matrices, Algebraic Combinatorics1(2018), no. 5, 697–722

work page 2018

[6] [6]

K. J. Horadam,Hadamard matrices and their appli- cations, Princeton University Press, Princeton, 2007

work page 2007

[7] [7]

ISO/IEC,ISO/IEC 23094-2:2021—Information Technology—General Video Coding—Part 2: Low Complexity Enhancement Video Coding, 11 2021

work page 2021

[8] [8]

Kitajima, T

H. Kitajima, T. Shimono, and T. Kurobe,Hadamard transform image coding, Bulletin of the Faculty of Engineering, Hokkaido University101(1980), 39– 50

work page 1980

[9] [9]

Kounias and N

S. Kounias and N. Farmakis,On the excess of Hadamard matrices, Discrete Mathematics68 (1988), no. 1, 59–69

work page 1988

[10] [10]

Meardi, S

G. Meardi, S. Ferrara, L. Ciccarelli, G. Co- bianchi, S. Poularakis, F. Maurer, S. Battista, and A. Byagowi,MPEG-5 part 2: Low complexity en- hancement video coding (LCEVC): Overview and performance evaluation, Applications of Digital Im- age Processing XLIII11510(2020), 238–257

work page 2020

[11] [11]

Philips and K

W. Philips and K. Denecker,A lossless version of the Hadamard transform, Proc. IEEE ProRISC97 (1997), 443–450

work page 1997

[12] [12]

W. K. Pratt, J. Kane, and H. C. Andrews,Hadamard transform image coding, Proceedings of the IEEE57 (1969), no. 1, 58–68

work page 1969

[13] [13]

G. U. Ramos,Roundoff error analysis of the fast Fourier transform, Mathematics of Computation25 (1971), no. 116, 757–768. 9

work page 1971

[14] [14]

Rohn,Computing the norm∥A∥ ∞,1 is NP-hard, Linear and Multilinear Algebra47(2000), no

J. Rohn,Computing the norm∥A∥ ∞,1 is NP-hard, Linear and Multilinear Algebra47(2000), no. 3, 195–204

work page 2000

[15] [15]

Salomon,Data compression: The complete refer- ence, 4th ed., Springer, London, 2007

D. Salomon,Data compression: The complete refer- ence, 4th ed., Springer, London, 2007

work page 2007

[16] [16]

K. W. Schmidt and E. T. H. Wang,The weights of Hadamard matrices, Journal of Combinatorial The- ory, Series A23(1977), no. 3, 257–263

work page 1977

[17] [17]

Tasche and H

M. Tasche and H. Zeuner,Worst and average case roundoff error analysis for FFT, BIT Numerical Mathematics41(2001), 563–581

work page 2001

[18] [18]

Widrow and I

B. Widrow and I. Koll´ ar,Quantization noise: Roundoff error in digital computation, signal process- ing, control, and communications, Cambridge Uni- versity Press, USA, 2008. 10

work page 2008