Title: Sparsification of large ultrametric matrices: insights into the microbial Tree of Life
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. more »« less
Sturmfels, Bernd; Uhler, Caroline; Zwiernik, Piotr
(, Kybernetika)
null
(Ed.)
Felsenstein's classical model for Gaussian distributions on a phylogenetic tree is shown to be a toric variety in the space of concentration matrices. We present an exact semialgebraic characterization of this model, and we demonstrate how the toric structure leads to exact methods for maximum likelihood estimation. Our results also give new insights into the geometry of ultrametric matrices.
Abstract Microbiome data from sequencing experiments contain the relative abundance of a large number of microbial taxa with their evolutionary relationships represented by a phylogenetic tree. The compositional and high-dimensional nature of the microbiome mediator challenges the validity of standard mediation analyses. We propose a phylogeny-based mediation analysis method called PhyloMed to address this challenge. Unlike existing methods that directly identify individual mediating taxa, PhyloMed discovers mediation signals by analyzing subcompositions defined on the phylogenic tree. PhyloMed produces well-calibrated mediation test p -values and yields substantially higher discovery power than existing methods.
Abstract Stochastic embeddings of finite metric spaces into graph-theoretic trees have proven to be a vital tool for constructing approximation algorithms in theoretical computer science. In the present work, we build out some of the basic theory of stochastic embeddings in the infinite setting with an aim toward applications to Lipschitz free space theory. We prove that proper metric spaces stochastically embedding into$$\mathbb {R}$$-trees have Lipschitz free spaces isomorphic to$$L^1$$-spaces. We then undergo a systematic study of stochastic embeddability of Gromov hyperbolic metric spaces into$$\mathbb {R}$$-trees by way of stochastic embeddability of their boundaries into ultrametric spaces. The following are obtained as our main results: (1) every snowflake of a compact, finite Nagata-dimensional metric space stochastically embeds into an ultrametric space and has Lipschitz free space isomorphic to$$\ell ^1$$, (2) the Lipschitz free space over hyperbolicn-space is isomorphic to the Lipschitz free space over Euclideann-space and (3) every infinite, finitely generated hyperbolic group stochastically embeds into an$$\mathbb {R}$$-tree, has Lipschitz free space isomorphic to$$\ell ^1$$, and admits a proper, uniformly Lipschitz affine action on$$\ell ^1$$.
Macias-Marques, Pedro; McDaniel, Chris; Seceleanu, Alexandra
(, International Mathematics Research Notices)
Abstract We define $$i$$-Lorentzian polynomials in two variables, and characterize them as the real homogeneous Macaulay dual generators whose corresponding codimension two algebras satisfy the mixed Hodge–Riemann relations in degree $$i$$ on the positive orthant of linear forms. We further show that $$i$$-Lorentzian polynomials of degree $$d$$ are in one-to-one correspondence with totally nonnegative Toeplitz matrices of size $$(i+1)\times (d-i+1)$$. Using this latter characterization, we show that a certain subclass of real rooted polynomials called normally stable are $$i$$-Lorentzian for all $$i$$. Our results also lead to a new theorem on Toeplitz matrices: the closure of the set of totally positive Toeplitz matrices equals the set of totally nonnegative Toeplitz matrices.
Abstract Precomputed Radiance Transfer (PRT) remains an attractive solution for real‐time rendering of complex light transport effects such as glossy global illumination. After precomputation, we can relight the scene with new environment maps while changing viewpoint in real‐time. However, practical PRT methods are usually limited to low‐frequency spherical harmonic lighting. All‐frequency techniques using wavelets are promising but have so far had little practical impact. The curse of dimensionality and much higher data requirements have typically limited them to relighting with fixed view or only direct lighting with triple product integrals. In this paper, we demonstrate a hybrid neural‐wavelet PRT solution to high‐frequency indirect illumination, including glossy reflection, for relighting with changing view. Specifically, we seek to represent the light transport function in the Haar wavelet basis. For global illumination, we learn the wavelet transport using a small multi‐layer perceptron (MLP) applied to a feature field as a function of spatial location and wavelet index, with reflected direction and material parameters being other MLP inputs. We optimize/learn the feature field (compactly represented by a tensor decomposition) and MLP parameters from multiple images of the scene under different lighting and viewing conditions. We demonstrate real‐time (512 x 512 at 24 FPS, 800 x 600 at 13 FPS) precomputed rendering of challenging scenes involving view‐dependent reflections and even caustics.
Gorman, Evan, and Lladser, Manuel E. Sparsification of large ultrametric matrices: insights into the microbial Tree of Life. Retrieved from https://par.nsf.gov/biblio/10495519. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 479.2277 Web. doi:10.1098/rspa.2022.0847.
Gorman, Evan, & Lladser, Manuel E. Sparsification of large ultrametric matrices: insights into the microbial Tree of Life. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 479 (2277). Retrieved from https://par.nsf.gov/biblio/10495519. https://doi.org/10.1098/rspa.2022.0847
Gorman, Evan, and Lladser, Manuel E.
"Sparsification of large ultrametric matrices: insights into the microbial Tree of Life". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 479 (2277). Country unknown/Code not available: The Royal Society Publishing. https://doi.org/10.1098/rspa.2022.0847.https://par.nsf.gov/biblio/10495519.
@article{osti_10495519,
place = {Country unknown/Code not available},
title = {Sparsification of large ultrametric matrices: insights into the microbial Tree of Life},
url = {https://par.nsf.gov/biblio/10495519},
DOI = {10.1098/rspa.2022.0847},
abstractNote = {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.},
journal = {Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences},
volume = {479},
number = {2277},
publisher = {The Royal Society Publishing},
author = {Gorman, Evan and Lladser, Manuel E.},
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.
An official website of the United States government
