Minimum rank positive semidefinite completions of sparse matrices with chordal sparsity patterns are easily computed via a recursion over the corresponding clique tree. This can be used, for example, to round solutions computed by semidefinite optimization algorithms based on matrix completion techniques. The talk will describe the minimum rank completion algorithm and applications to semidefinite relaxations.

Joint work with Xin Jiang, Martin Andersen, and Yifan Sun.