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.

Correct typos.

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.

Improved presentation, fixed typos.

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.

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.