Large sample spectral analysis of graph-based multi-manifold clustering
- URL: http://arxiv.org/abs/2107.13610v1
- Date: Wed, 28 Jul 2021 19:39:12 GMT
- Title: Large sample spectral analysis of graph-based multi-manifold clustering
- Authors: Nicolas Garcia Trillos, Pengfei He, Chenghui Li
- Abstract summary: We study statistical properties of graph-based algorithms for multi-manifold clustering (MMC)
In MMC the goal is to retrieve the multi-manifold structure underlying a given Euclidean data set.
We provide an example of a family of similarity graphs, which we call annular proximity graphs with angle constraints.
- Score: 3.383942690870476
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work we study statistical properties of graph-based algorithms for
multi-manifold clustering (MMC). In MMC the goal is to retrieve the
multi-manifold structure underlying a given Euclidean data set when this one is
assumed to be obtained by sampling a distribution on a union of manifolds
$\mathcal{M} = \mathcal{M}_1 \cup\dots \cup \mathcal{M}_N$ that may intersect
with each other and that may have different dimensions. We investigate
sufficient conditions that similarity graphs on data sets must satisfy in order
for their corresponding graph Laplacians to capture the right geometric
information to solve the MMC problem. Precisely, we provide high probability
error bounds for the spectral approximation of a tensorized Laplacian on
$\mathcal{M}$ with a suitable graph Laplacian built from the observations; the
recovered tensorized Laplacian contains all geometric information of all the
individual underlying manifolds. We provide an example of a family of
similarity graphs, which we call annular proximity graphs with angle
constraints, satisfying these sufficient conditions. We contrast our family of
graphs with other constructions in the literature based on the alignment of
tangent planes. Extensive numerical experiments expand the insights that our
theory provides on the MMC problem.
Related papers
- Gaussian Entanglement Measure: Applications to Multipartite Entanglement
of Graph States and Bosonic Field Theory [50.24983453990065]
An entanglement measure based on the Fubini-Study metric has been recently introduced by Cocchiarella and co-workers.
We present the Gaussian Entanglement Measure (GEM), a generalization of geometric entanglement measure for multimode Gaussian states.
By providing a computable multipartite entanglement measure for systems with a large number of degrees of freedom, we show that our definition can be used to obtain insights into a free bosonic field theory.
arXiv Detail & Related papers (2024-01-31T15:50:50Z) - Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure.
We introduce a new class of manifold, named soft manifold, that can solve this situation.
Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
arXiv Detail & Related papers (2023-11-29T12:48:33Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate.
To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
arXiv Detail & Related papers (2023-06-29T01:20:44Z) - Graph Fourier MMD for Signals on Graphs [67.68356461123219]
We propose a novel distance between distributions and signals on graphs.
GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation.
We showcase it on graph benchmark datasets as well as on single cell RNA-sequencing data analysis.
arXiv Detail & Related papers (2023-06-05T00:01:17Z) - Object based Bayesian full-waveform inversion for shear elastography [0.0]
We develop a computational framework to quantify uncertainty in shear elastography imaging of anomalies in tissues.
We find the posterior probability of parameter fields representing the geometry of the anomalies and their shear moduli.
We demonstrate the approach on synthetic two dimensional tests with smooth and irregular shapes.
arXiv Detail & Related papers (2023-05-11T08:25:25Z) - Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints.
The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution.
We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
arXiv Detail & Related papers (2022-10-21T13:19:45Z) - Partial Counterfactual Identification from Observational and
Experimental Data [83.798237968683]
We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data.
Our algorithms are validated extensively on synthetic and real-world datasets.
arXiv Detail & Related papers (2021-10-12T02:21:30Z) - Regularization of Mixture Models for Robust Principal Graph Learning [0.0]
A regularized version of Mixture Models is proposed to learn a principal graph from a distribution of $D$-dimensional data points.
Parameters of the model are iteratively estimated through an Expectation-Maximization procedure.
arXiv Detail & Related papers (2021-06-16T18:00:02Z) - Machine Learning and Variational Algorithms for Lattice Field Theory [1.198562319289569]
In lattice quantum field theory studies, parameters defining the lattice theory must be tuned toward criticality to access continuum physics.
We introduce an approach to "deform" Monte Carlo estimators based on contour deformations applied to the domain of the path integral.
We demonstrate that flow-based MCMC can mitigate critical slowing down and observifolds can exponentially reduce variance in proof-of-principle applications.
arXiv Detail & Related papers (2021-06-03T16:37:05Z) - Scaling Graph Clustering with Distributed Sketches [1.1011268090482575]
We present a method inspired by spectral clustering where we instead use matrix sketches derived from random dimension-reducing projections.
We show that our method produces embeddings that yield performant clustering results given a fully-dynamic block model stream.
We also discuss the effects of block model parameters upon the required dimensionality of the subsequent embeddings, and show how random projections could significantly improve the performance of graph clustering in distributed memory.
arXiv Detail & Related papers (2020-07-24T17:38:04Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.