We present an efficient stochastic algorithm (RSG+) for canonical correlation analysis (CCA) using a reparametrization of the projection matrices. We show how this reparametrization (into structured matrices), simple in hindsight, directly presents an opportunity to repurpose/adjust mature techniques for numerical optimization on Riemannian manifolds. Our developments nicely complement existing methods for this problem which either require O(d 3) time complexity per iteration with convergence rate (where d is the dimensionality) or only extract the top 1 component with convergence rate. In contrast, our algorithm offers an improvement: it achieves O(d 2 k) runtime complexity per iteration for extracting the top k canonical components with convergence rate. While our paper focuses more on the formulation and the algorithm, our experiments show that the empirical behavior on common datasets is quite promising. We also explore a potential application in training fair models with missing sensitive attributes.