Generating Hadamard matrices with transformers
We present a new method for constructing Hadamard matrices that combines transformer neural networks with local search in the PatternBoost framework. Our approach is designed for extremely sparse combinatorial search problems and is particularly effective for Hadamard matrices of Goethals--Seidel type, where Fourier methods permit fast scoring and optimisation. For orders between 100 and 200, it produces large numbers of inequivalent Hadamard matrices, and for larger orders, it succeeds where local search from random initialisation fails. The largest example found by our method has order 252. In addition to these new constructions, our experiments reveal that the transformer can discover and exploit useful hidden symmetry in the search space.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Equivariant neural networks for recovery of Hadamard matrices
We propose a message passing neural network architecture designed to be equivariant to column and row permutations of a matrix. We illustrate its advantages over traditional architectures like multi-layer perceptrons (ML…
Combinatorial OptimizationGradual Binary Search and Dimension Expansion : A general method for activation quantization in LLMs
Large language models (LLMs) have become pivotal in artificial intelligence, demonstrating strong capabilities in reasoning, understanding, and generating data. However, their deployment on edge devices is hindered by th…
QuantizationComputational ghost imaging with hybrid transforms by integrating Hadamard, discrete cosine, and Haar matrices
A scenario of ghost imaging with hybrid transform approach is proposed by integrating Hadamard, discrete cosine, and Haar matrices. The measurement matrix is formed by the Kronecker product of the two different transform…
Image CompressionComputational Resolution of Hadamard Product Factorization for $4 \times 4$ Matrices
We computationally resolve an open problem concerning the expressibility of $4 \times 4$ full-rank matrices as Hadamard products of two rank-2 matrices. Through exhaustive search over $\mathbb{F}_2$, we identify 5,304 co…
Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform
Random projections or sketching are widely used in many algorithmic and learning contexts. Here we study the performance of iterative Hessian sketch for least-squares problems. By leveraging and extending recent results …
Dimensionality Reduction