Fall 2014

Matrix Completion for the Independence Model

Monday, October 13th, 2014 4:00 pm4:25 pm

Add to Calendar


Calvin Lab Auditorium

We study the question when can a partial matrix be completed to a rank 1 probability matrix, i. e. a matrix with nonnegative entries which sum to 1. The motivation for studying the question comes from statistics: A lack of desired completion can provide a falsication test for partial observations to come from the independence model.

We first answer the question for diagonal partial matrices, then generalize it to block diagonal partial matrices and finally to arbitrary partial matrices. We show how to construct polynomial equations and inequalities that define the semialgebraic set of partial matrices which can be completed to rank 1 probability matrices. In case a partial matrix has a desired completion, we give an algorithm how to construct one, and if it has more than one such completion, we show how to construct a completion that minimizes the distance from a fixed probability distribution. We address the same questions also for diagonal partial tensors.

This talk is based on joint work with Zvi Rosen.