Asymptotically optimal approximate Hadamard matrices
Boris Alexeev, John Jasper, Dustin G. MixonAbstract
An approximate Hadamard matrix is a well‐conditioned square matrix with all entries in . We measure the quality of a matrix by its condition number, that is, the ratio of its largest and smallest singular values. We prove that for any fixed positive , every sufficiently large dimension admits an approximate Hadamard matrix with condition number at most . In particular, the smallest possible condition number tends to as . Conversely, there exists an absolute constant such that for every sufficiently large , every matrix with entries in has condition number at least . Along the way, we resolve a problem of Jaming and Matolcsi concerning flat orthogonal matrices, and we conclude by describing several explicit infinite families of approximate Hadamard matrices.