A tale of two subjects

Announcement: I have joined the mathematics division of the Chinese Academy of Sciences as Tenured Associate Professor (specifically, the Key Laboratory for Mathematics Mechanization, Academy of Mathematics and Systems Science). Students interested in doing research with me please read this.

With the advent of compressed sensing and robust principal component analysis in the 2000s and early 2010s, mathematical objects such as Grassmannians, low-rank matrices and subspace arrangements, have become important in solving machine learning and signal processing problems. In that context, they are most often treated from an optimization perspective. But these are also natural objects of algebraic geometry, the field of mathematics that studies solutions to polynomial systems of equations, a classical subject with deep technical foundations set in the second half of the 20th century. Examples where this algebraic geometric nature becomes necessary to call upon are low-rank matrix completion, subspace clustering, structure from motion, phase retrieval and linear regression without correspondences, where one needs to count dimensions or prove the injectivity of some algebraic map. At the same time, associated with these objects one finds related interesting questions within algebraic geometry itself (and its sister, commutative algebra), concerning notions such as Hilbert functions, free resolutions, Castelnuovo-Mumford regularity, Groebner bases and algebraic matroids. Besides their beauty, these interactions are fruitful in both directions. Some highlights:

  1. Exploiting the algebraic geometric nature of subspace arrangements, also known as unions of subspaces, leads to provably correct algorithms for data clustering. (pdf1,pdf2).

  2. A key ingredient in proving the correctness of these algorithms is the fact that the product ideal of a subspace arrangement has a linear resolution (pdf).

  3. Hyperplane arrangements can be used in a non-convex setting for data clustering in the high relative dimension case. The formulation naturally leads to a Fermat-Torricelli problem in the projective plane (pdf1,pdf2).

  4. The problem of low-rank matrix completion is intimately related to determinantal varieties, Grassmannians, Groebner bases and algebraic matroids (pdf1,pdf2).

  5. Unlabeled sensing, the problem of solving a linear system with the right-hand-side vector known only up to a permutation, can be posed as an algebraic geometry problem as well. Replacing permutations by arbitrary linear transformations leads to homomorphic sensing, which connects to determinantal varieties and generalizes to subspace arrangements (pdf1,pdf2,pdf3,pdf4).