Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR13-158 | 2nd March 2016 20:07

Information-theoretic approximations of the nonnegative rank

RSS-Feed




Revision #3
Authors: Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta
Accepted on: 2nd March 2016 20:07
Downloads: 206
Keywords: 


Abstract:

Common information was introduced by Wyner as a measure of dependence of two
random variables. This measure has been recently resurrected as a lower bound on the logarithm of the nonnegative rank of a nonnegative matrix. Lower bounds on nonnegative rank have important applications to several areas such
as communication complexity and combinatorial optimization.
We begin a systematic study of common information extending the dual characterization
of Witsenhausen. Our main results are: (i) Common information is additive under ten-
soring of matrices. (ii) It characterizes the (logarithm of the) amortized nonnegative rank of
matrix, i.e., the minimal nonnegative rank under tensoring and small l perturbations. We pro-
vide quantitative bounds compared to an analogous asymptotic result by Wyner. (iii) We
deliver explicit witnesses from the dual problem for several matrices leading to explicit lower
bounds on common information, which are robust under l perturbations. This includes improved lower bounds for perturbations of the all important unique disjointness partial matrix,
as well as new insights into its information-theoretic structure.



Changes to previous version:

Correct typos.


Revision #2 to TR13-158 | 18th August 2015 20:30

Information-theoretic approximations of the nonnegative rank





Revision #2
Authors: Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta
Accepted on: 18th August 2015 20:30
Downloads: 238
Keywords: 


Abstract:

Common information was introduced by Wyner as a measure of dependence of two
random variables. This measure has been recently resurrected as a lower bound on the logarithm of the nonnegative rank of a nonnegative matrix. Lower bounds on nonnegative rank have important applications to several areas such
as communication complexity and combinatorial optimization.
We begin a systematic study of common information extending the dual characterization
of Witsenhausen. Our main results are: (i) Common information is additive under ten-
soring of matrices. (ii) It characterizes the (logarithm of the) amortized nonnegative rank of
matrix, i.e., the minimal nonnegative rank under tensoring and small l perturbations. We pro-
vide quantitative bounds compared to an analogous asymptotic result by Wyner. (iii) We
deliver explicit witnesses from the dual problem for several matrices leading to explicit lower
bounds on common information, which are robust under l perturbations. This includes improved lower bounds for perturbations of the all important unique disjointness partial matrix,
as well as new insights into its information-theoretic structure.



Changes to previous version:

Improved presentation, fixed typos.


Revision #1 to TR13-158 | 1st April 2014 15:36

Information-theoretic approximations of the nonnegative rank





Revision #1
Authors: Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta
Accepted on: 1st April 2014 15:36
Downloads: 572
Keywords: 


Abstract:

Common information was introduced by Wyner [1975] as a measure of dependence of two random variables. This measure has been recently resurrected as a lower bound on the logarithm of the nonnegative rank of a nonnegative matrix in Jain et al. [2013], Braun and Pokutta [2013]. Lower bounds on nonnegative rank have important applications to several areas such as communication complexity and combinatorial optimization.
We begin a systematic study of common information extending the dual characterization of Witsenhausen [1976]. Our main results are: (i) Common information is additive under ten- soring of matrices. (ii) It characterizes the (logarithm of the) amortized nonnegative rank of a matrix, i.e., the minimal nonnegative rank under tensoring and small l1 perturbations. We also provide quantitative bounds generalizing previous asymptotic results by Wyner [1975]. (iii) We deliver explicit witnesses from the dual problem for several matrices leading to explicit lower bounds on common information, which are robust under l1 perturbations. This includes im- proved lower bounds for perturbations of the all important unique disjointness partial matrix, as well as new insights into its information-theoretic structure.


Paper:

TR13-158 | 18th November 2013 18:02

Information-theoretic approximations of the nonnegative rank


Abstract:

Common information was introduced by Wyner as a measure of dependence of two
random variables. This measure has been recently resurrected as a lower bound on the logarithm of the nonnegative rank of a nonnegative matrix. Lower bounds on nonnegative rank have important applications to several areas such
as communication complexity and combinatorial optimization.
We begin a systematic study of common information extending the dual characterization
of Witsenhausen. Our main results are: (i) Common information is additive under ten-
soring of matrices. (ii) It characterizes the (logarithm of the) amortized nonnegative rank of
matrix, i.e., the minimal nonnegative rank under tensoring and small l perturbations. We pro-
vide quantitative bounds compared to an analogous asymptotic result by Wyner. (iii) We
deliver explicit witnesses from the dual problem for several matrices leading to explicit lower
bounds on common information, which are robust under l perturbations. This includes improved lower bounds for perturbations of the all important unique disjointness partial matrix,
as well as new insights into its information-theoretic structure.



ISSN 1433-8092 | Imprint