Construction of high-degree ramanujan graphs with applications to matrix completion

S P, Burnwal and M, Vidyasagar (2019) Construction of high-degree ramanujan graphs with applications to matrix completion. In: American Control Conference, ACC, 10-12 July 2019, Philadelphia, United States.

Full text not available from this repository. (Request a copy)

Abstract

The matrix completion problem can be stated as follows: Suppose Xin mathbb{R}-{n{1}times n{2}} is unknown except for an upper bound r on its rank. By measuring a small number mll n{1}n{2} of elements of X, is it possible to recover X exactly, or at least, to construct a reasonable approximation of X? There are two existing approaches to choosing the elements to be measured, namely: choosing them at random or in some deterministic fashion. Practically all of the existing literature focuses on the case where the sampled locations are chosen at random. In contrast, the focus in the present paper is on deterministic methods for choosing the elements to be sampled. Specifically, we choose the measurement matrix to be the adjacency or biadjacency matrix of a so-called Ramanujan graph. Existing explicit techniques for constructing Ramanujan graphs lead to graphs whose degree d is bounded by n-{1/3} where n is the number of vertices. However, for the matrix completion problem, this degree is too small. We point out that the well-known Lubotzky-Phillips-Sarnak construction of Ramanujan graphs can be used to generate graphs of very high degree, and use these for the matrix construction problem. Then we carry out numerical studies of 'phase transition' in the matrix completion problem, by comparing the behavior of sampling at random with choosing the sampled locations using a Ramanujan graph. Specifically, we show that for a fixed sampling pattern, there is a maximum rank bar{r} for which randomly generated matrices of rank rleqoverline{r} can be recovered with probability one, and the recovery probability drops very sharply to zero if r is increased by just two or three beyond bar{r}. The technique proposed here is applicable only to the recovery of square matrices. The recovery of rectangular matrices requires so-called asymmetric Ramanujan graphs, and is studied in a separate paper.

[error in script]

IITH Creators: