Randomized Riemannian Preconditioning for Quadratically Constrained Problems
summary
Randomized sketching builds an approximate Riemannian metric for CCA by replacing Sigma_xx and Sigma_yy with cheaply formed MX and MY (via subspace embedding or dominant-subspace approximation), so Riemannian-gradient and trust-region steps avoid expensive inverses. The method acts as a preconditioner for manifold optimization, keeps each iteration to one pass over X/Y, achieves exponential convergence governed by the eigen-gap, and empirically cuts iterations dramatically (baseline ~205 iterations, exact-metric ~47, approximations close behind).
AI-written summary · about
chapters (14)
- 0:00Intro
- 3:27Two Approaches for Introducing Randomization in NLA
- 7:29Executive Summary
- 8:49Regularized Canonical Correlations Analysis CCA
- 11:23Solving CCA
- 13:30Alternating Least Squares Algorithm (Golub and Zha 1995)
- 18:05Alternating Least Squares - Costs
- 18:48Riemannian Optimization
- 22:07ALS is Riemannian Steepest Descent
- 24:17Riemannian Preconditioning (Mishra-Sepulchre '16): Change the Metric
- 25:07Sketching Based Preconditioning Strategies
- 26:08Preliminary Experimental Results
- 28:12Second Order Methods
- 29:04Conclusions and Future Work
related talks
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
01h 27mPast, Present and Future of Randomized Numerical Linear Algebra I
01h 04mSketching and Randomized Linear Algebra
33mRobust Sketching for Large-Scale Multi-Instance Conic Optimization
48mRandomized Numerical Linear Algebra
53mSketching and Projecting
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
29mImplementing Randomized Matrix Algorithms in Parallel and Distributed Environments