Timezone: »
We develop effective approximation methods for unitary matrices. In our formulation, a unitary matrix is represented as a product of rotations in two-dimensional subspaces, so-called Givens rotations. Instead of the quadratic dimension dependence when applying a dense matrix, applying such an approximation scales with the number factors, each of which can be implemented efficiently. Consequently, in settings where an approximation is once computed and then applied many times, such an effective representation becomes advantageous. Although efficient Givens factorizations are not possible for generic unitary operators, we show that minimizing a sparsity-inducing objective with a coordinate descent algorithm on the unitary group yields good factorizations for structured matrices. Canonical applications of such a setup are orthogonal basis transforms. We demonstrate that our methods improve the approximate representation of the graph Fourier transform, the matrix obtained when diagonalizing a graph Laplacian.
Author Information
Thomas Frerix (Technical University of Munich)
Joan Bruna (New York University)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: Approximating Orthogonal Matrices with Effective Givens Factorization »
Thu Jun 13th 01:30 -- 04:00 AM Room Pacific Ballroom
More from the Same Authors
-
2020 Poster: Extra-gradient with player sampling for faster convergence in n-player games »
Samy Jelassi · Carles Domingo-Enrich · Damien Scieur · Arthur Mensch · Joan Bruna -
2019 Workshop: Theoretical Physics for Deep Learning »
Jaehoon Lee · Jeffrey Pennington · Yasaman Bahri · Max Welling · Surya Ganguli · Joan Bruna -
2019 Poster: Neuron birth-death dynamics accelerates gradient descent and converges asymptotically »
Grant Rotskoff · Samy Jelassi · Joan Bruna · Eric Vanden-Eijnden -
2019 Oral: Neuron birth-death dynamics accelerates gradient descent and converges asymptotically »
Grant Rotskoff · Samy Jelassi · Joan Bruna · Eric Vanden-Eijnden