Information-theoretic approximations of the nonnegative rank

Braun, G; Jain, R; Lee, T; Pokutta, S

Information-theoretic approximations of the nonnegative rank

Braun, G Jain, R Lee, T

Pokutta, S

Permalink

Publisher:: Springer
Publication Type:: Journal Article
Citation:: Computational Complexity, 2017, 26, (1), pp. 147-197
Issue Date:: 2017-03-01

Closed Access

	Filename	Description	Size
	s00037-016-0125-z.pdf		765.75 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Braun, G
dc.contributor.author	Jain, R
dc.contributor.author	Lee, T https://orcid.org/0000-0001-6912-2338
dc.contributor.author	Pokutta, S
dc.date.accessioned	2022-08-17T03:12:00Z
dc.date.available	2022-08-17T03:12:00Z
dc.date.issued	2017-03-01
dc.identifier.citation	Computational Complexity, 2017, 26, (1), pp. 147-197
dc.identifier.issn	1016-3328
dc.identifier.issn	1420-8954
dc.identifier.uri	http://hdl.handle.net/10453/160415
dc.description.abstract	Common information was introduced by Wyner (IEEE Trans Inf Theory 21(2):163–179, 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 Braun and Pokutta (Proceedings of FOCS, 2013) and Jain et al. (Proceedings of SODA, 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 (SIAM J Appl Math 31(2):313–333, 1976). Our main results are: (i) Common information is additive under tensoring 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 ℓ1 perturbations. We also provide quantitative bounds generalizing previous asymptotic results by Wyner (IEEE Trans Inf Theory 21(2):163–179, 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 ℓ1 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.
dc.language	en
dc.publisher	Springer
dc.relation.ispartof	Computational Complexity
dc.relation.isbasedon	10.1007/s00037-016-0125-z
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0801 Artificial Intelligence and Image Processing, 0802 Computation Theory and Mathematics, 1702 Cognitive Sciences
dc.subject.classification	Computation Theory & Mathematics
dc.title	Information-theoretic approximations of the nonnegative rank
dc.type	Journal Article
utslib.citation.volume	26
utslib.for	0801 Artificial Intelligence and Image Processing
utslib.for	0802 Computation Theory and Mathematics
utslib.for	1702 Cognitive Sciences
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	closed_access	*
pubs.consider-herdc	false
dc.date.updated	2022-08-17T03:11:59Z
pubs.issue	1
pubs.publication-status	Published
pubs.volume	26
utslib.citation.issue	1

Abstract:

Common information was introduced by Wyner (IEEE Trans Inf Theory 21(2):163–179, 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 Braun and Pokutta (Proceedings of FOCS, 2013) and Jain et al. (Proceedings of SODA, 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 (SIAM J Appl Math 31(2):313–333, 1976). Our main results are: (i) Common information is additive under tensoring 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 ℓ1 perturbations. We also provide quantitative bounds generalizing previous asymptotic results by Wyner (IEEE Trans Inf Theory 21(2):163–179, 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 ℓ1 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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/160415