Introduction
Self-supervised learning (SSL) methods like Barlow Twins and VICReg have demonstrated remarkable success in learning visual representations without labeled data. These methods rely on decorrelation regularizers to prevent "collapse"—a failure mode where the model maps all inputs to a single constant vector. By forcing the cross-correlation or covariance matrix of embeddings toward the identity matrix, these models ensure that each feature dimension captures unique information.
However, these approaches face a significant "computational wall." The standard decorrelation loss requires computing a $d \times d$ matrix, where $d$ is the embedding dimension. This results in $O(d^2)$ complexity, which becomes a bottleneck as researchers scale embeddings to 8192, 16384, or beyond to improve performance. This paper introduces a novel approach using the Fast Fourier Transform (FFT) to reduce this complexity to $O(d \log d)$, enabling efficient training of high-dimensional representations.
Methodology: Relaxed Decorrelation via FFT
The core innovation is a "relaxed" version of the decorrelation loss. Instead of penalizing every individual off-diagonal element in the correlation matrix, the authors propose penalizing a "summary vector."
The Summary Vector and FFT Trick
The summary vector $v$ is defined such that each element $v_k$ is the sum of specific off-diagonal entries in the correlation matrix. Mathematically, the authors prove that this summary vector is equivalent to a circular correlation of the embedding vectors.
By leveraging the Wiener-Khinchin theorem, this circular correlation can be computed in the frequency domain using FFT. This shift from the spatial domain to the frequency domain reduces the computational complexity from $O(nd^2)$ to $O(nd \log d)$, where $n$ is the batch size.
Mitigating "Cheating" with Feature Permutation
A potential issue with a sum-based "relaxed" loss is that the model might learn to make some correlation terms positive and others negative so they cancel out to zero without actually decorrelating the features. To prevent this, the authors introduce random feature permutation in every training batch. By shuffling the order of features, the model is forced to decorrelate all pairs over time, as it cannot predict which features will be summed together in the next iteration.
Empirical Results
The proposed method was evaluated on ImageNet-100, ImageNet (ILSVRC-2012), and Pascal VOC benchmarks.
Efficiency and Scalability
The FFT-based approach provides substantial gains in both speed and memory efficiency. At a dimension of $d=8192$, the method is 1.2x to 2.2x faster than Barlow Twins. The advantage becomes even more pronounced at higher dimensions; at $d=16384$, it is up to 5.7x faster than VICReg.
As shown in the figure above, while Barlow Twins' memory usage grows quadratically, the proposed method scales much more gracefully, making high-dimensional research accessible on standard GPU hardware.
Accuracy Parity
Crucially, this efficiency does not come at the cost of performance. Despite the relaxed nature of the loss, the models achieve Top-1 accuracy on ImageNet that matches or slightly exceeds the original $O(d^2)$ methods. For instance, with $d=8192$, the proposed model achieved 73.2% Top-1 accuracy on ImageNet, identical to the performance reported in the original Barlow Twins paper.
Conclusion
By reframing the decorrelation problem through the lens of signal processing, this work breaks the $O(d^2)$ barrier in self-supervised learning. The combination of FFT-based circular correlation and random feature permutation allows for the training of extremely high-dimensional embeddings with significantly reduced computational overhead, paving the way for more scalable and accessible SSL research.
Summary updated