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

arXiv: https://arxiv.org/abs/2006.00402 · HTML: https://mlsanity.com/paper/2006.00402/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2020.

## Built on by (most cited first, 16 of 16)

- [Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation](https://mlsanity.com/paper/2101.09875/) (2021)
- [SNEkhorn: Dimension Reduction with Symmetric Entropic Affinities](https://mlsanity.com/paper/2305.13797/) (2023)
- [Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise](https://mlsanity.com/paper/2206.11386/) (2022)
- [Robust Inference of Manifold Density and Geometry by Doubly Stochastic Scaling](https://mlsanity.com/paper/2209.08004/) (2022)
- [Beyond kNN: Adaptive, Sparse Neighborhood Graphs via Optimal Transport](https://mlsanity.com/paper/2208.00604/) (2022)
- [Entropic Optimal Transport Eigenmaps for Nonlinear Alignment and Joint Embedding of High-Dimensional Datasets](https://mlsanity.com/paper/2407.01718/) (2024)
- [Your Attention Matters: to Improve Model Robustness to Noise and Spurious Correlations](https://mlsanity.com/paper/2507.20453/) (2025)
- [ManiFeSt: Manifold-based Feature Selection for Small Data Sets](https://mlsanity.com/paper/2207.08574/) (2022)
- [Manifold Learning with Sparse Regularised Optimal Transport](https://mlsanity.com/paper/2307.09816/) (2023)
- [Improving Deep Regression with Tightness](https://mlsanity.com/paper/2502.09122/) (2025)
- [Optimal Transport with Adaptive Regularisation](https://mlsanity.com/paper/2310.02925/) (2023)
- [Orthogonalization of data via Gromov-Wasserstein type feedback for clustering and visualization](https://mlsanity.com/paper/2207.12279/) (2022)
- [A cutting plane algorithm for globally solving low dimensional k-means clustering problems](https://mlsanity.com/paper/2402.13595/) (2024)
- [Sketching the Heat Kernel: Using Gaussian Processes to Embed Data](https://mlsanity.com/paper/2403.07929/) (2024)
- [Euclidean Distance Deflation Under High-Dimensional Heteroskedastic Noise](https://mlsanity.com/paper/2507.18520/) (2025)
- [Robust Tangent Space Estimation via Laplacian Eigenvector Gradient Orthogonalization](https://mlsanity.com/paper/2510.02308/) (2025)

## Abstract (arXiv)

A fundamental step in many data-analysis techniques is the construction of an affinity matrix describing similarities between data points. When the data points reside in Euclidean space, a widespread approach is to from an affinity matrix by the Gaussian kernel with pairwise distances, and to follow with a certain normalization (e.g. the row-stochastic normalization or its symmetric variant). We demonstrate that the doubly-stochastic normalization of the Gaussian kernel with zero main diagonal (i.e., no self loops) is robust to heteroskedastic noise. That is, the doubly-stochastic normalization is advantageous in that it automatically accounts for observations with different noise variances. Specifically, we prove that in a suitable high-dimensional setting where heteroskedastic noise does not concentrate too much in any particular direction in space, the resulting (doubly-stochastic) noisy affinity matrix converges to its clean counterpart with rate m-1/2, where m is the ambient dimension. We demonstrate this result numerically, and show that in contrast, the popular row-stochastic and symmetric normalizations behave unfavorably under heteroskedastic noise. Furthermore, we provide examples of simulated and experimental single-cell RNA sequence data with intrinsic heteroskedasticity, where the advantage of the doubly-stochastic normalization for exploratory analysis is evident.