More Like this

1. Clustering and visualization of single-cell RNA-seq data using path metrics

   https://doi.org/10.1371/journal.pcbi.1012014  

   Manousidaki, Andriana; Little, Anna; Xie, Yuying (May 2024, PLOS Computational Biology)

   Zhang, Shihua (Ed.)

   Recent advances in single-cell technologies have enabled high-resolution characterization of tissue and cancer compositions. Although numerous tools for dimension reduction and clustering are available for single-cell data analyses, these methods often fail to simultaneously preserve local cluster structure and global data geometry. To address these challenges, we developed a novel analyses framework,Single-CellPathMetricsProfiling (scPMP), using power-weighted path metrics, which measure distances between cells in a data-driven way. Unlike Euclidean distance and other commonly used distance metrics, path metrics are density sensitive and respect the underlying data geometry. By combining path metrics with multidimensional scaling, a low dimensional embedding of the data is obtained which preserves both the global data geometry and cluster structure. We evaluate the method both for clustering quality and geometric fidelity, and it outperforms current scRNAseq clustering algorithms on a wide range of benchmarking data sets. 

   more » « less
2. Sample-efficient geometry reconstruction from euclidean distances using non-convex optimization

   Ghosh, Ipsita; Tasissa, Abiy; Kümmerle, Christian (December 2024, Neural Information Processing Systems Foundation, Inc. (NeurIPS))

   The problem of finding suitable point embedding or geometric configurations given only Euclidean distance information of point pairs arises both as a core task and as a sub-problem in a variety of machine learning applications. In this paper, we aim to solve this problem given a minimal number of distance samples. To this end, we leverage continuous and non-convex rank minimization formulations of the problem and establish a local convergence guarantee for a variant of iteratively reweighted least squares (IRLS), which applies if a minimal random set of observed distances is provided. As a technical tool, we establish a restricted isometry property (RIP) restricted to a tangent space of the manifold of symmetric rank- matrices given random Euclidean distance measurements, which might be of independent interest for the analysis of other non-convex approaches. Furthermore, we assess data efficiency, scalability and generalizability of different reconstruction algorithms through numerical experiments with simulated data as well as real-world data, demonstrating the proposed algorithm's ability to identify the underlying geometry from fewer distance samples compared to the state-of-the-art. The Matlab code can be found at https://github.com/ipsita-ghosh-1/EDG-IRLS. 

   more » « less
3. Intrinsic Riemannian Metrics on Spaces of Curves: Theory and Computation

   https://doi.org/10.1007/978-3-030-03009-4_87-1  

   Bauer, Martin; Charon, Nicolas; Klassen, Eric; Le_Brigant, Alice (January 2021, Springer International Publishing)

   This chapter reviews some past and recent developments in shape comparison and analysis of curves based on the computation of intrinsic Riemannian metrics on the space of curve modulo shape-preserving transformations. We summarize the general construction and theoretical properties of quotient elastic metrics for Euclidean as well as non-Euclidean curves before considering the special case of the square root velocity metric for which the expression of the resulting distance simplifies through a particular transformation. We then examine the different numerical approaches that have been proposed to estimate such distances in practice and in particular to quotient out curve reparametrization in the resulting minimization problems. 

   more » « less
4. Linear Distance Metric Learning with Noisy Labels

   Alishahi, Meysam; Little, Anna; Phillips, Jeff M (April 2024, Journal of machine learning research)

   In linear distance metric learning, we are given data in one Euclidean metric space and the goal is to find an appropriate linear map to another Euclidean metric space which respects certain distance conditions as much as possible. In this paper, we formalize a simple and elegant method which reduces to a general continuous convex loss optimization problem, and for different noise models we derive the corresponding loss functions. We show that even if the data is noisy, the ground truth linear metric can be learned with any precision provided access to enough samples, and we provide a corresponding sample complexity bound. Moreover, we present an effective way to truncate the learned model to a low-rank model that can provably maintain the accuracy in the loss function and in parameters -- the first such results of this type. Several experimental observations on synthetic and real data sets support and inform our theoretical results. 

   more » « less
5. Linear Distance Metric Learning with Noisy Labels

   Alishahi, Meysam; Little, Anna; Phillips, Jeff M (January 2024, Journal of Machine Learning Research)

   In linear distance metric learning, we are given data in one Euclidean metric space and the goal is to find an appropriate linear map to another Euclidean metric space which respects certain distance conditions as much as possible. In this paper, we formalize a simple and elegant method which reduces to a general continuous convex loss optimization problem, and for different noise models we derive the corresponding loss functions. We show that even if the data is noisy, the ground truth linear metric can be learned with any precision provided access to enough samples, and we provide a corresponding sample complexity bound. Moreover, we present an effective way to truncate the learned model to a low-rank model that can provably maintain the accuracy in the loss function and in parameters – the first such results of this type. Several experimental observations on synthetic and real data sets support and inform our theoretical results. 

   more » « less