A Topological Approach to Inferring the Intrinsic Dimension of Convex Sensing Data

• URL: http://arxiv.org/abs/2007.03208v1
• Date: Tue, 7 Jul 2020 05:35:23 GMT
• Title: A Topological Approach to Inferring the Intrinsic Dimension of Convex Sensing Data
• Authors: Min-Chun Wu, Vladimir Itskov
• Abstract summary: We consider a common measurement paradigm, where an unknown subset of an affine space is measured by unknown quasi- filtration functions. In this paper, we develop a method for inferring the dimension of the data under natural assumptions.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a common measurement paradigm, where an unknown subset of an affine space is measured by unknown continuous quasi-convex functions. Given the measurement data, can one determine the dimension of this space? In this paper, we develop a method for inferring the intrinsic dimension of the data from measurements by quasi-convex functions, under natural generic assumptions. The dimension inference problem depends only on discrete data of the ordering of the measured points of space, induced by the sensor functions. We introduce a construction of a filtration of Dowker complexes, associated to measurements by quasi-convex functions. Topological features of these complexes are then used to infer the intrinsic dimension. We prove convergence theorems that guarantee obtaining the correct intrinsic dimension in the limit of large data, under natural generic assumptions. We also illustrate the usability of this method in simulations.

Related papers

• The signaling dimension in generalized probabilistic theories [48.99818550820575]
  The signaling dimension of a given physical system quantifies the minimum dimension of a classical system required to reproduce all input/output correlations of the given system. We show that it suffices to consider extremal measurements with rayextremal effects, and we bound the number of elements of any such measurement in terms of the linear dimension. For systems with a finite number of extremal effects, we recast the problem of characterizing the extremal measurements with ray-extremal effects.
  arXiv  Detail & Related papers  (2023-11-22T02:09:16Z)
• Intrinsic Dimension for Large-Scale Geometric Learning [0.0]
  A naive approach to determine the dimension of a dataset is based on the number of attributes. More sophisticated methods derive a notion of intrinsic dimension (ID) that employs more complex feature functions.
  arXiv  Detail & Related papers  (2022-10-11T09:50:50Z)
• Intrinsic dimension estimation for discrete metrics [65.5438227932088]
  In this letter we introduce an algorithm to infer the intrinsic dimension (ID) of datasets embedded in discrete spaces. We demonstrate its accuracy on benchmark datasets, and we apply it to analyze a metagenomic dataset for species fingerprinting. This suggests that evolutive pressure acts on a low-dimensional manifold despite the high-dimensionality of sequences' space.
  arXiv  Detail & Related papers  (2022-07-20T06:38:36Z)
• Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddings [97.12538243736705]
  We study reinforcement learning with function approximation for large-scale Partially Observable Decision Processes (POMDPs) Our algorithm provably scales to large-scale POMDPs.
  arXiv  Detail & Related papers  (2022-06-24T05:13:35Z)
• Intrinsic Dimension Estimation [92.87600241234344]
  We introduce a new estimator of the intrinsic dimension and provide finite sample, non-asymptotic guarantees. We then apply our techniques to get new sample complexity bounds for Generative Adversarial Networks (GANs) depending on the intrinsic dimension of the data.
  arXiv  Detail & Related papers  (2021-06-08T00:05:39Z)
• A Unifying and Canonical Description of Measure-Preserving Diffusions [60.59592461429012]
  A complete recipe of measure-preserving diffusions in Euclidean space was recently derived unifying several MCMC algorithms into a single framework. We develop a geometric theory that improves and generalises this construction to any manifold.
  arXiv  Detail & Related papers  (2021-05-06T17:36:55Z)
• Manifold Learning via Manifold Deflation [105.7418091051558]
  dimensionality reduction methods provide a valuable means to visualize and interpret high-dimensional data. Many popular methods can fail dramatically, even on simple two-dimensional Manifolds. This paper presents an embedding method for a novel, incremental tangent space estimator that incorporates global structure as coordinates. Empirically, we show our algorithm recovers novel and interesting embeddings on real-world and synthetic datasets.
  arXiv  Detail & Related papers  (2020-07-07T10:04:28Z)
• ABID: Angle Based Intrinsic Dimensionality [0.0]
  The intrinsic dimensionality refers to the true'' dimensionality of the data, as opposed to the dimensionality of the data representation. Most popular methods for estimating the local intrinsic dimensionality are based on distances. We derive the theoretical distribution of angles and use this to construct an estimator for intrinsic dimensionality.
  arXiv  Detail & Related papers  (2020-06-23T10:19:34Z)

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.