Sparsification of large ultrametric matrices: insights into the microbial Tree of Life
Sparsification of large ultrametric matrices: insights into the microbial Tree of Life
复制标题
DOI：
10.1098/rspa.2022.0847
复制
发表时间：
2023-09-20
影响因子：
3.5
通讯作者：
Lladser，Manuel E.
中科院分区：
文献类型：
--
作者：
Gorman，Evan;Lladser，Manuel E.
超度量矩阵出现在数学和科学的许多领域;然而，它们可以是大的和密集的，使得它们难以存储和操作，不像大但稀疏的矩阵。在这篇文章中，我们利用超度量矩阵可以表示为二叉树，通过基于Haar小波的正交基变换来稀疏化它们。我们表明，具有压倒性的高概率，只有一个渐进的可忽略不计的分数的非对角项随机，但大超度量矩阵保持非零后，基地的变化，并开发一个算法，直接从他们的树表示稀疏这样的矩阵。我们还确定了类Haar小波对角化矩阵的子类，并提供了一个充分条件，以逼近该子类以外的超度量矩阵的谱。我们的方法计算访问微生物学家的生命树的协方差矩阵模型，这是以前无法访问的，由于其大小，并激励引入一个新的基于小波（β多样性）的度量来比较微生物环境。与已建立的度量不同，新度量可用于识别树中以统计学显著方式将微生物组成与环境因素联系起来的内部节点（即分裂）。
Ultrametric matrices appear in many domains of mathematics and science; nevertheless, they can be large and dense, making them difficult to store and manipulate, unlike large but sparse matrices. In this manuscript, we exploit that ultrametric matrices can be represented as binary trees to sparsify them via an orthonormal base change based on Haar-like wavelets. We show that, with overwhelmingly high probability, only an asymptotically negligible fraction of the off-diagonal entries in random but large ultrametric matrices remain non-zero after the base change; and develop an algorithm to sparsify such matrices directly from their tree representation. We also identify the subclass of matrices diagonalized by the Haar-like wavelets and supply a sufficient condition to approximate the spectrum of ultrametric matrices outside this subclass. Our methods give computational access to a covariance matrix model of the microbiologists’ Tree of Life, which was previously inaccessible due to its size, and motivate introducing a new wavelet-based (beta-diversity) metric to compare microbial environments. Unlike the established metrics, the new metric may be used to identify internal nodes (i.e. splits) in the Tree that link microbial composition and environmental factors in a statistically significant manner.