On spectral and numerical properties of random butterfly matrices

Abstract

Spectral and numerical properties of classes of random orthogonal butterfly matrices, as introduced by Parker (1995), are discussed, including the uniformity of eigenvalue distributions. These matrices are important because the matrix-vector product with an $N$-dimensional vector can be performed in $O(N\log N)$ operations. And in the simplest situation, these random matrices coincide with Haar measure on a subgroup of the orthogonal group. We discuss other implications in the context of randomized linear algebra.

Fixed a few typos and added some additional comments

References in corpus (1)

• Fast, Robust and Non-convex Subspace Recovery

Cited by in corpus (4)

• Randomized Numerical Linear Algebra: Foundations & Algorithms
• Growth factors of random butterfly matrices and the stability of avoiding pivoting
• Generalizing Random Butterfly Transforms to Arbitrary Matrix Sizes
• Distribution of the number of pivots needed using Gaussian elimination with partial pivoting on random matrices