FoCM 2014 conference
Workshop C3 - Learning Theory
December 19, 14:30 ~ 15:00 - Room B23
Learning a Hidden Basis through Imperfect Measurements: Why and How
Misha Belkin
Ohio State University, USA - mbelkin@cse.ohio-state.edu
In this talk I will describe a general framework of inferring a hidden basis from imperfect measurements. I will show that a number of problems from the classical eigendecompositions of symmetric matrices to such topics of recent interest as multiclass spectral clustering, Independent Component Analysis and Gaussian mixture learning can be viewed as examples of hidden basis learning.
I will then describe algorithms for basis recovery and provide theoretical guarantees in terms of computational complexity and perturbation size. The proposed algorithms are based on what may be called "gradient iteration" and are simple to describe and to implement. They can be viewed as generalizations of both the classical power method for recovering eigenvectors of symmetric matrices as well as the recent work on power methods for tensors. Unlike these methods, our analysis is based not on tensorial properties, but on certain "hidden convexity" of constrast functions.
Joint work with L. Rademacher (Ohio State University) and J. Voss (Ohio State University).