Unverified Re-invented 2026

Hadamard-exact binary feature sketch

Implementation & benchmark of arXiv:2608.25058 — On exact discretization of the $L_2$-norm in the space spanned by the first $N$ Rademacher functions

Usefulness7/10

Difficulty5/10

Novelty5/10

Architecture Memory Speedup Accuracy Mlp Embedding Memory Inference speedup Linear algebra Harmonic analysis Combinatorics

Source paper: On exact discretization of the $L_2$-norm in the space spanned by the first $N$ Rademacher functions arXiv:2608.25058 ⓘ · analyzed Aug 29, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Build a fixed binary-sign feature layer whose evaluation can be restricted to N carefully selected sign patterns while preserving the squared L2 norm of every feature vector in the first-N Rademacher subspace exactly. Use a Hadamard matrix when order N exists; otherwise use N+1 patterns and positive weights satisfying the same isotropy equation.

Formulas

$$\int_{\Omega}f^{2}\,d\mu=\sum_{j=1}^{m}\lambda_{j}f^{2}(\xi^{j})$$

$$A\Lambda A^{\mathsf T}=I_N,\qquad A_{l,k}=r_l(\Delta_{i_k}),\qquad \Lambda=\operatorname{diag}(\lambda_1,\ldots,\lambda_m)$$

$$\int_0^1\left(\sum_{l=0}^{N-1}c_l r_l(x)\right)^2dx=\sum_{k=1}^{m}\lambda_k\left(\sum_{l=0}^{N-1}c_l A_{l,k}\right)^2$$

$$HH^{\mathsf T}=NI_N\quad\Longrightarrow\quad H\left(\frac{1}{N}I_N\right)H^{\mathsf T}=I_N$$

Mathematical statement

Let r_0,...,r_{N-1} be the first N Rademacher functions on [0,1], each constant with value plus or minus 1 on dyadic intervals Delta_0,...,Delta_{2^N-1}. For f(x)=sum_{l=0}^{N-1} c_l r_l(x), define A in {+1,-1}^{N times m} by A_{l,k}=r_l(Delta_{i_k}), where i_k are selected cells, and Lambda=diag(lambda_1,...,lambda_m). Exact discretization is A Lambda A^T=I_N, equivalently the integral of f squared equals sum_k lambda_k f(xi_k)^2 for every f in the Rademacher span. If H is a Hadamard matrix with H H^T=N I_N, choosing A=H and lambda_k=1/N gives exact norm preservation with m=N. The paper states that the minimum number of nodes is N when a Hadamard matrix of order N exists, and N+1 otherwise.

Implementation notes

Integrate this at an embedding or MLP bottleneck that currently evaluates a large binary-sign feature bank. Let the input be u in R^d, choose an integer N, and construct a fixed sign code A in {+1,-1}^{N times m} from a Hadamard matrix when possible. The module computes coefficients c=g_theta(u) in R^N and represents the feature function by sign evaluations z_k=sum_l A_{l,k}c_l. Retain only the m=N Hadamard columns and set z_tilde_k=z_k divided by sqrt(N); then sum_k z_tilde_k squared equals the coefficient norm exactly. Pseudocode: c = encoder(u); z = transpose(A) @ c; z = sqrt(lambda) * z; energy = (z*z).sum(); y = decoder(z). If N is not a Hadamard order, search over N+1 sign columns and solve A diag(lambda) A^T=I_N for nonnegative weights, using softplus weights and a matrix-residual penalty if necessary. The exact part comes from the isotropy identity; decoder reconstruction error is empirical. First test on CIFAR-10 with a small MLP replacing a 2^N-wide binary-feature layer for N=8, 12, and 16. Compare dense, random-sign, and Hadamard variants at equal parameter count. Success means lower feature memory and wall-clock cost with no accuracy loss on data represented by the learned coefficient subspace.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.