Source-linked AI summary
Randomized Nonlinear Component Analysis
David Lopez-Paz, Suvrit Sra, Alex Smola, Zoubin Ghahramani, Bernhard Schölkopf
TL;DR
PCA and CCA expose only linear relationships, while existing nonlinear variants can be computationally prohibitive at scale. The paper uses randomized features to build scalable nonlinear PCA and CCA methods, with theoretical convergence analysis and real-world evaluations. The methods are presented as effective randomized alternatives and are extended to further multivariate-analysis applications.
Problem
PCA and CCA reveal only linear relationships, while nonlinear extensions can have high computational complexity, limited parallelizability, or no theoretical guarantees.
Method
The paper constructs randomized nonlinear variants of PCA and CCA by applying linear component methods to randomized nonlinear feature mappings and analyzing their kernel approximations.
Results
The proposed methods are demonstrated on real-world data against Deep CCA, with additional experiments and applications including privileged-information learning and scalable nonlinear autoencoder training.
Takeaways & Limitations
Randomized features provide a basis for scalable nonlinear PCA and CCA while extending to tools such as spectral clustering and linear discriminant analysis.
Takeaways & Limitations
The RCCA analysis requires positive regularizers to avoid spurious ±1 correlations, and existing nonlinear alternatives may remain computationally expensive at scale.
Abstract
from arXiv · showhide
Classical methods such as Principal Component Analysis (PCA) and Canonical Correlation Analysis (CCA) are ubiquitous in statistics. However, these techniques are only able to reveal linear relationships in data. Although nonlinear variants of PCA and CCA have been proposed, these are computationally prohibitive in the large scale. In a separate strand of recent research, randomized methods have been proposed to construct features that help reveal nonlinear patterns in data. For basic tasks such as regression or classification, random features exhibit little or no loss in performance, while achieving drastic savings in computational requirements. In this paper we leverage randomness to design scalable new variants of nonlinear PCA and CCA; our ideas extend to key multivariate analysis tools such as spectral clustering or LDA. We demonstrate our algorithms through experiments on real-world data, on which we compare against the state-of-the-art. A simple R implementation of the presented algorithms is provided.
1. Introduction
PCA and CCA are widely used multivariate methods, but they reveal only linear relationships. The paper develops randomized nonlinear variants to address the computational burden of existing nonlinear extensions and evaluates them on real-world data.
- PCA rotates correlated variables into orthogonal components ordered by explained variance, while CCA finds orthogonal projections of two variables with maximal cross-correlation.
- Nonlinear PCA and CCA extensions include KPCA, autoencoders, KCCA, and DCCA, but often have cubic sample-size complexity, limited parallelizability, or no theoretical guarantees.
- Random features can reveal nonlinear patterns with little or no performance loss versus exact kernels while reducing computational complexity from cubic to linear in sample size.
- The paper lays foundations for randomized nonlinear PCA and CCA by analyzing low-rank kernel matrices formed from random feature dot-products using matrix Bernstein inequalities.
- Experiments on real-world data compare the methods with Deep CCA, while additional applications include privileged-information learning and scalable nonlinear autoencoder training.
2. Random Nonlinear Features
Random nonlinear features replace difficult joint optimization over nonlinear parameters with randomized feature maps and tractable least-squares problems. The resulting approximations simplify computation while retaining bounded-error guarantees and support scalable kernel component analysis.
- The function class uses nonlinear weights and bounded nonlinear maps, and includes models such as kernel machines, Gaussian processes, AdaBoost, and neural networks.
- Jointly optimizing feature weights and nonlinear parameters is difficult, so the method samples parameters from a data-independent distribution to construct randomized features.
- Using precomputed random features transforms the nonconvex optimization problem into a least-squares problem, typically solved with regularization.
- Theorem 1 gives a probabilistic bounded-error guarantee for approximating functions with randomized features under a Lipschitz loss.
- Solving the randomized-feature problem costs O(ndm + m^2n), while testing t points costs O(tdm); subsampled Hadamard transforms can reduce logarithmic factors.
- The paper focuses on scalable kernel component analysis with theoretical guarantees and notes that Nyström features are also covered when their randomly sampled basis is bounded.
3. Principal Component Analysis (PCA)
PCA transforms correlated variables into orthogonal components ordered by explained variance, while nonlinear extensions address richer relationships at higher computational cost. RPCA instead applies PCA to randomized nonlinear features, approximating KPCA with complexity linear in sample size.
- Classical and nonlinear PCA: PCA transforms correlated variables into orthogonal principal components ordered by the variance they explain.The first component captures maximum variance, and successive components capture maximum remaining variance orthogonal to preceding components.
- Classical and nonlinear PCA: Kernel PCA performs PCA in a high-dimensional reproducing kernel Hilbert space, but its eigenvalue computation requires O(n3) operations.
- Randomized nonlinear PCA: RPCA applies linear PCA to randomized nonlinear feature mappings and serves as a low-rank approximation to KPCA for shift-invariant kernels.The random feature map typically has m ≪ n dimensions.
- Computational complexity: O(n3) for KPCA, O(d2n) for PCA and O(m2n) for RPCA, with PCA and RPCA both linear in the sample size n.With nonlinear features, RPCA loadings approximate nonlinear functions rather than remaining linear transformations.
- Approximation and extensions: Random-feature kernel matrices converge to exact kernel matrices as m increases, enabling spectral-norm analysis through matrix Bernstein inequalities.The analysis also extends to randomized nonlinear spectral clustering.
- Approximation and extensions: Dividing the kernel approximation bound by ∥K∥ yields a relative-error bound whose dependence on n is logarithmic.The stated bound uses upper bounds on random features and kernel evaluations.
4. Canonical Correlation Analysis (CCA)
CCA finds maximally correlated linear projections of two data views, while KCCA and DCCA provide nonlinear alternatives with substantial computational cost. RCCA uses randomized nonlinear mappings so linear CCA approximates KCCA, retaining linear dependence on sample size.
- Classical and nonlinear CCA: CCA computes orthogonal canonical bases whose paired projections are maximally correlated and ordered by explained cross-correlation.The canonical correlations arise from the generalized eigenvalue problem with regularization on diagonal terms.
- Classical and nonlinear CCA: KCCA uses kernelized nonlinear projections with exact computation taking O(n3), while DCCA learns nonlinear transformations by gradient descent.
- Randomized nonlinear CCA: RCCA performs linear CCA on paired randomized nonlinear mappings and approximates KCCA equipped with shift-invariant kernels.Its basis vectors become basis functions from the corresponding nonlinear function classes.
- Computational complexity: O(n3) for KCCA, O((p2+ q2)n) for CCA and O((m2 y)n) for RCCA, with CCA and RCCA both linear in n.
- Approximation analysis: RCCA convergence analysis compares randomized kernel matrices with KCCA through regularized operators and matrix Bernstein bounds.Positive regularizers γx and γy are mandatory to avoid spurious ±1 correlations.
- Extensions: The RCCA analysis extends to randomized nonlinear LDA and further characterizes the Randomized Dependence Coefficient.LDA can be formulated as CCA between data features and one-hot label indicators.
5. Experiments
The experiments validate the theoretical error behavior of randomized PCA and CCA, compare RCCA with competing CCA methods, and apply RCCA and RPCA to privileged-information learning and scalable autoencoders.
- Canonical correlation analysis: RCCA is compared with linear CCA and Deep CCA on MNIST and XRMB using accumulated test canonical correlation.Exact KCCA was omitted because of its cubic complexity, while other low-rank approximations had been shown inferior to DCCA.
- Canonical correlation analysis: With enough random projections, RCCA explains the most test correlation while running drastically faster than DCCA.RCCA also requires up to two orders of magnitude fewer test-time weights, and Fastfood multiplications further accelerate evaluation.
- Learning using privileged information: For learning using privileged information, RCCA constructs semi-privileged features from regular image descriptors and training-only animal attributes.The experiments use SURF descriptors as regular features and 85 binary attributes as privileged features on the Animals-with-Attributes dataset.
- Learning using privileged information: RCCA features improve linear-SVM classification by an average of 14% over image features alone across 14 binary animal-classification experiments.The improvement is statistically significant under a paired Wilcoxon test at a 95% confidence interval; directly using high-level attributes yields 100% accuracy.
- Randomized autoencoders: RPCA trains nonlinear autoencoders by mapping data to nonlinear principal components and reconstructing it with nonlinear regressors.Unseen MNIST and CIFAR-10 reconstructions use 2000 random projections and train in under 200 seconds per full dataset.