Doubly Stochastic Normalization of the Gaussian Kernel Is Robust to Heteroskedastic Noise

Area of Science:

• Data Science
• Machine Learning
• Computational Biology

Background:

• Affinity matrix construction is crucial for data analysis, often using Gaussian kernels on Euclidean data.
• Common normalization methods include row-stochastic and symmetric variants.
• Heteroskedastic noise, where data points have different noise variances, poses a challenge for these methods.

Purpose of the Study:

• To investigate the robustness of doubly-stochastic normalization for affinity matrices under heteroskedastic noise.
• To compare the performance of doubly-stochastic normalization against row-stochastic and symmetric normalizations in the presence of noise.

Main Methods:

• Constructing affinity matrices using Gaussian kernels on pairwise distances.
• Applying doubly-stochastic, row-stochastic, and symmetric normalizations.
• Theoretical analysis in a high-dimensional setting with heteroskedastic noise.
• Numerical simulations and analysis of single-cell RNA sequencing data.

Main Results:

• Doubly-stochastic normalization demonstrates robustness to heteroskedastic noise.
• Theoretical convergence rate of the noisy affinity matrix to its clean counterpart is m^(-1/2).
• Row-stochastic and symmetric normalizations perform unfavorably under heteroskedastic noise.

Conclusions:

• Doubly-stochastic normalization is advantageous for data with varying noise variances.
• This method offers improved exploratory analysis for datasets like single-cell RNA sequences.
• The findings highlight the importance of normalization choice in noisy, high-dimensional data analysis.