Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition
We study $k$-GenEV, the problem of finding the top $k$ generalized eigenvectors, and $k$-CCA, the problem of finding the top $k$ vectors in canonical-correlation analysis. We propose algorithms $\mathtt{LazyEV}$ and $\mathtt{LazyCCA}$ to solve the two problems with running times linearly dependent on the input size and on $k$. Furthermore, our algorithms are DOUBLY-ACCELERATED: our running times depend only on the square root of the matrix condition number, and on the square root of the eigengap. This is the first such result for both $k$-GenEV or $k$-CCA. We also provide the first gap-free results, which provide running times that depend on $1/\sqrt{\varepsilon}$ rather than the eigengap.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Accelerated graph-based spectral polynomial filters
Graph-based spectral denoising is a low-pass filtering using the eigendecomposition of the graph Laplacian matrix of a noisy signal. Polynomial filtering avoids costly computation of the eigendecomposition by projections…
DenoisingAn Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification
Sparsity regularized loss minimization problems play an important role in various fields including machine learning, data mining, and modern statistics. Proximal gradient descent method and coordinate descent method are …
Dimensionality Reductiongo-$m$HC: Direct Parameterization of Manifold-Constrained Hyper-Connections via Generalized Orthostochastic Matrices
Doubly stochastic matrices enable learned mixing across residual streams, but parameterizing the set of doubly stochastic matrices (the Birkhoff polytope) exactly and efficiently remains an open challenge. Existing exact…
New Accelerated Past-Extragradient Methods with Variance Reduction for Generalized Equations
We develop a novel past-extragradient-type algorithmic framework, combining both Nesterov's \textit{acceleration} and \textit{variance-reduction} techniques, to solve a class of generalized equations involving possibly \…
A tutorial on generalized eigendecomposition for denoising, contrast enhancement, and dimension reduction in multichannel electrophysiology
The goal of this paper is to present a theoretical and practical introduction to generalized eigendecomposition (GED), which is a robust and flexible framework used for dimension reduction and source separation in multic…
DenoisingDimensionality Reduction