Principal Components Analysis
Assumptions: linearity, orthogonality.
Directions (subspaces) of maximal sample variance -> Top (dominant) eigenvectors of the sample covariance matrix, with associated eigenvalues directional variances.
Principal Components: (unit) eigenvectors of the sample covariance matrix
PCA at scale:
- big n (observations), small d (feature set)
- complexities:
- local storage O(d^2) [outer product],
- local computation O(d^3) [eigen-decomposition],
- communication O(dk) [top eigenvectors]
- algorithm: similar to closed-form linear regression
- big n, big d
- complexities:
- local storage O(dk+n) [iterated top eigenvectors + intermediate vector],
- local computation O(dk+n) [vector multiplication + vector concatenation],
- communication O(dk+n) [iterated top eigenvectors + intermediate vector]
- algorithm: iterative algorithm (Krylov subspace methods, random projection.)
[Distributed machine learning first distributes n observations, preserving closed-form algorithm (if exists) for performance; when feature set d also scales, algorithm complexity needs to be restricted to be linear in both n and d, and typically iterative algorithms are used such as stochastic gradient descent (SGD).]
Singular Value Decomposition
🏷 Category=Computation Category=Machine Learning