skip to main content

Title: Homotopy Reconstruction via the Cech Complex and the Vietoris-Rips Complex
We derive conditions under which the reconstruction of a target space is topologically correct via the Čech complex or the Vietoris-Rips complex obtained from possibly noisy point cloud data. We provide two novel theoretical results. First, we describe sufficient conditions under which any non-empty intersection of finitely many Euclidean balls intersected with a positive reach set is contractible, so that the Nerve theorem applies for the restricted Čech complex. Second, we demonstrate the homotopy equivalence of a positive μ-reach set and its offsets. Applying these results to the restricted Čech complex and using the interleaving relations with the Čech complex (or the Vietoris-Rips complex), we formulate conditions guaranteeing that the target space is homotopy equivalent to the Čech complex (or the Vietoris-Rips complex), in terms of the μ-reach. Our results sharpen existing results.
; ; ; ;
Award ID(s):
Publication Date:
Journal Name:
Leibniz international proceedings in informatics
36th International Symposium on Computational Geometry (SoCG 2020)
Page Range or eLocation-ID:
Sponsoring Org:
National Science Foundation
More Like this
  1. We consider the topological and geometric reconstruction of a geodesic subspace of [Formula: see text] both from the Čech and Vietoris-Rips filtrations on a finite, Hausdorff-close, Euclidean sample. Our reconstruction technique leverages the intrinsic length metric induced by the geodesics on the subspace. We consider the distortion and convexity radius as our sampling parameters for the reconstruction problem. For a geodesic subspace with finite distortion and positive convexity radius, we guarantee a correct computation of its homotopy and homology groups from the sample. This technique provides alternative sampling conditions to the existing and commonly used conditions based on weak feature size and [Formula: see text]–reach, and performs better under certain types of perturbations of the geodesic subspace. For geodesic subspaces of [Formula: see text], we also devise an algorithm to output a homotopy equivalent geometric complex that has a very small Hausdorff distance to the unknown underlying space.
  2. Let [Formula: see text] be a group acting properly and by isometries on a metric space [Formula: see text]; it follows that the quotient or orbit space [Formula: see text] is also a metric space. We study the Vietoris–Rips and Čech complexes of [Formula: see text]. Whereas (co)homology theories for metric spaces let the scale parameter of a Vietoris–Rips or Čech complex go to zero, and whereas geometric group theory requires the scale parameter to be sufficiently large, we instead consider intermediate scale parameters (neither tending to zero nor to infinity). As a particular case, we study the Vietoris–Rips and Čech thickenings of projective spaces at the first scale parameter where the homotopy type changes.
  3. Copy number changes play an important role in the development of cancer and are commonly associated with changes in gene expression. Persistence curves, such as Betti curves, have been used to detect copy number changes; however, it is known these curves are unstable with respect to small perturbations in the data. We address the stability of lifespan and Betti curves by providing bounds on the distance between persistence curves of Vietoris–Rips filtrations built on data and slightly perturbed data in terms of the bottleneck distance. Next, we perform simulations to compare the predictive ability of Betti curves, lifespan curves (conditionally stable) and stable persistent landscapes to detect copy number aberrations. We use these methods to identify significant chromosome regions associated with the four major molecular subtypes of breast cancer: Luminal A, Luminal B, Basal and HER2 positive. Identified segments are then used as predictor variables to build machine learning models which classify patients as one of the four subtypes. We find that no single persistence curve outperforms the others and instead suggest a complementary approach using a suite of persistence curves. In this study, we identified new cytobands associated with three of the subtypes: 1q21.1-q25.2, 2p23.2-p16.3, 23q26.2-q28 with the Basalmore »subtype, 8p22-p11.1 with Luminal B and 2q12.1-q21.1 and 5p14.3-p12 with Luminal A. These segments are validated by the TCGA BRCA cohort dataset except for those found for Luminal A.« less
  4. The computation of Vietoris-Rips persistence barcodes is both execution-intensive and memory-intensive. In this paper, we study the computational structure of Vietoris-Rips persistence barcodes, and identify several unique mathematical properties and algorithmic opportunities with connections to the GPU. Mathematically and empirically, we look into the properties of apparent pairs, which are independently identifiable persistence pairs comprising up to 99% of persistence pairs. We give theoretical upper and lower bounds of the apparent pair rate and model the average case. We also design massively parallel algorithms to take advantage of the very large number of simplices that can be processed independently of each other. Having identified these opportunities, we develop a GPU-accelerated software for computing Vietoris-Rips persistence barcodes, called Ripser++. The software achieves up to 30x speedup over the total execution time of the original Ripser and also reduces CPU-memory usage by up to 2.0x. We believe our GPU-acceleration based efforts open a new chapter for the advancement of topological data analysis in the post-Moore's Law era.
  5. A recent advance in the synthesis of alkenylated arenes was the demonstration that the Pd(OAc)2 catalyst precursor gives >95% selectivity toward styrene from ethylene and benzene under optimized conditions using excess Cu(II) carboxylate as the in situ oxidant [ Organometallics 2019, 38(19), 3532−3541]. To understand the mechanism underlying this catalysis, we applied density functional theory (DFT) calculations in combination with experimental studies. From DFT calculations, we determined the lowest-energy multimetallic Pd and Pd–Cu mixed metal species as possible catalyst precursors. From the various structures, we determined the cyclic heterotrinuclear complex PdCu2(μ-OAc)6 to be the global minimum in Gibbs free energy under conditions of excess Cu(II). For cyclic PdCu2(μ-OAc)6 and the parent [Pd(μ-OAc)2]3, we evaluated the barriers for benzene C–H activation through concerted metalation deprotonation (CMD). The PdCu2(μ-OAc)6 cyclic trimer leads to a CMD barrier of 33.5 kcal/mol, while the [Pd(μ-OAc)2]3 species leads to a larger CMD barrier at >35 kcal/mol. This decrease in the CMD barrier arises from the insertion of Cu(II) into the trimetallic species. Because cyclic PdCu2(μ-OAc)6 is likely the predominant species under experimental conditions (the Cu to Pd ratio is 480:1 at the start of catalysis) with a predicted CMD barrier within the range of the experimentallymore »determined activation barrier, we propose that cyclic PdCu2(μ-OAc)6 is the Pd species responsible for catalysis and report a full reaction mechanism based on DFT calculations. For catalytic conversion of benzene and ethylene to styrene at 120 °C using Pd(OAc)2 as the catalyst precursor and Cu(OPiv)2 (OPiv = pivalate) as the oxidant, an induction period of ∼1 h was observed, followed by catalysis with a turnover frequency of ∼2.3 × 10–3 s–1. In situ1H NMR spectroscopy experiments indicate that during the induction period, Pd(OAc)2 is likely converted to cyclic PdCu2(η2-C2H4)3(μ-OPiv)6, which is consistent with the calculations and consistent with the proposal that the active catalyst is the ethylene-coordinated heterotrinuclear complex cyclic PdCu2(η2-C2H4)3(μ-OPiv)6.« less