Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2308.07187 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910309300568064 |
|---|---|
| author | Chee, Yeow Meng Le, Quoc Tung Ta, Hoang |
| author_facet | Chee, Yeow Meng Le, Quoc Tung Ta, Hoang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_07187 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Asymptotic Nonnegative Rank of Matrices and its Applications in Information Theory Chee, Yeow Meng Le, Quoc Tung Ta, Hoang Information Theory Computational Complexity Commutative Algebra 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. |
| title | On the Asymptotic Nonnegative Rank of Matrices and its Applications in Information Theory |
| topic | Information Theory Computational Complexity Commutative Algebra |
| url | https://arxiv.org/abs/2308.07187 |