Seminar • Algorithms and Complexity • “A Tale of Two Subspaces” [Regev]

Please note: This seminar will take place in DC 3102.

Akshay Ramachandran, Postdoctoral Researcher
Centrum Wiskunde & Informatica

Optimization problems with orthogonality constraints arise in many fields in science and engineering. For example, optimization over subspaces in physics and signal processing, and over rotations in computational geometry. The key step in solving these problems often boils down to understanding the relation between two subspaces. It turns out that this question has a surprisingly elegant answer given by the CS decomposition from numerical linear algebra.

In this talk, we will discuss the CS decomposition in the context of the geodesic geometry of subspaces. This perspective further gives a unifying framework for understanding the various numerical algorithms used to solve problems with orthogonality constraints. As our main illustration, we study the problem of computing eigenspaces of a matrix, giving a rigorous convergence analysis of the well-known power method and its subspace generalization. If time permits, we also present some new results on tractable algorithms for constrained optimization over rotation matrices.

This is joint work with Kevin Shu and Alex Wang.