We propose a new fast method of measuring distances between large numbers of
related high dimensional datasets called the Diffusion Earth Mover's Distance
(EMD). We model the datasets as distributions supported on common data graph
that is derived from the affinity matrix computed on the combined data. In such
cases where the graph is a discretization of an underlying Riemannian closed
manifold, we prove that Diffusion EMD is topologically equivalent to the
standard EMD with a geodesic ground distance. Diffusion EMD can be computed in
$\tilde{O}(n)$ time and is more accurate than similarly fast algorithms such as
tree-based EMDs. We also show Diffusion EMD is fully differentiable, making it
amenable to future uses in gradient-descent frameworks such as deep neural
networks. Finally, we demonstrate an application of Diffusion EMD to single
cell data collected from 210 COVID-19 patient samples at Yale New Haven
Hospital. Here, Diffusion EMD can derive distances between patients on the
manifold of cells at least two orders of magnitude faster than equally accurate
methods. This distance matrix between patients can be embedded into a higher
level patient manifold which uncovers structure and heterogeneity in patients.
More generally, Diffusion EMD is applicable to all datasets that are massively
collected in parallel in many medical and biological systems.

本文提出了一种计算大规模相关高维数据集之间的距离的快速方法，称为扩散地球移位距离（Diffusion Earth Mover's Distance）。通过建模数据集为分布并计算相互作用矩阵来实现，该方法的时间复杂度为 O (n)，并且比基于树的算法更加准确和可微分，适用于深度神经网络等梯度下降框架。实验通过 210 个 COVID-19 样本的单细胞数据表明该方法比同等精确度的方法至少快两个数量级，且可以嵌入更高层次的患者流形中揭示患者间的结构和异质性，并可适用于其他医学和生物模型中大规模数据集的距离计算。

扩散地球移动距离与分配嵌入

Diffusion Earth Mover's Distance and Distribution Embeddings

Discovering causal relationships from observational data is a crucial problem
and it has applications in many research areas. The PC algorithm is the
state-of-the-art constraint based method for causal discovery. However, runtime
of the PC algorithm, in the worst-case, is exponential to the number of nodes
(variables), and thus it is inefficient when being applied to high dimensional
data, e.g. gene expression datasets. On another note, the advancement of
computer hardware in the last decade has resulted in the widespread
availability of multi-core personal computers. There is a significant
motivation for designing a parallelised PC algorithm that is suitable for
personal computers and does not require end users' parallel computing knowledge
beyond their competency in using the PC algorithm. In this paper, we develop
parallel-PC, a fast and memory efficient PC algorithm using the parallel
computing technique. We apply our method to a range of synthetic and real-world
high dimensional datasets. Experimental results on a dataset from the DREAM 5
challenge show that the original PC algorithm could not produce any results
after running more than 24 hours; meanwhile, our parallel-PC algorithm managed
to finish within around 12 hours with a 4-core CPU computer, and less than 6
hours with a 8-core CPU computer. Furthermore, we integrate parallel-PC into a
causal inference method for inferring miRNA-mRNA regulatory relationships. The
experimental results show that parallel-PC helps improve both the efficiency
and accuracy of the causal inference algorithm.

本文提出了一种使用并行计算技术的快速、高效的 PC 算法，并在高维数据集和 miRNA-mRNA 调节关系推断中进行了应用和实验，结果表明该算法比原始 PC 算法更加高效和准确。

多核 PC 算法高维因果发现快速实现

A fast PC algorithm for high dimensional causal discovery with  multi-core PCs

Canonical correlation analysis is a classical technique for exploring the
relationship between two sets of variables. It has important applications in
analyzing high dimensional datasets originated from genomics, imaging and other
fields. This paper considers adaptive minimax and computationally tractable
estimation of leading sparse canonical coefficient vectors in high dimensions.
First, we establish separate minimax estimation rates for canonical coefficient
vectors of each set of random variables under no structural assumption on
marginal covariance matrices. Second, we propose a computationally feasible
estimator to attain the optimal rates adaptively under an additional sample
size condition. Finally, we show that a sample size condition of this kind is
needed for any randomized polynomial-time estimator to be consistent, assuming
hardness of certain instances of the Planted Clique detection problem. The
result is faithful to the Gaussian models used in the paper. As a byproduct, we
obtain the first computational lower bounds for sparse PCA under the Gaussian
single spiked covariance model.

本文探讨了适应性极小化和可计算的高维度下领先的稀疏规范系数向量的估计方法，得出了基于高斯模型的计算下限，并提出了第一个基于高斯单钉合模型的稀疏 PCA 的计算下限。

稀疏 CCA：自适应估计与计算障碍

Sparse CCA: Adaptive Estimation and Computational Barriers

We present several theoretical contributions which allow Lie groups to be fit
to high dimensional datasets. Transformation operators are represented in their
eigen-basis, reducing the computational complexity of parameter estimation to
that of training a linear transformation model. A transformation specific
"blurring" operator is introduced that allows inference to escape local minima
via a smoothing of the transformation space. A penalty on traversed manifold
distance is added which encourages the discovery of sparse, minimal distance,
transformations between states. Both learning and inference are demonstrated
using these methods for the full set of affine transformations on natural image
patches. Transformation operators are then trained on natural video sequences.
It is shown that the learned video transformations provide a better description
of inter-frame differences than the standard motion model based on rigid
translation.

该论文提出了一种方法，可以将 Lie 群适配到高维数据集上，通过一个特定的模糊算子使推理可以逃脱局部最小值，鼓励发现稀疏的、最小距离的状态之间的变换，同时演示了如何在自然图像补丁和自然视频序列上进行变换学习和推理。