Constructing fast approximate eigenspaces with application to the fast graph Fourier transforms

Matrix decomposition techniques Stewart [2000], and specifically eigenvalue decompositions Golub and van der Vorst [2000], are widely used in numerical linear algebra, scientific computing, machine learning, quantum computing and other scientific fields. In general, given no assumptions on the structure of an eigenspace, the eigenvector matrix of a given linear operator of size n n exhibits no advantageous numerical properties and therefore they require O(n 2) operations when performing matrix-vector multiplications. In this paper, we want to perform an approximate eigenvalue decomposition so that we accurately represent the original eigenspace with a new one that also exhibits favorable numerical complexity, for example, it requires only O(n log n) operations when performing matrix-vector multiplication with a generic vector. In such cases, a tradeoff between the accuracy of the approximation and its numerical complexity exists.