Explain the kernel trick, and why does it become a scal...

Many models (SVM, kernel PCA, kernel ridge regression) only need the dot product between pairs of transformed feature vectors, never the transformed vectors themselves. The kernel trick exploits that: instead of explicitly mapping x into some high- or infinite-dimensional space φ(x) and computing φ(x)·φ(y), you use a kernel function k(x, y) that computes the same dot product directly in the original space, at the original space’s cost. An RBF kernel implicitly corresponds to an infinite-dimensional feature map that would be impossible to materialize, yet the kernel trick makes the model exact and cheap per pair.

The catch is “per pair” — you need the full N×N Gram matrix of pairwise kernel evaluations, which costs O(N²) to build and, for methods that need to invert or eigendecompose it, O(N³) to solve. That’s fine for thousands of examples and prohibitive for millions. The standard fixes are Nystrom approximation (build a low-rank approximation of the Gram matrix from a small landmark subset) and random feature maps like Random Kitchen Sinks (explicitly construct a finite-dimensional randomized feature space whose dot products approximate the kernel), both trading a controlled amount of approximation error for linear-model scaling. In production this is exactly why linear models and gradient-boosted trees dominate over kernel SVMs once N gets large.