# Hadamard-exact binary feature sketch

- ID: 154
- Canonical URL: https://synthcore.org/idea/154/hadamard-exact-binary-feature-sketch
- API JSON: https://synthcore.org/api/idea/154.json
- API Markdown: https://synthcore.org/api/idea/154.md
- Verification status: unverified
- Source: [arXiv:2608.25058](https://arxiv.org/abs/2608.25058)
- Category: architecture
- Solves: memory, speedup, accuracy
- ML areas: mlp, embedding, memory, inference-speedup
- Math tags: linear-algebra, harmonic-analysis, combinatorics
- Ratings: usefulness 7/10; difficulty 5/10; novelty 5/10

## 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.

## 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.

## Key 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$$

## 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.

## Disclaimer

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