chapter  15
22 Pages

Learning Sets and Subspaces

WithAlessandro Rudi, Guillermo D. Canas, Ernesto De Vito, Lorenzo Rosasco

Alessandro Rudi∗ DIBRIS, Università degli Studi di Genova and LCSL, Massachusetts Institute of Technology, and Istituto Italiano di Tecnologia

Guillermo D. Canas∗

Massachusetts Institute of Technology

Ernesto De Vito∗

DIMA, Università degli Studi di Genova

Lorenzo Rosasco∗ DIBRIS, Università degli Studi di Genova and LCSL, Massachusetts Institute of Technology, and Istituto Italiano di Tecnologia

15.1 Unsupervised Statistical Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 15.2 Subspace Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339

15.2.1 Problem Definition and Notation . . . . . . . . . . . . . . . . . . . . . . . 340 15.2.2 Subspace Estimators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 15.2.3 Performance Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 15.2.4 Summary of Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 15.2.5 Kernel PCA and Embedding Methods . . . . . . . . . . . . . . . . . . 343 15.2.6 Comparison with Previous Results in the Literature . . . 344

15.3 Set Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 15.3.1 Set Learning via Subspace Learning . . . . . . . . . . . . . . . . . . . . 345 15.3.2 Consistency Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347

15.4 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 15.5 Sketch of the Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 15.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352

Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353

We consider here the classic problem of support estimation, or learning a set from random samples, and propose a natural but novel approach to address it. We do this by investigating its connection with a seemingly distinct problem, namely subspace learning.