Spectral norm bound for the product of random Fourier-Walsh matrices

Libin Zhu; Damek Davis; Dmitriy Drusvyatskiy; Maryam Fazel

paper

Spectral norm bound for the product of random Fourier-Walsh matrices

arXiv:2504.03148

Abstract

We consider matrix products of the form $A_{1} (A_{2} A_{2})^{⊤} \dots (A_{m} A_{m}^{⊤}) A_{m + 1}$ , where $A_{i}$ are normalized random Fourier-Walsh matrices. We identify an interesting polynomial scaling regime when the operator norm of the expected matrix product tends to zero as the dimension tends to infinity.

18 pages, 2 figures