Higher Order Principal Components: Complexity and Applications

Standard Principal Components are directions that optimize second moments of a given set of points and have proven to be a powerful tool. Here we consider higher order principal components, i.e., directions that optimize higher moments of a data set (or the spectral norm of higher-dimensional arrays). They appear to be much less structured — there could be exponentially many, need not be pairwise orthogonal and it is NP-hard to find global maxima for arbitrary inputs.
We discuss applications to combinatorial optimization and learning: (a) finding a planted clique in a random graph, where higher-order maxima even for semi-random inputs would be effective and (b) learning an unknown function of a low-dimensional subspace from labeled examples (a k-subspace junta, generalizing the well-known class of k-juntas), where *local* optima suffice and can be approximated efficiently for a wide class of input distributions.
Most of the talk is joint work with Ying Xiao.

发言人详细信息

Santosh Vempala is Distinguished Professor of Computer Science and currently serves as the Director of the Algorithms, Randomness and Complexity Center (ARC) at Georgia Tech. His research interests are, ironically, in algorithms, randomness and complexity. He graduated from CMU in 1997, advised by Avrim Blum and was at MIT until 2006 except for a year at UC Berkeley. He has written two books, “The Random Projection Method,” (2004) and “Spectral Algorithms” (with Ravi Kannan, 2009) and is working on a third titled, “How to be(at) Kalai.” Vempala continues to get unreasonably excited when a phenomenon that appears complex from one perspective turns out to be simple from another. More information can be found on his webpage: http://www.cc.gatech.edu/~vempala

日期：
演讲者：
Santosh Vempala
所属机构：
Georgia Tech