# Boundary Detection Algorithm Inspired by Locally Linear Embedding

arXiv: https://arxiv.org/abs/2406.18456 · HTML: https://mlsanity.com/paper/2406.18456/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 43 references that are in the map.
- First posted on arXiv 26 Jun 2024.

## Builds on (most cited first, 12 of 12)

- [Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation](https://mlsanity.com/paper/2006.02037/) (2020)
- [Lipschitz regularity of graph Laplacians on random data clouds](https://mlsanity.com/paper/2007.06679/) (2020)
- [Convergence of Graph Laplacian with kNN Self-tuned Kernels](https://mlsanity.com/paper/2011.01479/) (2020)
- [Impact of signal-to-noise ratio and bandwidth on graph Laplacian spectrum from high-dimensional noisy point cloud](https://mlsanity.com/paper/2011.10725/) (2020)
- [BdryGP: a new Gaussian process model for incorporating boundary information](https://mlsanity.com/paper/1908.08868/) (2019)
- [Graph Based Gaussian Processes on Restricted Domains](https://mlsanity.com/paper/2010.07242/) (2020)
- [The embedding dimension of Laplacian eigenfunction maps](https://mlsanity.com/paper/1605.01643/) (2016)
- [Inferring manifolds using Gaussian processes](https://mlsanity.com/paper/2110.07478/) (2021)
- [Strong Uniform Consistency with Rates for Kernel Density Estimators with General Kernels on Manifolds](https://mlsanity.com/paper/2007.06408/) (2020)
- [Boundary Estimation from Point Clouds: Algorithms, Guarantees and Applications](https://mlsanity.com/paper/2111.03217/) (2021)
- [Set estimation from reflected Brownian motion](https://mlsanity.com/paper/1411.0433/) (2014)
- [Distributed boundary tracking using alpha and Delaunay-Cech shapes](https://mlsanity.com/paper/1302.3982/) (2013)

## Abstract (arXiv)

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.