UMAP for dimensionality reduction: Foundations

Before you can read a single formula in the parent note, you need to be fluent in a small pile of symbols. This page unpacks every one of them, in an order where each rests on the previous. We build from absolutely nothing — no prior linear algebra, no calculus jargon assumed.

0. What "a point in many dimensions" even means

The very first symbol the parent throws at you is $X \in R^{n \times d}$ . Let us earn every piece of it.

Figure s01 — one object, more slots. Look left to right: the same thing (a point, drawn as an orange dot) is a dot on a line when it has 1 number, a dot on a sheet when it has 2, a dot in a box when it has 3. The teal labels count the numbers. The lesson to carry away: adding dimensions just means adding measurement slots — the pattern keeps going even after we run out of ways to draw it (like the 784-D digit).

1. Distance — the ruler between two points

Every UMAP formula starts with $d_{ij}$ , the distance between point $i$ and point $j$ . We must define what "distance" means before using it.

Figure s02 — distance is just Pythagoras. The two black dots are points $i$ and $j$ . The dashed teal segment is the horizontal gap (here 3), the dashed orange segment is the vertical gap (here 2), and the solid plum line is the actual distance between them. Notice the plum line is the hypotenuse of the right triangle formed by the two gaps — so its length is $3^{2} + 2^{2}$ . That is exactly what "Euclidean distance" computes; in higher dimensions we just have more gaps to square and add.

Definition Vector subtraction and the double-bar notation

$∥ \cdot ∥_{2}$ $y_{i}$ and $y_{j}$ are each a short list of $d^{'}$ numbers of the same length (both live in $R^{d^{'}}$ ), so we can subtract them slot by slot: $y_{i} - y_{j}$ is the list of coordinate-differences (in 2-D, the horizontal gap and the vertical gap of Figure s02). Subtraction only makes sense because both have the same shape — the dimensions must match. The double vertical bars $∥ \cdot ∥_{2}$ mean length of (also called the norm): square every slot, add, take the root. So $∥ y_{i} - y_{j} ∥_{2}$ = "the straight-line length of the arrow between the two low-D points" (the plum hypotenuse in Figure s02, but in the low-D plot). The small subscript $2$ names this the Pythagoras (squared-and-rooted) recipe — the " $ℓ_{2}$ " norm. So $∥ y_{i} - y_{j} ∥_{2}^{2}$ (with an outer power 2) is just distance-squared — which conveniently cancels the square root.

Intuition Why the topic needs distance — and what "metric" means

UMAP decides who is a neighbour by measuring distances. Small distance → likely a neighbour → strong bond. Large distance → strangers → weak bond. Everything downstream is a transformation of these $d_{ij}$ numbers. The parent lists metric as a hyperparameter. A metric is simply which ruler you use to turn two points into a distance number. Swapping metrics just swaps the recipe that produces $d_{ij}$ — the rest of UMAP is untouched:

Euclidean ( $ℓ_{2}$ ): $d_{ij} = \sum_{m} (x_{im} - x_{j m})^{2}$ — straight-line length (our default).
Manhattan ( $ℓ_{1}$ ): $d_{ij} = \sum_{m} ∣ x_{im} - x_{j m} ∣$ — add the gaps without squaring (city-block walking).
Cosine: $d_{ij} = 1 - \frac{x _{i} \cdot x _{j}}{∥ x _{i} ∥ ∥ x _{j} ∥}$ — measures the angle between the two arrows, ignoring their length (great for text/word counts).

Whichever you pick, UMAP feeds the resulting $d_{ij}$ into every later formula unchanged. Related: Nearest Neighbors Algorithms is the machinery that finds the closest points quickly.

2. Neighbours — the set $N (i)$ and the hyperparameter $k$

Before the friendship formula, we must say which points count as neighbours of $x_{i}$ .

3. Turning distance into a "friendship weight"

The parent's core high-D formula is $w_{ij} = exp (- \frac{m a x ( 0 , d _{ij} - ρ _{i} )}{σ _{i}}), j \in N (i) .$ Three new pieces to earn: $exp$ , $max (0, \cdot)$ , and the parameters $ρ_{i}, σ_{i}$ .

Figure s03 — the friendship weight fades from 1 down to 0. The horizontal axis is distance $d_{ij}$ ; the vertical axis is the weight $w_{ij}$ . Follow either curve from left to right: it starts flat at weight $1$ up to the dashed orange line at $ρ_{i}$ (the nearest-neighbour distance), then slides smoothly toward $0$ — never crossing below zero. Compare the two curves: the plum one (small $σ_{i}$ ) drops steeply so only very close points keep any weight, while the teal one (large $σ_{i}$ ) fades gently so farther points still count. That contrast is what $σ_{i}$ controls.

