Coordinate-descent for learning orthogonal matrices through Givens rotations
Uri Shalit, Gal Chechik · 2014
Optimizing over the set of orthogonal matrices is a central component in problems like sparse-PCA or tensor decomposition. Unfortunately, such optimization is hard since simple operations on orthogonal matrices easily break orthogonal-ity, and correcting orthogonality usually costs a large amount of computation. Here we propose a framework for optimiz-ing orthogonal matrices, that is the parallel of coordinate-descent in Euclidean spaces. It is based on Givens-rotations, a fast-to-compute op-eration that affects a small number of entries in the learned matrix, and preserves orthogonality. We show two applications of this approach: an al-gorithm for tensor decompositions used in learn-ing mixture models, and an algorithm for sparse-PCA. We study the parameter regime where a Givens rotation approach converges faster and achieves a superior model on a genome-wide brain-wide mRNA expression dataset. 1.