Burnwal, Shantanu Prasad and Vidyasagar, Mathukumalli
(2019)
Completion of Rectangular Matrices Using Asymmetric Ramanujan Graphs.
In: 58th IEEE Conference on Decision and Control, CDC, 11-13 December 2019, France.
Full text not available from this repository.
(
Request a copy)
Abstract
In this paper we study the matrix completion problem: Suppose X \in {{\mathbb{R}}^{{n-r} \times {n-c}}} is unknown except for an upper bound r on its rank. By measuring a small number m ≪ nrnc of elements of X, is it possible to recover X exactly, or at least, to construct a reasonable approximation of X The focus in the present paper is on deterministic methods for choosing the elements to be sampled, specifically, as the edge set of an asymmetric Ramanujan graph. For such a measurement matrix, we derive bounds on the error between a scaled version of the sampled matrix and unknown matrix. These bounds are an improvement on known results for square matrices.While some techniques exist for constructing Ramanujan bipartite graphs with equal numbers of vertices on both sides, until now no methods exist for constructing Ramanujan bipartite graphs with unequal numbers of vertices on the two sides. We provide a method for the construction of an infinite family of asymmetric biregular Ramanujan graphs with q left vertices and lq right vertices, where q is any prime number and l is any integer between 2 and q. The left degree is l and the right degree is q. So far as the authors are aware, this is the first explicit constuction of an asymmetric Ramanujan graph.
Actions (login required)
 |
View Item |
Altmetric
Altmetric