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:

  1. 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
  2. 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