Doubly Stochastic Normalization of the Gaussian Kernel Is Robust to Heteroskedastic Noise.
Doubly Stochastic Normalization of the Gaussian Kernel Is Robust to Heteroskedastic Noise.
复制标题
DOI：
10.1137/20m1342124
复制
发表时间：
2021
影响因子：
3.6
通讯作者：
Kluger Y
中科院分区：
文献类型：
--
作者：
Landa B;Coifman RR;Kluger Y
许多数据分析技术的一个基本步骤是构建描述数据点之间相似性的亲和矩阵。当数据点位于欧几里得空间中时，一种普遍的方法是通过具有成对距离的高斯核来形成亲和矩阵，然后进行一定的归一化（例如行随机归一化或其对称变体）。我们证明了具有零主对角线的高斯核的双随机归一化（即，无自环）对异方差噪声是鲁棒的。也就是说，双随机归一化的优点在于它自动考虑具有不同噪声方差的观测。具体来说，我们证明了在一个合适的高维设置中，异方差噪声不会在空间中的任何特定方向上集中太多，由此产生的（双重随机）噪声亲和矩阵以m−1/2的速率收敛到其干净的对应矩阵，其中m是环境维度。我们证明了这一结果的数值，并表明，相比之下，流行的行随机和对称规范化下的异方差噪声表现不利。此外，我们还提供了具有内在异方差性的模拟和实验单细胞RNA序列数据的例子，其中探索性分析的双随机归一化的优势是显而易见的。
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.