NDLI: Information-theoretic approximations of the nonnegative rank

Content Provider	Springer Nature Link
Author	Braun, Gábor Jain, Rahul Lee, Troy Pokutta, Sebastian
Copyright Year	2016
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 $${\ell_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 $${\ell_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.
Ending Page	197
Page Count	51
Starting Page	147
File Format	PDF
ISSN	10163328
e-ISSN	14208954
Journal	Computational complexity
Issue Number	1
Volume Number	26
Language	English
Publisher	Springer International Publishing
Publisher Date	2016-05-23
Publisher Place	Cham
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Nonnegative rank Measures of information, entropy Computational Mathematics and Numerical Analysis Common information Algorithm Analysis and Problem Complexity Information theory
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Lower Bounds for Agnostic Learning via Approximate Rank

A counterexample to the chain rule for conditional HILL entropy

Common Information and Unique Disjointness

Complexity of Solving Tropical Linear Systems

Dimension Characterizations of Complexity Classes

Halfspace Matrices

Extractors And Rank Extractors For Polynomial Sources

Multipartite Quantum Correlation and Communication Complexities

The complexity of estimating min-entropy

Information-theoretic approximations of the nonnegative rank

Similar Documents

Lower Bounds for Agnostic Learning via Approximate Rank

A counterexample to the chain rule for conditional HILL entropy

Common Information and Unique Disjointness

Complexity of Solving Tropical Linear Systems

Dimension Characterizations of Complexity Classes

Halfspace Matrices

Extractors And Rank Extractors For Polynomial Sources

Multipartite Quantum Correlation and Communication Complexities

The complexity of estimating min-entropy

Information-theoretic approximations of the nonnegative rank