2025/05/30 by Kalle Alaluusua, Konstantin Avrachenkov, Alaluusua, Kalle +5
Computer Science · #05C65 #05C80 #62C20 #62H12 #62H30 #62R10 #90B15 #94A15 #FOS: Computer and information sciences #FOS: Mathematics #Graph Theory and Algorithms #Machine Learning (stat.ML) #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2505.24868
openalex publication_date 2025/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.