Boundary Detection Algorithm Inspired by Locally Linear Embedding

• URL: http://arxiv.org/abs/2406.18456v1
• Date: Wed, 26 Jun 2024 16:05:57 GMT
• Title: Boundary Detection Algorithm Inspired by Locally Linear Embedding
• Authors: Pei-Cheng Kuo, Nan Wu,
• Abstract summary: We propose a method for detecting boundary points inspired by the widely used locally linear embedding algorithm. We implement this method using two nearest neighborhood search schemes: the $epsilon$-radius ball scheme and the $K$-nearest neighbor scheme.
• Score: 8.259071011958254
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the study of high-dimensional data, it is often assumed that the data set possesses an underlying lower-dimensional structure. A practical model for this structure is an embedded compact manifold with boundary. Since the underlying manifold structure is typically unknown, identifying boundary points from the data distributed on the manifold is crucial for various applications. In this work, we propose a method for detecting boundary points inspired by the widely used locally linear embedding algorithm. We implement this method using two nearest neighborhood search schemes: the $\epsilon$-radius ball scheme and the $K$-nearest neighbor scheme. This algorithm incorporates the geometric information of the data structure, particularly through its close relation with the local covariance matrix. We discuss the selection the key parameter and analyze the algorithm through our exploration of the spectral properties of the local covariance matrix in both neighborhood search schemes. Furthermore, we demonstrate the algorithm's performance with simulated examples.

Related papers

• Density based Spatial Clustering of Lines via Probabilistic Generation of Neighbourhood [0.0]
  In this paper, we design a clustering algorithm that generates a customised neighbourhood for a line of a fixed volume. This algorithm is not sensitive to the outliers and can effectively identify the noise in the data using a cardinality parameter. One of the pivotal applications of this algorithm is clustering data points in $mathbbRn$ with missing entries.
  arXiv  Detail & Related papers  (2024-10-03T08:17:11Z)
• Direction of Arrival Estimation with Sparse Subarrays [0.0]
  We introduce array architectures that incorporate two distinct array categories, namely type-I and type-II arrays. We devise two Direction of Arrival (DOA) estimation algorithms that are suitable for partially-calibrated array scenarios. The algorithms are capable of estimating a greater number of sources than the number of available physical sensors.
  arXiv  Detail & Related papers  (2024-08-17T23:47:24Z)
• 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)
• Learning Structure Aware Deep Spectral Embedding [11.509692423756448]
  We propose a novel structure-aware deep spectral embedding by combining a spectral embedding loss and a structure preservation loss. A deep neural network architecture is proposed that simultaneously encodes both types of information and aims to generate structure-aware spectral embedding. The proposed algorithm is evaluated on six publicly available real-world datasets.
  arXiv  Detail & Related papers  (2023-05-14T18:18:05Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Learning Implicit Feature Alignment Function for Semantic Segmentation [51.36809814890326]
  Implicit Feature Alignment function (IFA) is inspired by the rapidly expanding topic of implicit neural representations. We show that IFA implicitly aligns the feature maps at different levels and is capable of producing segmentation maps in arbitrary resolutions. Our method can be combined with improvement on various architectures, and it achieves state-of-the-art accuracy trade-off on common benchmarks.
  arXiv  Detail & Related papers  (2022-06-17T09:40:14Z)
• The decomposition of the higher-order homology embedding constructed from the $k$-Laplacian [5.076419064097734]
  The null space of the $k$-th order Laplacian $mathbfmathcal L_k$ encodes the non-trivial topology of a manifold or a network. We propose an algorithm to factorize the homology embedding into subspaces corresponding to a manifold's simplest topological components.
  arXiv  Detail & Related papers  (2021-07-23T00:40:01Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
  arXiv  Detail & Related papers  (2021-05-23T19:21:55Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  Adversarial examples are a widely studied phenomenon in machine learning models. We propose an algorithm for evaluating the adversarial robustness of $k$-nearest neighbor classification.
  arXiv  Detail & Related papers  (2020-11-19T08:49:10Z)
• Implicit Multidimensional Projection of Local Subspaces [42.86321366724868]
  We propose a visualization method to understand the effect of multidimensional projection on local subspaces. Our method is able to analyze the shape and directional information of the local subspace to gain more insights into the global structure of the data.
  arXiv  Detail & Related papers  (2020-09-07T17:27:27Z)
• 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)

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.