Dimensionality Reduction
mapping
Q high dims
P low dims (2 or 3)
n points
map Q->P
minimize error of low-dim distances wrt high-dim dist
distance measures
pairwise distance matrix between points
metric between points in space
methods
MDS (multidimensional scaling)
LLE (locally linear embedding)
IsoMap, charting
PCA, SOM
complexity
naive O(n^3), many O(n^2),
best O(n sqrt n)
[LLE, Roweis and Saul, www.cs.toronto.edu/~roweis/papers/2323.pdf]
42