Boundary Detection Algorithm Inspired by Locally Linear Embedding

• URL: http://arxiv.org/abs/2406.18456v2
• Date: Wed, 20 Aug 2025 19:01:46 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.<n>In the presence of high-dimensional noise, we propose a framework aimed at enhancing boundary detection in noisy data.
• 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 analyze the algorithm by exploring the spectral properties of the local covariance matrix, with the findings guiding the selection of key parameters. In the presence of high-dimensional noise, we propose a framework aimed at enhancing boundary detection in noisy data. Furthermore, we demonstrate the algorithm's performance with simulated examples.

Related papers

• Robust Tangent Space Estimation via Laplacian Eigenvector Gradient Orthogonalization [48.25304391127552]
  Estimating the tangent spaces of a data manifold is a fundamental problem in data analysis.<n>We propose a method, Laplacian Eigenvector Gradient Orthogonalization (LEGO), that utilizes the global structure of the data to guide local tangent space estimation.
  arXiv  Detail & Related papers  (2025-10-02T17:59:45Z)
• Robust Multi-Manifold Clustering via Simplex Paths [10.304857373037596]
  This article introduces a novel, geometric approach for multi-manifold clustering (MMC)<n>We first compute a locality graph on d-simplices, using the dihedral angle in between adjacent simplices as the graph weights, and then compute infinity path distances in this simplex graph.<n>We analyze the properties of LAPD under random sampling, and prove that with an appropriate denoising procedure, this metric separates the manifold components with high probability.
  arXiv  Detail & Related papers  (2025-07-14T18:22:50Z)
• Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces [94.12116458306916]
  We show that in $q$-metric spaces, metric trees can leverage a stronger version of the triangle inequality to reduce comparisons for exact search.<n>We propose a novel projection method that embeds datasets with arbitrary dissimilarity measures into $q$-metric spaces.
  arXiv  Detail & Related papers  (2025-06-06T22:09:44Z)
• Diffusion-based Semi-supervised Spectral Algorithm for Regression on Manifolds [2.0649432688817444]
  We introduce a novel diffusion-based spectral algorithm to tackle regression analysis on high-dimensional data. Our method uses the local estimation property of heat kernel, offering an adaptive, data-driven approach to overcome this obstacle. Our algorithm performs in an entirely data-driven manner, operating directly within the intrinsic manifold structure of the data.
  arXiv  Detail & Related papers  (2024-10-18T15:29:04Z)
• 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)
• A Robust and Efficient Boundary Point Detection Method by Measuring Local Direction Dispersion [8.906932064891796]
  Boundary point detection aims to outline the external contour structure of clusters.<n>Existing boundary point detectors are sensitive to density or cannot identify boundary points in concave structures.<n>We propose a robust and efficient boundary point detection method based on Local Direction Dispersion (LoDD)
  arXiv  Detail & Related papers  (2023-12-07T06:09:21Z)
• 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)
• Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystr\"om method [76.73096213472897]
  We develop techniques which exploit spectral properties of the data matrix to obtain improved approximation guarantees. Our approach leads to significantly better bounds for datasets with known rates of singular value decay. We show that both our improved bounds and the multiple-descent curve can be observed on real datasets simply by varying the RBF parameter.
  arXiv  Detail & Related papers  (2020-02-21T00:43:06Z)

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.