← Back to papers
2012 NIPS NeurIPS 2012

Learning Manifolds with K-Means and K-Flats

Abstract

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.

🧭 Keyword Pioneer — subspace approximation
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Interdisciplinary, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Speech & Audio
🐣 Hot Topic Early Bird — dimensionality reduction

Authors

Guillermo Canas , Tomaso Poggio , Lorenzo Rosasco

Topics

Machine Learning > Core Methods > Clustering Machine Learning > Core Methods > Representation Learning Machine Learning > Learning Types > Unsupervised Learning Machine Learning > Optimization & Theory > Theory Machine Learning > Core Methods > Dimensionality Reduction

Keywords

subspace clustering unsupervised learning dimensionality reduction manifold learning k-means clustering dimension reduction piecewise linear subspace approximation
Download PDF

Related papers

Kernel Hyperalignment 2012
Fused sparsity and robust estimation for linear models with unknown variance 2012
Slice sampling normalized kernel-weighted completely random measure mixture models 2012
Scaling MPE Inference for Constrained Continuous Markov Random Fields with Consensus Optimization 2012
Matrix reconstruction with the local max norm 2012