  We present a fast algorithm for approximate Canonical Correlation Analysis
(CCA). Given a pair of tall-and-thin matrices, the proposed algorithm first
employs a randomized dimensionality reduction transform to reduce the size of
the input matrices, and then applies any CCA algorithm to the new pair of
matrices. The algorithm computes an approximate CCA to the original pair of
matrices with provable guarantees, while requiring asymptotically less
operations than the state-of-the-art exact algorithms.
