WE2.R7.1

On the Asymptotic Nonnegative Rank of Matrices and its Applications in Information Theory

Yeow Meng Chee, National University of Singapore, Singapore; Quoc Tung Le, Toulouse School of Economics, Universit ́e de Toulouse, France; Hoang Ta, National University of Singapore, Singapore

Session:
Combinatorics and Information Theory 2

Track:
21: Other topics

Location:
VIP

Presentation Time:
Wed, 10 Jul, 11:30 - 11:50

Session Chair:
Shu Liu , University of Electronic Science and Technology of China
Abstract
In this paper, we study the asymptotic nonnegative rank of matrices, which characterizes the asymptotic growth of the nonnegative rank of fixed nonnegative matrices under the Kronecker product. This quantity is important since it governs several notions in information theory such as the so-called exact Rényi common information and the amortized communication complexity. By using the theory of asymptotic spectra of V. Strassen (J. Reine Angew. Math. 1988), we define formally the asymptotic spectrum of nonnegative matrices and give a dual characterization of the asymptotic nonnegative rank. As a complementary of the nonnegative rank, we introduce the notion of the subrank of a nonnegative matrix and show that it is exactly equal to the size of the maximum induced matching of the bipartite graph defined on the support of the matrix (therefore, independent of the value of entries). Finally, we show that two matrix parameters, namely rank and fractional cover number, belong to the asymptotic spectrum of nonnegative matrices.
Resources