|
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.
Following the approach initiated by Singer and Cucuringu 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 present combinatorial characterizations
of local and global (unique) completability for special families of graphs.
We characterize local and global completability in all dimensions
for cluster graphs, i.e. graphs which
can be obtained from
disjoint complete graphs by adding a set of independent edges.
These results correspond to theorems for body-bar frameworks in rigidity
theory.
We also provide a characterization of two-dimensional local completability of
planar bipartite graphs, which leads to a characterization of
two-dimensional local
completability
in the rectangular matrix model when the underlying bipartite graph is planar.
These results are based on new observations that certain
graph operations preserve local
or global completability, as well as on a further connection between rigidity
and completability.
We also prove that a rank condition on the completability stress
matrix of a graph is a sufficient condition for
global completability. This verifies a conjecture of
Singer and Cucuringu.
Bibtex entry:
| AUTHOR | = | {Jackson, Bill and Jord{\'a}n, Tibor and Tanigawa, Shin-ichi}, |
| TITLE | = | {Combinatorial Conditions for the Unique Completability of Low Rank Matrices}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2014}, |
| NUMBER | = | {TR-2014-01} |