Graph Realization and Low-Rank Matrix Completion

Abstract

This thesis consists of five chapters, and focuses on two main problems: the graph realization problem with its applications to localization of sensor network and structural biology, and the low-rank matrix completion problem. Chapter 1 is a brief introduction to rigidity theory and supplies the background needed for the subsequent chapters. Chapter 2 introduces the graph realization problem in dimension two, and its application to sensor network localization. Chapter 3 considers the three dimensional graph realization problem and its application to the molecule problem from structural biology. Chapter 4 focuses on the group synchronization problem, and provides a more in-depth analysis of the synchronization methods used in our algorithms for the graph realization problem in R^2 and R^3. Finally, Chapter 5 investigates the problem of uniqueness of low-rank matrix completion, building on tools from rigidity theory.