NMF & Clustering

Chapter 1: The Factorization V ≈ WH

Given a non-negative matrix V of size m×n (m frequency bins, n time frames), we want:

Here k is the number of components (sources). Each column of W is a spectral basis — the frequency fingerprint of one source. Each row of H is an activation vector — the temporal pattern of that source.

What Each Dimension Means

The reconstruction of one column (one time frame) is:

Each time frame is a non-negative mixture of the k spectral bases, weighted by the activations. This is exactly source separation: each source contributes its spectral shape scaled by its current loudness.

Chapter 2: Multiplicative Update Rules

How do we actually compute W and H? We can't just use SVD (it gives negative values). Instead, Lee and Seung (1999) gave beautifully simple multiplicative update rules that guarantee non-negativity and monotonic decrease of the cost function.

The Cost Function

We minimize the squared Frobenius norm of the reconstruction error:

The Updates

The ⊙ is element-wise multiplication, and division is also element-wise. These rules are derived from the gradient, but structured so that:

1. Non-negativity is preserved: if W, H start non-negative and V is non-negative, the updates stay non-negative (we're multiplying by non-negative ratios).
2. Cost monotonically decreases: each update is guaranteed to not increase the objective.
3. Fixed points are stationary points: when H_ij(W^TV)_ij = H_ij(W^TWH)_ij for all i,j, we've reached a (local) minimum.

Derivation Sketch

Take the gradient of ||V-WH||² with respect to H:

Standard gradient descent would be H ← H - η∇_H. Lee & Seung choose the step size element-wise as η_ij = H_ij / (W^TWH)_ij. Substituting gives the multiplicative rule. The non-negativity of V, W, H ensures the ratio is always non-negative.

python
import numpy as np

def nmf(V, k, n_iter=200, eps=1e-10):
    """Multiplicative update NMF. V >= 0, shape (m, n)."""
    m, n = V.shape
    W = np.random.rand(m, k) + eps
    H = np.random.rand(k, n) + eps

    for _ in range(n_iter):
        # Update H
        H *= (W.T @ V) / (W.T @ W @ H + eps)
        # Update W
        W *= (V @ H.T) / (W @ H @ H.T + eps)

    return W, H

Chapter 3: Audio Source Separation

The killer application of NMF is audio source separation. Given a recording of multiple sounds mixed together, NMF can pull them apart — without knowing what the sources are in advance.

The Pipeline

Why It Works

Each source has a distinctive spectral shape (its column in W). A violin has strong harmonics at specific frequencies. A drum has broadband energy in short bursts. NMF discovers these shapes from the mixture alone, because:

• Different sources activate at different times (H is approximately sparse)
• Different sources have different spectral shapes (W columns are distinct)
• The non-negativity constraint prevents destructive interference artifacts

Chapter 4: Deep NMF

What if we stack multiple NMF layers? Instead of V ≈ WH, we factorize:

Each layer provides a finer decomposition. The first layer captures broad structure, deeper layers capture finer details. This is Deep NMF — and it connects NMF to deep learning.

Why Go Deep?

A single-layer NMF with k components finds the best rank-k non-negative approximation. But what if the true structure is hierarchical? A face is composed of eyes, nose, mouth (layer 1). Each eye is composed of iris, pupil, eyelid (layer 2). Deep NMF captures this hierarchy naturally.

Implicit Regularization

Even without explicit regularization, depth acts as an implicit constraint. A deep factorization V ≈ W₂W₁H with the same total rank has a different optimization landscape than shallow V ≈ WH. Deeper factorizations tend to find sparser, more structured solutions — a phenomenon also observed in deep linear networks.

Chapter 5: k-means as NMF

Here's a surprising connection: k-means clustering is a special case of NMF. When we constrain H to have exactly one non-zero entry per column (a one-hot encoding), NMF reduces to k-means.

The Equivalence

In k-means, we assign each data point x_j to cluster c_i and represent it by the centroid μ_i. In matrix form:

The columns of W are the cluster centroids. H is the assignment matrix (one-hot per column). The reconstruction VH = centroids of assigned clusters.

Standard NMF relaxes the one-hot constraint: H can have multiple non-zero entries per column. This means each data point can be a mixture of clusters rather than assigned to exactly one. NMF is "soft clustering."

Chapter 6: Showcase — Interactive Source Separation

The moment of truth. You'll mix 2-3 synthetic spectral sources with different frequencies and temporal patterns. Then watch NMF separate them in real time.

What Makes Separation Hard?

Try making Source 1 and Source 2 have similar frequencies (both around 3-4). The separation degrades because NMF can't distinguish sources with identical spectral shapes. Separation works when sources have distinctive frequency fingerprints.

Chapter 7: Beyond — Connections

NMF sits at the intersection of matrix factorization, source separation, topic modeling, and deep learning.

Related Lessons

Previous: Autoencoders & Robust PCA — linear AE = PCA, the non-negative cousin of NMF.

Next: Dictionary Learning & Sparse Coding — what happens when you allow negative values but enforce sparsity.