【报告摘要】Subspace clustering, also known as Generalized Principal Component Analysis, is a classical unsupervised machine learning paradigm, where one is given a set of points in affine space coming from a union X of n linear subspaces, and the task is that of clustering the points according to their subspace membership. Algebraic approaches to solving this problem, pioneered by Vidal-Ma-Sastry (2003-2005), consist in fitting homogeneous polynomials to the given points, and extracting bases for the orthogonal complements of the subspaces from their gradients. The correctness of such an approach relies on fitting polynomials of sufficiently high degree, so that all generators of the vanishing ideal I_X of X are captured. By a theorem of Derksen-Sidman (2002), the Castelnuovo-Mumford regularity of I_X is bounded above by n, and thus I_X is generated at most up to degree n. In turn, this leads to a high computational complexity of existing algebraic subspace clustering algorithms, which limits their applicability. This talk will present a bound on the regularity of I_X of the order of the square root of n, valid for generic subspaces of codimension at least 2. This is a result proved recently in collaboration with AMSS PhD students Hong Xin and Yi-Song Huang. Besides being the only sublinear bound we are aware of, except for those implied by the landmark work of Harsthorne-Hirschowitz (1981) for subspaces of dimensions less than or equal to 2, this result is expected to lead to a considerable reduction in the computational complexity of algebraic subspace clustering algorithms.

【报告人简介】Manolis C. Tsakiris holds a PhD in commutative algebra advised by Aldo Conca, and a PhD in theoretical machine learning advised by Rene Vidal. His research is concerned with problems where  these two fields interact, as well as with intrinsic questions within commutative algebra and algebraic geometry. He publishes in journals such as JEMS, ANT, IEEE PAMI, JMLR, e.t.c.  From 2017 to 2022 he was an Assistant Professor at ShanghaiTech University in Shanghai, and since 2022 he is an Associate Professor at the Academy of Mathematics and Systems Science in Beijing.