Sinkhorn-Knopp Algorithm

The algorithm iteratively normalizes the rows and columns of a non-negative square matrix K until it converges to a doubly stochastic matrix. Given an initial matrix, it alternates between:

• Row normalization: Scaling each row to sum to 1
• Column normalization: Scaling each column to sum to 1 This process is guaranteed to converge for any matrix with total support, producing a unique doubly stochastic matrix of the form D₁ K D₂ where D₁ and D₂ are diagonal scaling matrices.

When combined with an entropic penalty, the Sinkhorn-Knopp algorithm computes a smooth approximation of the Wasserstein distance in optimal transport. The entropy term -εH(P) is added to the transport cost, making the optimization strictly convex and solvable via iterative matrix scaling. The parameter ε controls the trade-off:

• Small ε: Approximates exact optimal transport (sparse couplings)
• Large ε: Produces smoother, more diffuse couplings This differentiable formulation enables end-to-end training with gradient backpropagation through the transport plan.

In the SwAV (Swapping Assignments between Views) framework, the Sinkhorn-Knopp algorithm operates on the predicted code matrix Q to enforce equipartition. The algorithm solves:

• Constraint: Each of K prototypes must be assigned to approximately B/K samples in a batch of size B
• Output: A soft assignment matrix where columns sum to uniform marginal distributions This prevents the trivial solution where all samples collapse to a single prototype, forcing the model to learn diverse, discriminative visual features without requiring explicit negative pairs.

The iterative row-column normalization can be efficiently implemented on GPU hardware using matrix operations. A typical implementation converges in 3-5 iterations for the online clustering use case, as exact convergence is unnecessary for representation learning. The algorithm's computational complexity is O(K × B × iterations) where K is the number of prototypes and B is the batch size. Key optimizations include:

• In-place normalization operations to minimize memory allocation
• Fused CUDA kernels for the alternating scaling steps
• Early stopping when the marginal constraint violation falls below a threshold

The Sinkhorn-Knopp algorithm solves the entropy-regularized optimal transport problem, which seeks the most efficient coupling between two probability distributions subject to a cost matrix. In the self-supervised context:

• Source distribution: Uniform distribution over batch samples
• Target distribution: Uniform distribution over prototypes
• Cost matrix: Negative cosine similarities between sample embeddings and prototype vectors The resulting transport plan assigns samples to prototypes while respecting the equipartition constraint, making it a principled alternative to hard cluster assignment methods like K-means.

The Sinkhorn-Knopp theorem proves that for any strictly positive square matrix, the iterative row-column normalization procedure converges linearly to a unique doubly stochastic matrix. Key theoretical properties:

• Linear convergence rate: Error decreases geometrically with each iteration
• Global convergence: Guaranteed from any initial positive matrix
• Uniqueness: The resulting doubly stochastic matrix is unique up to the scaling factors In practice, a small regularization constant λ is added to prevent division by zero when the code matrix contains near-zero entries, ensuring numerical stability throughout training.

The mathematical foundation upon which the Sinkhorn-Knopp algorithm operates. Optimal transport seeks the most efficient way to move probability mass from a source distribution to a target distribution while minimizing a cost function.

• Entropic Regularization: Adding an entropy term smooths the problem, making it strictly convex and solvable via the Sinkhorn iterations.
• Coupling Matrix: The output is a soft assignment matrix that maps input samples to cluster prototypes.
• Dual Use: Balances cluster assignments while respecting the semantic similarity between embeddings and prototypes.

A training paradigm where cluster assignments are computed on-the-fly for each mini-batch rather than over the entire dataset. The Sinkhorn-Knopp algorithm is critical here because it enforces a balanced partition constraint without requiring a global clustering pass.

• Batch-Level Constraint: Ensures that within each mini-batch, the K clusters are used roughly uniformly.
• Trivial Solution Avoidance: Without equipartition, the model would assign all images to a single dominant cluster.
• Scalability: Enables clustering-based self-supervised learning on massive, uncurated image datasets.

A catastrophic failure mode in self-supervised learning where the encoder produces a constant, non-informative vector for all inputs. The Sinkhorn-Knopp algorithm acts as an explicit regularizer to prevent this by forcing the model to use all available clusters.

• Full Collapse: All outputs map to a single point, achieving zero variance.
• Dimensional Collapse: The embedding space collapses to a lower-dimensional subspace.
• Prevention: Equipartition constraints ensure the model must differentiate between data points to distribute them across distinct clusters.

The mathematical object produced by the Sinkhorn-Knopp algorithm—a square matrix where all rows and columns sum to 1. In the context of self-supervised clustering, this matrix represents a balanced assignment of B samples to K prototypes.

• Row Constraint: Each sample's total assignment mass across all prototypes equals 1.
• Column Constraint: Each prototype receives an equal total mass of B/K from the batch.
• Iterative Normalization: Achieved by alternating between scaling rows and columns until convergence, typically in fewer than 10 iterations.

An alternative to clustering-based methods that prevents collapse without requiring the Sinkhorn-Knopp algorithm or negative pairs. VICReg explicitly regularizes the variance of each embedding dimension and decorrelates the covariance matrix.

• Variance Regularization: A hinge loss keeps the standard deviation of each dimension above a threshold.
• Covariance Penalty: Minimizes off-diagonal elements of the covariance matrix to decorrelate features.
• Contrast: Unlike SwAV, VICReg avoids the computational overhead of iterative Sinkhorn normalization on each batch.