# On the Sample Complexity of Subspace Learning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Aug 2014.

## Built on by (most cited first, 7 of 7)

- [A Rainbow in Deep Network Black Boxes](https://mlsanity.com/paper/2305.18512/) (2023)
- [Statistical Optimality and Computational Efficiency of Nystr"om Kernel PCA](https://mlsanity.com/paper/2105.08875/) (2021)
- [Vector-Valued Least-Squares Regression under Output Regularity Assumptions](https://mlsanity.com/paper/2211.08958/) (2022)
- [Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels](https://mlsanity.com/paper/2302.10128/) (2023)
- [Learning convolution operators on compact Abelian groups](https://mlsanity.com/paper/2501.05279/) (2025)
- [Kernel Trace Distance: Quantum Statistical Metric between Measures through RKHS Density Operators](https://mlsanity.com/paper/2507.06055/) (2025)
- [Fast Learning Rates for Physics-Informed Kernel Methods](https://mlsanity.com/paper/2609.18901/) (2026)

## Abstract (arXiv)

A large number of algorithms in machine learning, from principal component analysis (PCA), and its non-linear (kernel) extensions, to more recent spectral embedding and support estimation methods, rely on estimating a linear subspace from samples. In this paper we introduce a general formulation of this problem and derive novel learning error estimates. Our results rely on natural assumptions on the spectral properties of the covariance operator associated to the data distribu- tion, and hold for a wide class of metrics between subspaces. As special cases, we discuss sharp error estimates for the reconstruction properties of PCA and spectral support estimation. Key to our analysis is an operator theoretic approach that has broad applicability to spectral learning methods.