VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 01: Arrays and strings

Lesson 1.16 of 16 in this moduleFree

Normalise a Batch of Feature Vectors

The module's ML twin: L2-normalise every row and standardise every column of a batch. From nested Python loops, to precomputed norms, to vectorised NumPy with axis and keepdims, then the constraints that matter in production: zero rows, numerical stability, streaming statistics and train/serve skew.

about 10 min 7 Python examples 2 quick checks

Problem. You have a batch X of n feature vectors, each of dimension d (an n × d matrix).

  1. L2-normalise each row: divide every row by its length, so each has norm 1 (used before cosine similarity).
  2. Standardise each column: subtract the column mean and divide by the column standard deviation (used before training most models).
text
X = [[3, 4],          row norms [5, 10]        →   [[0.6, 0.8],
     [6, 8]]                                         [0.6, 0.8]]

This is the module's ML twin: nothing here is an interview puzzle, but every idea from module 01 shows up. Arrays and memory layout (1.1), running sums (1.2), one-pass statistics, and the habit of asking what happens when the constraints change. The complexity barely changes (it's O(n · d) from start to finish); what changes is the constant, numerical stability and correctness in production.


1. Step 1: Clarify

Question Answer Why it matters
Shape? n × d, e.g. 10⁵ × 768 7.7 × 10⁷ values: Python loops are too slow
Can a row be all zeros? Yes (padding, empty documents) Division by zero → NaN
Can a column be constant? Yes Standard deviation 0 → division by zero
Does it fit in memory? Sometimes not Streaming statistics
Training or serving? Both Statistics must come from the training data only

2. Step 2: Brute force: nested Python loops

Compute each row's norm by looping over its values, then divide. Note the hidden waste: this version recomputes the norm for every element.

python
import math


def l2_normalise_naive(X):
    out = []
    for row in X:
        new_row = []
        for x in row:
            norm = math.sqrt(sum(v * v for v in row))      # recomputed d times per row!
            new_row.append(x / norm)
        out.append(new_row)
    return out


X = [[3.0, 4.0], [6.0, 8.0]]
assert l2_normalise_naive(X) == [[0.6, 0.8], [0.6, 0.8]]
print("naive version works: O(n · d²) time")

O(n · d²): for 10⁵ rows of dimension 768, about 6 × 10¹⁰ operations. The first fix is the same as lesson 1.2's: don't recompute what you can compute once.


3. Step 3: Optimise

Optimisation 1: compute each norm once (O(n · d))

python
import math


def l2_normalise_loops(X):
    out = []
    for row in X:
        norm = math.sqrt(sum(v * v for v in row))          # once per row: O(d)
        out.append([v / norm for v in row])
    return out


X = [[3.0, 4.0], [6.0, 8.0]]
assert l2_normalise_loops(X) == [[0.6, 0.8], [0.6, 0.8]]
print("one norm per row: O(n · d) time")

Now O(n · d), which is optimal: every value must be read and written. But each step still runs in the Python interpreter, which costs tens of nanoseconds per operation. With 7.7 × 10⁷ values, that's seconds per batch.

Optimisation 2: vectorise with NumPy (same O(n · d), much smaller constant)

First principles (lesson 1.1): a NumPy array is one contiguous buffer, and its operations run as compiled loops. np.linalg.norm(X, axis=1, keepdims=True) computes all row norms at once with shape (n, 1); dividing X (n, d) by it broadcasts the norm across each row.

a 3 by 4 batch with row norms 5, 1 and 10 as a 3 by 1 column; dividing broadcasts each norm across its row, giving unit-length rows.
Diagram— a 3 by 4 batch with row norms 5, 1 and 10 as a 3 by 1 column; dividing broadcasts each norm across its row, giving unit-length rows.
python
import math
import time

import numpy as np


def l2_normalise_loops(X):
    out = []
    for row in X:
        norm = math.sqrt(sum(v * v for v in row))
        out.append([v / norm for v in row])
    return out


def l2_normalise(X):
    return X / np.linalg.norm(X, axis=1, keepdims=True)   # (n, d) / (n, 1)


rng = np.random.default_rng(32)
X = rng.normal(size=(2000, 128))
Y = l2_normalise(X)
assert np.allclose(np.linalg.norm(Y, axis=1), 1.0)
assert np.allclose(Y, np.array(l2_normalise_loops(X.tolist())))

t0 = time.perf_counter(); l2_normalise_loops(X.tolist()); t_loop = time.perf_counter() - t0
t0 = time.perf_counter(); l2_normalise(X); t_vec = time.perf_counter() - t0
print(f"loops {t_loop * 1e3:.1f} ms, NumPy {t_vec * 1e3:.2f} ms, same O(n·d)")
assert t_vec < t_loop

