UC Irvine

The recursive structure of butterfly matrices has been exploited to accelerate common methods in computational linear algebra. This was first developed by D. Stott Parker \cite{Pa95}. Recently, the machine learning community has taken particular interest in these applications. Butterfly structures can now be found integrated into architectures for software used in learning fast solvers for large linear systems and in image recognition, covering tasks such as early cancer identification or smart vehicle navigation \cite{uwBFT, butterflynet, fast_alg}. These new advances have enabled less powerful computing systems, such as in mobile devices or portable smart devices, to effectively utilize computationally heavy tools that were previously unavailable. Although empirical evidence supports the use of butterfly matrices in these newer technologies, the literature on the mathematical theory that justified these results is lacking. Building on research started in \cite{Tr19}, I will give a fuller picture of the numerical, spectral, and group properties of particular ensembles of random butterfly matrices. This document will provide a stronger mathematical foundation to further support the approaches already found in practice and can inform future applications not yet explored.