Parallelized Computation and Backpropagation Under Angle-Parametrized Orthogonal Matrices

We present a methodology for parallel acceleration of learning in the\npresence of matrix orthogonality and unitarity constraints of interest in\nseveral branches of machine learning. We show how an apparently sequential\nelementary rotation parametrization can be restructured into blocks of\ncommutative operations using a well-known tool for coloring the edges of\ncomplete graphs, in turn widely applied to schedule round-robin\n(all-against-all) sports tournaments. The resulting decomposition admits an\nalgorithm to compute a fully-parametrized orthogonal matrix from its rotation\nparameters in $O(n)$ sequential steps and one to compute the gradient of a\ntraining loss with respect to its parameters in $O(n\\log n)$ steps. We discuss\nparametric restrictions of interest to generative modeling and present\npromising performance results with a prototype GPU implementation.\n