Exact Completion of Rectangular Matrices Using Ramanujan Bigraphs

Burnwal, Shantanu Prasad and Vidyasagar, Mathukumalli (2020) Exact Completion of Rectangular Matrices Using Ramanujan Bigraphs. In: 2020 American Control Conference, ACC 2020, 1 July 2020through 3 July 2020, Denver.

Text
Control_Conference.pdf - Published Version
Restricted to Registered users only
Download (281kB) | 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? At present, there are two approaches to choosing the sample set, namely probabilistic and deterministic. Probabilistic methods can guarantee exact recovery of the unknown matrix, but only with high probability. In this approach, samples are taken uniformly at random. Therefore we need to start sampling for every new matrix afresh. In the deterministic approach, sampling points can be kept fixed. At present, there are very few deterministic methods, and they mostly apply only to square matrices. In this paper, we present a deterministic method for selecting the sample set that can guarantee the exact recovery of the unknown matrix. This approach works for the recovery of rectangular as well as square matrices. We achieve this by choosing the elements to be sampled as the edge set of a Ramanujan bigraph. If samples are the edge set of a Ramanujan bigraph, then we can recover the unknown matrix from that sample set using nuclear norm minimization. A companion paper discusses the explicit construction of Ramanujan bigraphs. We provide a sufficient condition, that is if the samples taken are of the order of r3 then we can recover the unknown entries exactly if the unknown matrix satisfies some coherence condition. We believe this the first sufficient condition available using deterministic sampling technique and nuclear norm minimization. © 2020 AACC.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Vidyasagar, Mathukumalli	UNSPECIFIED

Item Type:

Conference or Workshop Item (Paper)

Additional Information:

The authors are with the Indian Institute of Technology Hyderabad, Kandi, Telangana 502285, India. Emails: ee16resch11019@iith.ac.in, m.vidyasagar@iith.ac.in. This research was supported by the Department of Science and Technology, and the Science and Engineering Research Board, Government of India.

Uncontrolled Keywords:

Coherence conditions; Deterministic approach; Deterministic methods; Deterministic sampling; Explicit constructions; Matrix completion problems; Nuclear norm minimizations; Probabilistic methods

Subjects:

Electrical Engineering

Divisions:

Department of Electrical Engineering

Depositing User:

. LibTrainee 2021

Date Deposited:

03 Nov 2022 13:45

Last Modified:

03 Nov 2022 13:45

URI:

http://raiithold.iith.ac.in/id/eprint/11147