Same Big-O, very different wall-clock time (measure it on your machine; the gap is usually one to two orders of magnitude). Big-O tells you how cost grows; the constant tells you whether it's usable.

  • keepdims=True matters: without it, the norms have shape (n,), and X / norms would try to broadcast along the columns, which is wrong (or crashes when n ≠ d).

Standardising columns: the same idea along the other axis

python
import numpy as np


def standardise(X):
    mean = X.mean(axis=0, keepdims=True)                   # (1, d)
    std = X.std(axis=0, keepdims=True)                     # (1, d)
    return (X - mean) / std


rng = np.random.default_rng(33)
X = rng.normal(loc=5.0, scale=3.0, size=(1000, 4))
Z = standardise(X)
assert np.allclose(Z.mean(axis=0), 0.0) and np.allclose(Z.std(axis=0), 1.0)
print("standardised: column means 0, standard deviations 1")

Rows use axis=1, columns use axis=0. Getting the axis wrong is the most common bug in this kind of code, so assert the shapes and the result (norms are 1, means are 0) just as we cross-checked against brute force in every lesson.

Quick check

The loop version and the NumPy version are both O(n · d). Why is NumPy much faster?

  1. NumPy uses a better algorithm
  2. Both do the same number of operations, but NumPy runs them as compiled loops over a contiguous buffer, while Python pays interpreter overhead for every single value
  3. NumPy skips some values
  4. NumPy uses the GPU automatically
Show the answer

B. Both do the same number of operations, but NumPy runs them as compiled loops over a contiguous buffer, while Python pays interpreter overhead for every single value — Big-O hides constants. Vectorisation shrinks the constant without changing the complexity.


4. When the constraints change

a decision map: vectorised NumPy when the batch fits in memory, an epsilon guard for zero rows or zero variance, running statistics for streams, statistics fitted on training data only, and plain loops only as a reference check.
Diagram— a decision map: vectorised NumPy when the batch fits in memory, an epsilon guard for zero rows or zero variance, running statistics for streams, statistics fitted on training data only, and plain loops only as a reference check.

Change A: zero rows and constant columns

A padding row has norm 0, so X / 0 gives NaN, which then spreads through every later computation. Guard the denominator.

python
import numpy as np


def l2_normalise_safe(X, eps=1e-12):
    norms = np.linalg.norm(X, axis=1, keepdims=True)
    return X / np.maximum(norms, eps)                      # zero rows stay zero, no NaN


def standardise_safe(X, eps=1e-8):
    std = X.std(axis=0, keepdims=True)
    return (X - X.mean(axis=0, keepdims=True)) / np.where(std < eps, 1.0, std)


X = np.array([[3.0, 4.0, 1.0], [0.0, 0.0, 1.0], [6.0, 8.0, 1.0]])   # a zero row (first two columns)
Y = l2_normalise_safe(X[:, :2])
assert not np.isnan(Y).any() and Y[1].tolist() == [0.0, 0.0]
Z = standardise_safe(X)
assert not np.isnan(Z).any() and np.allclose(Z[:, 2], 0.0)          # constant column → 0, not NaN
print("guards: no NaN from zero rows or constant columns")

Change B: the data doesn't fit in memory (streaming statistics)

To standardise, you need each column's mean and variance over all the data, but you can only see one batch at a time. Keep running statistics. The naive way (running sum and running sum of squares, then E[x²] − E[x]²) suffers catastrophic cancellation when values are large. Welford's algorithm updates the mean and the sum of squared deviations directly and stays stable. Here it's the batched form (Chan et al.):

python
import numpy as np


class RunningStats:
    """Column means and variances over batches, numerically stable (Welford / Chan)."""

    def __init__(self, d):
        self.n = 0
        self.mean = np.zeros(d)
        self.m2 = np.zeros(d)                          # sum of squared deviations

    def update(self, batch):
        b = len(batch)
        b_mean = batch.mean(axis=0)
        b_m2 = ((batch - b_mean) ** 2).sum(axis=0)
        delta = b_mean - self.mean
        total = self.n + b
        self.mean = self.mean + delta * b / total
        self.m2 = self.m2 + b_m2 + delta ** 2 * self.n * b / total
        self.n = total

    @property
    def std(self):
        return np.sqrt(self.m2 / self.n)


rng = np.random.default_rng(34)
data = rng.normal(loc=1e8, scale=1.0, size=(10_000, 3))     # large offset: cancellation-prone
stats = RunningStats(3)
for start in range(0, len(data), 512):                      # stream in batches of 512
    stats.update(data[start:start + 512])
