Randomized sketches for kernel CCA. (July 2020) - Lian, Heng; Zhang, Fode; Lu, Wenqi
Abstract: Kernel canonical correlation analysis (KCCA) is a popular tool as a nonlinear extension of canonical correlation analysis. Consistency and optimal convergence rate have been established in the literature. However, the time complexity of KCCA scales as O ( n 3 ) and is thus prohibitive when n is large. We propose an m -dimensional randomized sketches approach for KCCA with m < < n, based on the recent work on randomized sketches for kernel ridge regression (KRR). Technically we establish our theoretical results relying on an interesting connection between KCCA and KRR by utilizing a novel "duality tracking" device that alternates between the infinite-dimensional operator-theory-based view of KCCA and the finite-dimensional kernel-matrix-based view.