Conference Agenda

Overview and details of the sessions of this conference. Please select a date or location to show only sessions at that day or location. Please select a single session for detailed view (with abstracts and downloads if available).

 
Session Overview
Session
MS142: Algebraic geometry of low-rank matrix completion
Time:
Tuesday, 09/Jul/2019:
10:00am - 12:00pm

Location: Unitobler, F023
104 seats, 126m^2

Presentations
10:00am - 12:00pm

Algebraic geometry of low-rank matrix completion

Chair(s): Carlos Améndola (TU Munich), Daniel Irving Bernstein (MIT)

In a matrix completion problem, one is presented with a subset of entries of a matrix and wishes to find values for the remaining entries so that the completed matrix has a particular property. For example, one may want the completed matrix to have low rank or to be positive semidefinite. Such problems abound in application areas ranging from recommender systems (e.g. the "Netflix problem"), to rigidity theory, to compressed sensing, to maximum likelihood estimation for graphical models. Matrix completion problems also motivate many questions that can be considered fundamental within algebraic geometry. For example, studying low-rank matrix completion motivates the question: which coordinate projections of a given determinantal variety are dominant? What changes when one restricts to the real part of this determinantal variety? This minisymposium aims to bring together researchers who study algebraic aspects of matrix completion, both from theoretical and applied perspectives.

 

(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)

 

Real geometry of matrix completion

Rainer Sinn
FU Berlin

I will discuss matrix completion problems from the point of view of real algebraic geometry. This means that coordinate projections of rank varieties of matrices are the central object of study. Important invariants are called generic rank, typical rank, and maximum likelihood threshold.

 

Low algebraic dimension matrix completion

Greg Ongie
U Chicago

In the low rank matrix completion (LRMC) problem, the low rank assumption means that the columns (or rows) of the matrix to be completed are points on a low-dimensional linear algebraic variety. We extend this thinking to cases where the columns are points on a low-dimensional nonlinear algebraic variety, a problem we call Low Algebraic Dimension Matrix Completion (LADMC). Matrices whose columns belong to a union of subspaces are an important special case. We propose a LADMC algorithm that leverages existing LRMC methods on a tensorized representation of the data. This approach succeeds in many cases where traditional LRMC is guaranteed to fail because the data are low-rank in the tensorized representation but not in the original representation. We also provide a formal mathematical justification for the success of our method. In particular, we show bounds of the rank of these data in the tensorized representation, and prove sampling requirements on the number of observed entries per column necessary and sufficient to guarantee uniqueness of the completion. We also provide experimental results showing that the new approach significantly outperforms existing state-of-the-art methods for matrix completion in many situations.

 

The tropical Cayley-Menger variety

Daniel Irving Bernstein
MIT

Varieties that arise in the algebraic study of matrix completion come embedded in a vector space whose coordinates are indexed by some graph. A recurring problem is to find combinatorial descriptions, in terms of these graphs, of the algebraic matroids underlying these varieties. Tropical geometry can be used to solve such problems. In this talk, I will show that the tropicalization of the Cayley-Menger variety of points in the plane has a simplicial complex structure that can be described in terms of rooted trees. Then, I will show how one can use this to obtain a new proof of Laman's theorem, a celebrated theorem from rigidity theory giving a combinatorial description of the algebraic matroid underlying the Cayley-Menger variety of points in the plane.

 

Unlabelled global rigidity and low-rank matrix completion

Louis Theran
University of St. Andrews

A graph $G$ with $n$ is said to be generically globally rigid in dimension $d$ if we can reconstruct an unknown, but generic, set of $n$ points in $d$-dimensional Euclidean space from the pairwise distance measurements indexed by the edges of $G$. Perhaps surprisingly, even when $G$ is an unknown generically globally rigid graph, it is still possible to reconstruct the original points from the distance measurements. Despite the fact that global rigidity is a special case of low-rank matrix completion, the analogous unlabelled matrix completion problem is mostly open. I’ll talk about both problems and some key differences. This talk is based on joint work with Shlomo Gortler and Dylan Thurston.