Common information was introduced by Wyner as a measure of dependence of tworandom 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 suchas communication complexity and combinatorial optimization.We begin a systematic study of common information extending the dual characterizationof 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 ofmatrix, 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) Wedeliver explicit witnesses from the dual problem for several matrices leading to explicit lowerbounds 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.