Alladi Ramakrishnan Hall

Witnessing Nonnegative Rank

Hitesh Wankhede

IMSc

Given a real matrix of rank at least $d$, this fact can be witnessed by a full-rank submatrix of order $d$. Similar to the notion of real rank, we define nonnegative rank for (entry-wise) nonnegative matrices. Now given a nonnegative matrix with nonnegative rank at least $r$, it it known that this fact, unlike real rank, cannot always be witnessed exactly by a submatrix of order $r$. In this talk, we show that such a witnessing is possible approximately if witness size is allowed to be slightly larger than $r$.

This talk is a credit seminar. It is based on the paper "Hard submatrices for nonnegative rank and communication complexity" by Pavel Hrube\v{s} (2024).