Published in:
We consider the problems of completing a low-rank positive semidefinite square
matrix $M$ or a low-rank rectangular matrix $N$ from a given subset of their entries. We study
the local and global uniqueness of such completions by analysing the structure of the graphs
determined by the positions of the known entries of $M$ or $N$.
We show that the unique completability testing of rectangular matrices is a special case of the unique completability testing of
positive semidefinite matrices. We prove that a generic partially filled matrix is globally uniquely
completable if any principal minor of size $n-1$ is locally uniquely completable.
These results are based on new geometric observations that extend similar results of the theory of rigid frameworks.
We also give an example showing that global completability is not a generic property in $\mathbb{R}^2$.
We provide sufficient conditions for two-dimensional local and global unique completability of an $n\times n$ matrix
by proving tight lower (resp. upper) bounds on the minimum number of known entries per row
on the total number of unknown entries, resp.) as a function of $n$.
Bibtex entry:
AUTHOR | = | {Jackson, Bill and Jord{\'a}n, Tibor and Tanigawa, Shin-ichi}, |
TITLE | = | {Unique low rank completability of partially filled matrices}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2015}, |
NUMBER | = | {TR-2015-08} |