Doubly-Stochastic Normalization of the Gaussian Kernel is Robust to Heteroskedastic Noise

The evolution of kernel-based methods like Diffusion Maps and spectral clustering has revolutionized nonlinear data analysis. These methods rely on affinity matrices derived from pairwise similarities, typically using Gaussian kernels. Traditional normalization techniques, such as row-stochastic and symmetric normalization, have been effective under ideal conditions but falter in noisy, high-dimensional settings. Recent advances introduced the concept of doubly-stochastic normalization, motivated by optimal transport theory, which offers promising robustness. Nonetheless, the impact of heteroskedastic noise—where observation variances vary across samples—remained underexplored, especially in high dimensions. Addressing this gap is crucial for biological data, imaging, and other fields where measurement noise is inherently non-uniform.

Existing normalization techniques assume homogeneous noise, leading to biases and inaccuracies when heteroskedasticity is present. In high-dimensional spaces, noise biases can dominate the affinity structure, impairing downstream tasks like clustering and embedding. The core challenge is to develop a normalization that automatically adjusts for variable noise levels, preserves the true geometric structure, and converges reliably as dimension grows. Without such robustness, analyses risk misinterpretation, especially in sensitive applications like single-cell genomics, where noise varies across cell types and experimental conditions.

The paper introduces a matrix scaling approach to achieve doubly-stochastic affinity matrices (W(d)), leveraging the Sinkhorn-Knopp algorithm. This method ensures each row and column sums to one, inherently correcting for noise biases. The authors provide a rigorous high-dimensional convergence analysis, proving that under mild conditions on the noise covariance, the biased affinity matrix converges to the clean version at a rate of m^{-1/2}. The approach integrates optimal transport perspectives, interpreting W(d) as the solution to an entropy-regularized transport problem, which balances data smoothness and bias correction. This theoretical foundation distinguishes it from prior heuristic normalization methods, offering provable robustness.

• �� Construct the similarity matrix K using Gaussian kernel with zero diagonal to avoid self-loops.
• �� Apply Sinkhorn-Knopp algorithm to scale K, ensuring the resulting matrix W(d) is doubly-stochastic.
• �� Prove that in high dimensions, the bias introduced by heteroskedastic noise diminishes at a rate of m^{-1/2} under mild assumptions.
• �� Use numerical simulations with high-dimensional circle data and real single-cell RNA datasets, adding heteroskedastic noise with varying covariance structures.
• �� Compare the performance of W(d) with traditional W(r) and W(s), measuring errors via Frobenius norm and eigenvector stability.
• �� Analyze the asymptotic behavior and noise correction properties through theoretical proofs and empirical validation.

Simulated data involved points on a high-dimensional circle embedded in R^m with added heteroskedastic Gaussian noise, varying noise covariance and dimension. Real data included single-cell RNA sequencing datasets with intrinsic heteroskedasticity. Metrics such as Frobenius norm error, eigenvector correlation, and affinity matrix similarity were used. The experiments tested the convergence rate of W(d) to the clean affinity matrix, compared robustness under different noise models, and evaluated the preservation of data structure. Results consistently showed that W(d) maintains high fidelity to the true structure as dimension increases, outperforming W(r) and W(s).

Theoretical analysis confirms that the bias in W(d) reduces at a rate of m^{-1/2} under heteroskedastic noise, validated by simulations where errors decrease proportionally to the square root of ambient dimension. Empirical results on single-cell data demonstrate that W(d) effectively uncovers cell subpopulations despite complex noise, with eigenvector correlations exceeding 0.9. The robustness persists across various noise covariance structures, confirming the method’s broad applicability. These findings establish W(d) as a reliable normalization in high-dimensional noisy environments.

Applicable in biological data analysis, especially single-cell genomics, where heteroskedastic measurement noise is common. Also useful in image processing, sensor networks, and any domain requiring stable affinity matrices under variable noise conditions. The method requires only constructing the Gaussian kernel and applying Sinkhorn scaling, making it straightforward to integrate into existing pipelines. Its robustness enhances downstream tasks like clustering, visualization, and manifold learning, especially when data quality varies across samples. Long-term, it could facilitate more accurate models in noisy high-dimensional settings, including deep learning frameworks.

The theoretical guarantees depend on high-dimensional asymptotics; performance may degrade in low dimensions or with extremely correlated noise. Computational complexity of O(n^2) limits scalability, necessitating approximate algorithms for large datasets. Assumptions on noise covariance structures may not hold universally, potentially affecting robustness. Future work should focus on reducing computational costs, extending to non-Gaussian noise, and validating performance in diverse real-world scenarios.