assert np.allclose(stats.mean, data.mean(axis=0))
assert np.allclose(stats.std, data.std(axis=0), rtol=1e-6)

naive_var = (data ** 2).mean(axis=0) - data.mean(axis=0) ** 2   # E[x²] − E[x]²
print("Welford std:", np.round(stats.std, 4), "| naive variance:", np.round(naive_var, 1))
assert np.abs(naive_var - 1.0).max() > 1.0                  # true variance is 1; the naive formula misses badly

Memory is O(d), whatever n is. Run it: the naive variance comes out visibly wrong (here −18, 0 and 42 instead of 1) because E[x²] and E[x]² are both around 10¹⁶, and their tiny difference is lost to rounding. This is the same "keep a small running state" idea as the running minimum (1.4) and Boyer–Moore (1.6), now with numerical stability as a constraint.

Change C: train versus serve (leakage and skew)

Fit the statistics on the training set only, store them, and apply the same numbers at serving time. Computing statistics on the test set (or on each serving batch) leaks information or makes predictions depend on whatever else is in the batch.

python
import numpy as np

rng = np.random.default_rng(35)
train = rng.normal(5.0, 2.0, size=(1000, 2))
mean, std = train.mean(axis=0), train.std(axis=0)            # fit once, on train

def transform(batch):
    return (batch - mean) / std                              # same numbers everywhere

one_request = np.array([[5.0, 5.0]])
assert np.allclose(transform(one_request), (one_request - mean) / std)
per_batch = (one_request - one_request.mean(axis=0)) / (one_request.std(axis=0) + 1e-8)
assert np.allclose(per_batch, 0.0)                           # a lone request always becomes 0: useless
print("fit statistics on training data; per-batch statistics break single requests")

The full table

If the constraint becomes… Best approach Time Extra space
Teaching or reference check Python loops, norm once per row O(n·d), slow constant O(n·d) output
Batch fits in memory Vectorised NumPy, axis + keepdims O(n·d), fast constant O(n) or O(d) stats
Zero rows / constant columns Guard denominators with eps same same
Data doesn't fit in memory Streaming mean / variance (Welford) O(n·d) total O(d)
Large offsets, float32 Welford; never E[x²] − E[x]² O(n·d) O(d)
Training vs serving Fit stats on train, store, reuse O(d) per value served O(d)
Very large batches on GPU Same maths in PyTorch / JAX O(n·d), parallel O(d)

Quick check

Why compute variance with Welford's algorithm instead of E[x²] − E[x]² when streaming?

  1. When values are large, E[x²] and E[x]² are huge and nearly equal, so their difference loses almost all precision to rounding; Welford updates deviations directly and stays accurate
  2. Welford is asymptotically faster
  3. E[x²] − E[x]² is mathematically wrong
  4. Welford uses less memory
Show the answer

A. When values are large, E[x²] and E[x]² are huge and nearly equal, so their difference loses almost all precision to rounding; Welford updates deviations directly and stays accurate — Both are O(n·d) time and O(d) memory; the difference is numerical stability (catastrophic cancellation).


5. Saying it out loud

"Normalising is O(n·d) and that's optimal, since every value is read and written. The naive loop recomputes each norm per element, which makes it O(n·d²), so compute it once per row. Then vectorise: X / norm(X, axis=1, keepdims=True), same complexity but compiled loops over a contiguous buffer. In production I'd guard zero norms and zero variances with an epsilon, stream statistics with Welford if the data doesn't fit, and fit the statistics on training data only."


Check yourself

  1. Why is the naive loop O(n · d²), and what fixes it?
  2. Why is the vectorised version faster if the complexity is the same?
  3. What does keepdims=True do, and what goes wrong without it?
  4. How do you avoid NaN for zero rows and constant columns?
  5. Why is E[x²] − E[x]² dangerous, and what do you use instead?
  6. Why fit normalisation statistics on the training set only?
Answers
  1. The norm (O(d)) is recomputed for each of the d elements in a row; compute it once per row.
  2. NumPy runs compiled loops over contiguous memory; Python pays interpreter overhead for every value. Same Big-O, much smaller constant.
  3. It keeps the reduced axis with size 1, e.g. norms of shape (n, 1), so broadcasting divides each row by its own norm; without it the shape is (n,), which broadcasts along columns instead.
  4. Divide by max(norm, eps) and replace zero standard deviations (e.g. with 1) so constant columns become 0.
  5. Catastrophic cancellation: both terms are huge and nearly equal. Use Welford's (or Chan's batched) update.
  6. Using test or serving data leaks information and makes outputs depend on the rest of the batch; stored training statistics give the same transform everywhere.