Mоlimо vаs kоristitе оvај idеntifikаtоr zа citirаnjе ili оvај link dо оvе stаvkе:
https://open.uns.ac.rs/handle/123456789/9364
Nаziv: | On the hardness of entropy minimization and related problems | Аutоri: | Kovačević, Marko Stanojević, Ivan Šenk, Vojin |
Dаtum izdаvаnjа: | 1-дец-2012 | Čаsоpis: | 2012 IEEE Information Theory Workshop, ITW 2012 | Sažetak: | We investigate certain optimization problems for Shannon information measures, namely, minimization of joint and conditional entropies H(X, Y), H(X|Y), H(Y|X), and maximization of mutual information I(X; Y), over convex regions. When restricted to the so-called transportation polytopes (sets of distributions with fixed marginals), very simple proofs of NP-hardness are obtained for these problems because in that case they are all equivalent, and their connection to the well-known SUBSET SUM and PARTITION problems is revealed. The computational intractability of the more general problems over arbitrary polytopes is then a simple consequence. Further, a simple class of polytopes is shown over which the above problems are not equivalent and their complexity differs sharply, namely, minimization of H(X, Y) and H(Y|X) is trivial, while minimization of H(X|Y) and maximization of I(X; Y) are strongly NP-hard problems. Finally, two new (pseudo)metrics on the space of discrete probability distributions are introduced, based on the so-called variation of information quantity, and NP-hardness of their computation is shown. © 2012 IEEE. | URI: | https://open.uns.ac.rs/handle/123456789/9364 | ISBN: | 9781467302234 | DOI: | 10.1109/ITW.2012.6404727 |
Nаlаzi sе u kоlеkciјаmа: | FTN Publikacije/Publications |
Prikаzаti cеlоkupаn zаpis stаvki
SCOPUSTM
Nаvоđеnjа
12
prоvеrеnо 20.11.2023.
Prеglеd/i stаnicа
16
Prоtеklа nеdеljа
8
8
Prоtеkli mеsеc
0
0
prоvеrеnо 10.05.2024.
Google ScholarTM
Prоvеritе
Аlt mеtrikа
Stаvkе nа DSpace-u su zаštićеnе аutоrskim prаvimа, sа svim prаvimа zаdržаnim, оsim аkо nije drugačije naznačeno.