4. Summation and logarithm — reading the calibration target

The parent sets $\sum_{j \in N (i)} w_{ij} = lo g_{2} (k)$ . Two more notations — and recall from Section 2 that $N (i)$ is the $k$ -nearest-neighbour set and $k$ is n_neighbors.

Intuition WHY a unique

$σ_{i}$ always exists (the monotonicity argument) Think of the total weight as a knob-reading that depends on $σ_{i}$ : $S (σ_{i}) = \sum_{j \in N (i)} exp (- \frac{m a x ( 0 , d _{ij} - ρ _{i} )}{σ _{i}}) .$ Turn $σ_{i}$ up and every single term rises (each exponential fades more slowly), so $S$ rises. Turn $σ_{i}$ down and every term falls, so $S$ falls. Because $S$ moves strictly one direction as $σ_{i}$ changes — it is monotonic — it can equal the target $lo g_{2} (k)$ at exactly one value of $σ_{i}$ . In the two limits:

As $σ_{i} \to 0^{+}$ : only the nearest neighbour survives, so $S \to 1$ (below the target).
As $σ_{i} \to \infty$ : every term $\to 1$ , so $S \to k$ (above the target, since $k > lo g_{2} k$ ).

A strictly-increasing quantity that starts below the target and ends above it must cross the target once. That is the guarantee that makes the binary search in Worked Example 3 valid: it is squeezing in on that single crossing point. Picture the plum/teal curves of Figure s03 as one knob-turn: sliding $σ_{i}$ smoothly slides the whole sum up or down.

5. Making the graph undirected — the fuzzy union

So far $w_{ij}$ is directed: it is "how strongly $i$ reaches toward $j$ ," and $w_{ij}$ need not equal $w_{j i}$ . We now define a single undirected edge weight, written with the superscript "sym" (for symmetric):

6. The low-D kernel — drawing bonds in 2-D

The parent's low-D weight: $v_{ij} = \frac{1}{1 + a ∥ y _{i} - y _{j} ∥ _{2}^{2 b}} .$

7. Comparing two structures — cross-entropy

The final objective compares the high-D bonds $w_{ij}^{sym}$ against the low-D bonds $v_{ij}$ using cross-entropy, written $L$ (a script "L" for Loss — the single number we push downhill).

How the foundations feed UMAP

Every arrow is a symbol you now own. Related big-picture methods worth knowing: PCA and Random Projection (linear squashing), Isomap and Spectral Clustering (graph/manifold cousins), Autoencoders (neural squashing), and the deeper theory in Topological Data Analysis.

Equipment checklist

Try to answer each before revealing. If any stumps you, re-read its section above.

What is the bold-face convention for matrices vs vectors?

Bold uppercase (e.g.

X

Y

) is a whole matrix/table; plain lowercase with a subscript (e.g.

x_{i}

y_{i}

) is one row — a single point/vector.

What does

X \in R^{n \times d}

mean in plain words?

X

is the data matrix: a table of real numbers with

n

rows (one per data point) and

d

columns (one per measurement).

What is

Y

and what is

d^{'}

Y

is the output matrix — the finished layout with

n

rows and

d^{'}

columns;

d^{'}

is the small target dimension (usually 2), so the result can be plotted.

What is the difference between

x_{i}

and

y_{i}

x_{i}

is the original high-D data point (a row of

X

);

y_{i}

is its finished low-D position (a row of

Y

), the

(x, y)

dot on the plot.

What do the subscripts in

d_{ij}

tell you?

That distance needs two points — point number

i

and point number

j

Why can you subtract

y_{i} - y_{j}

, and what does

∥ y_{i} - y_{j} ∥_{2}

compute?

Because both are vectors of the same length, so you subtract slot by slot; the double bars then give the straight-line (Euclidean,

ℓ_{2}

) length of that difference.

What is a "metric" and name two besides Euclidean.

The ruler used to turn two points into a distance

d_{ij}

; e.g. Manhattan (

ℓ_{1}

, sum of absolute gaps) and cosine (angle between the arrows).

What is

N (i)

, and is

i

itself in it?

The set of the

k

nearest neighbours of point

i

; no —

i

is excluded (a point is not its own neighbour).

What constraint must

k

(n_neighbors) satisfy and why?

k < n

— you cannot have more neighbours than there are other points;

N (i)

needs

k \leq n - 1

For which

j

w_{ij}

non-zero?

Only for

j \in N (i)

(the

k

nearest neighbours); for all other $