Consistent line clustering using geometric hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911572721401856 |
|---|---|
| author | Alaluusua, Kalle Avrachenkov, Konstantin Kumar, B. R. Vinay Leskelä, Lasse |
| author_facet | Alaluusua, Kalle Avrachenkov, Konstantin Kumar, B. R. Vinay Leskelä, Lasse |
| contents | Subspace clustering becomes inherently difficult near intersections, where points from different subspaces are barely separated. Most existing theoretical results address this issue by imposing separation or sampling assumptions that limit the statistical effect of points near the intersection. We study a minimal setting of two intersecting lines in which the latent sampling law places polynomially large mass in small neighborhoods of the intersection. We derive information-theoretic lower bounds for exact and almost exact recovery under Gaussian noise. In particular, we show that the exact-recovery threshold is determined by the rate at which the latent law concentrates near the intersection. Since any two points are collinear, pairwise information alone does not reveal whether they are sampled from the same latent line. We therefore construct a hypergraph in which nearly collinear triples form hyperedges, and study the resulting hypergraph similarity matrix. Under a simple regularity condition on the latent distribution, we introduce a spectral algorithm that achieves the information-theoretic bounds up to polylogarithmic factors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_24868 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Consistent line clustering using geometric hypergraphs Alaluusua, Kalle Avrachenkov, Konstantin Kumar, B. R. Vinay Leskelä, Lasse Statistics Theory Machine Learning 62H30, 62R10, 62C20, 05C65, 05C80, 62H12, 94A15, 90B15 Subspace clustering becomes inherently difficult near intersections, where points from different subspaces are barely separated. Most existing theoretical results address this issue by imposing separation or sampling assumptions that limit the statistical effect of points near the intersection. We study a minimal setting of two intersecting lines in which the latent sampling law places polynomially large mass in small neighborhoods of the intersection. We derive information-theoretic lower bounds for exact and almost exact recovery under Gaussian noise. In particular, we show that the exact-recovery threshold is determined by the rate at which the latent law concentrates near the intersection. Since any two points are collinear, pairwise information alone does not reveal whether they are sampled from the same latent line. We therefore construct a hypergraph in which nearly collinear triples form hyperedges, and study the resulting hypergraph similarity matrix. Under a simple regularity condition on the latent distribution, we introduce a spectral algorithm that achieves the information-theoretic bounds up to polylogarithmic factors. |
| title | Consistent line clustering using geometric hypergraphs |
| topic | Statistics Theory Machine Learning 62H30, 62R10, 62C20, 05C65, 05C80, 62H12, 94A15, 90B15 |
| url | https://arxiv.org/abs/2505.24868 |