Matrix Majorization in Large Samples

Farooq, MU; Fritz, T; Haapasalo, E; Tomamichel, M

Matrix Majorization in Large Samples

Farooq, MU Fritz, T Haapasalo, E Tomamichel, M

Permalink

Publisher:: IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
Publication Type:: Journal Article
Citation:: IEEE Transactions on Information Theory, 2024, 70, (5), pp. 3118-3144
Issue Date:: 2024-05-01

Closed Access

	Filename	Description	Size
	1700311.pdf	Published version	1.18 MB	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	Farooq, MU
dc.contributor.author	Fritz, T
dc.contributor.author	Haapasalo, E
dc.contributor.author	Tomamichel, M https://orcid.org/0000-0001-5410-3329
dc.date.accessioned	2024-08-07T04:40:41Z
dc.date.available	2024-08-07T04:40:41Z
dc.date.issued	2024-05-01
dc.identifier.citation	IEEE Transactions on Information Theory, 2024, 70, (5), pp. 3118-3144
dc.identifier.issn	0018-9448
dc.identifier.issn	1557-9654
dc.identifier.uri	http://hdl.handle.net/10453/180217
dc.description.abstract	One tuple of probability vectors is more informative than another tuple when there exists a single stochastic matrix transforming the probability vectors of the first tuple into the probability vectors of the other. This is called matrix majorization. Solving an open problem raised by Mu et al, we show that if certain monotones - namely multivariate extensions of Rényi divergences - are strictly ordered between the two tuples, then for sufficiently large n , there exists a stochastic matrix taking the n -fold Kronecker power of each input distribution to the n -fold Kronecker power of the corresponding output distribution. The same conditions, with non-strict ordering for the monotones, are also necessary for such matrix majorization in large samples. Our result also gives conditions for the existence of a sequence of statistical maps that asymptotically (with vanishing error) convert a single copy of each input distribution to the corresponding output distribution with the help of a catalyst that is returned unchanged. Allowing for transformation with arbitrarily small error, we find conditions that are both necessary and sufficient for such catalytic matrix majorization. We derive our results by building on a general algebraic theory of preordered semirings recently developed by one of the authors. This also allows us to recover various existing results on majorization in large samples and in the catalytic regime as well as relative majorization in a unified manner.
dc.language	English
dc.publisher	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
dc.relation.ispartof	IEEE Transactions on Information Theory
dc.relation.isbasedon	10.1109/TIT.2024.3352088
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0801 Artificial Intelligence and Image Processing, 0906 Electrical and Electronic Engineering, 1005 Communications Technologies
dc.subject.classification	Networking & Telecommunications
dc.subject.classification	4006 Communications engineering
dc.subject.classification	4613 Theory of computation
dc.title	Matrix Majorization in Large Samples
dc.type	Journal Article
utslib.citation.volume	70
utslib.for	0801 Artificial Intelligence and Image Processing
utslib.for	0906 Electrical and Electronic Engineering
utslib.for	1005 Communications Technologies
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
utslib.copyright.status	closed_access	*
dc.date.updated	2024-08-07T04:40:40Z
pubs.issue	5
pubs.publication-status	Published
pubs.volume	70
utslib.citation.issue	5

Abstract:

One tuple of probability vectors is more informative than another tuple when there exists a single stochastic matrix transforming the probability vectors of the first tuple into the probability vectors of the other. This is called matrix majorization. Solving an open problem raised by Mu et al, we show that if certain monotones - namely multivariate extensions of Rényi divergences - are strictly ordered between the two tuples, then for sufficiently large n , there exists a stochastic matrix taking the n -fold Kronecker power of each input distribution to the n -fold Kronecker power of the corresponding output distribution. The same conditions, with non-strict ordering for the monotones, are also necessary for such matrix majorization in large samples. Our result also gives conditions for the existence of a sequence of statistical maps that asymptotically (with vanishing error) convert a single copy of each input distribution to the corresponding output distribution with the help of a catalyst that is returned unchanged. Allowing for transformation with arbitrarily small error, we find conditions that are both necessary and sufficient for such catalytic matrix majorization. We derive our results by building on a general algebraic theory of preordered semirings recently developed by one of the authors. This also allows us to recover various existing results on majorization in large samples and in the catalytic regime as well as relative majorization in a unified manner.

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

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