Coordinate-descent for learning orthogonal matrices through Givens rotations

Uri Shalit, Gal Chechik
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(1):548-556, 2014.

Abstract

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 orthogonality, and correcting orthogonality usually costs a large amount of computation. Here we propose a framework for optimizing orthogonal matrices, that is the parallel of coordinate-descent in Euclidean spaces. It is based on \em Givens-rotations, a fast-to-compute operation that affects a small number of entries in the learned matrix, and preserves orthogonality. We show two applications of this approach: an algorithm for tensor decompositions used in learning 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-shalit14, title = {Coordinate-descent for learning orthogonal matrices through Givens rotations}, author = {Shalit, Uri and Chechik, Gal}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {548--556}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/shalit14.pdf}, url = {https://proceedings.mlr.press/v32/shalit14.html}, abstract = {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 orthogonality, and correcting orthogonality usually costs a large amount of computation. Here we propose a framework for optimizing orthogonal matrices, that is the parallel of coordinate-descent in Euclidean spaces. It is based on \em Givens-rotations, a fast-to-compute operation that affects a small number of entries in the learned matrix, and preserves orthogonality. We show two applications of this approach: an algorithm for tensor decompositions used in learning 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.} }
Endnote
%0 Conference Paper %T Coordinate-descent for learning orthogonal matrices through Givens rotations %A Uri Shalit %A Gal Chechik %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-shalit14 %I PMLR %P 548--556 %U https://proceedings.mlr.press/v32/shalit14.html %V 32 %N 1 %X 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 orthogonality, and correcting orthogonality usually costs a large amount of computation. Here we propose a framework for optimizing orthogonal matrices, that is the parallel of coordinate-descent in Euclidean spaces. It is based on \em Givens-rotations, a fast-to-compute operation that affects a small number of entries in the learned matrix, and preserves orthogonality. We show two applications of this approach: an algorithm for tensor decompositions used in learning 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.
RIS
TY - CPAPER TI - Coordinate-descent for learning orthogonal matrices through Givens rotations AU - Uri Shalit AU - Gal Chechik BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-shalit14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 1 SP - 548 EP - 556 L1 - http://proceedings.mlr.press/v32/shalit14.pdf UR - https://proceedings.mlr.press/v32/shalit14.html AB - 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 orthogonality, and correcting orthogonality usually costs a large amount of computation. Here we propose a framework for optimizing orthogonal matrices, that is the parallel of coordinate-descent in Euclidean spaces. It is based on \em Givens-rotations, a fast-to-compute operation that affects a small number of entries in the learned matrix, and preserves orthogonality. We show two applications of this approach: an algorithm for tensor decompositions used in learning 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. ER -
APA
Shalit, U. & Chechik, G.. (2014). Coordinate-descent for learning orthogonal matrices through Givens rotations. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(1):548-556 Available from https://proceedings.mlr.press/v32/shalit14.html.

Related Material