Infinite families of graphs and stable completion of arbitrary matrices, Part I
By: Augustin Cosse
We study deterministic constructions of graphs for which the unique completion of low rank matrices is generically possible regardless of the values of the entries. We relate the completability to the presence of some patterns (particular unions of self-avoiding walks) in the subgraph of the lattice graph generated from the support of the bi-adjacency matrix. The construction makes it possible to design infinite families of graphs on which exact and stable completion is possible for every fixed rank matrix through the sum-of-squares hierarchy.
Similar Papers
Near-optimal Rank Adaptive Inference of High Dimensional Matrices
Information Theory
Finds hidden patterns in messy data.
Matrix Completion Survey: Theory, Algorithms, and Empirical Evaluation
Computation
Helps computers fill in missing data smartly.
Metrics on Permutation Families Defined by a Restriction Graph
Discrete Mathematics
Finds best ways to sort things using math.