Learning Manifolds with K-Means and K-Flats
We study the problem of estimating a manifold from random samples. In particular, we consider piecewise constant and piecewise linear estimators induced by k-means and k-flats, and analyze their performance. We extend previous results for k-means in two separate directions. First, we provide new results for k-means reconstruction on manifolds and, secondly, we prove reconstruction bounds for higher-order approximation (k-flats), for which no known results were previously available. While the results for k-means are novel, some of the technical tools are well-established in the literature. In the case of k-flats, both the results and the mathematical tools are new.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Flatsomatic: A Method for Compression of Somatic Mutation Profiles in Cancer
In this study, we present Flatsomatic - a Variational Auto Encoder (VAE) optimized to compress somatic mutations that allow for unbiased data compression whilst maintaining the signal. We compared two different neural ne…
ClusteringData CompressionFitting Flats to Flats
Affine subspaces of Euclidean spaces are also referred to as flats. A standard task in computer vision or more generally in engineering and applied sciences is fitting a flat to a set of points which is commonly solv…
FLatS: Principled Out-of-Distribution Detection with Feature-Based Likelihood Ratio Score
Detecting out-of-distribution (OOD) instances is crucial for NLP models in practical applications. Although numerous OOD detection methods exist, most of them are empirical. Backed by theoretical analysis, this paper adv…
Out-of-Distribution DetectionDiffusion $K$-means clustering on manifolds: provable exact recovery via semidefinite relaxations
We introduce the {\it diffusion $K$-means} clustering method on Riemannian submanifolds, which maximizes the within-cluster connectedness based on the diffusion distance. The diffusion $K$-means constructs a random walk …
ClusteringUnifying lower bounds on prediction dimension of convex surrogates
The convex consistency dimension of a supervised learning task is the lowest prediction dimension $d$ such that there exists a convex surrogate $L : \mathbb{R}^d \times \mathcal Y \to \mathbb R$ that is consistent for t…
Open-Ended Question AnsweringPrediction