{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,3]],"date-time":"2026-09-03T15:48:25Z","timestamp":1788450505040,"version":"build-2803163510"},"reference-count":21,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2015,5,18]],"date-time":"2015-05-18T00:00:00Z","timestamp":1431907200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Center of Science (Poland)","award":["2014\/13\/N\/ST6\/01832"],"award-info":[{"award-number":["2014\/13\/N\/ST6\/01832"]}]},{"name":"National Center of Science (Poland)","award":["2014\/13\/B\/ST6\/01792"],"award-info":[{"award-number":["2014\/13\/B\/ST6\/01792"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In this paper, we investigate a lossy source coding problem, where an upper limit on the permitted distortion is defined for every dataset element. It can be seen as an alternative approach to rate distortion theory where a bound on the allowed average error is specified. In order to find the entropy, which gives a statistical length of source code compatible with a fixed distortion bound, a corresponding optimization problem has to be solved. First, we show how to simplify this general optimization by reducing the number of coding partitions, which are irrelevant for the entropy calculation. In our main result, we present a fast and feasible for implementation greedy algorithm, which allows one to approximate the entropy within an additive error term of log2 e. The proof is based on the minimum entropy set cover problem, for which a similar bound was obtained.<\/jats:p>","DOI":"10.3390\/e17053400","type":"journal-article","created":{"date-parts":[[2015,5,18]],"date-time":"2015-05-18T10:56:37Z","timestamp":1431946597000},"page":"3400-3418","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Entropy Approximation in Lossy Source Coding Problem"],"prefix":"10.3390","volume":"17","author":[{"given":"Marek","family":"\u015amieja","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, Jagiellonian University, Lojasiewicza 6, 30-348 Krak\u00f3w, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jacek","family":"Tabor","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Jagiellonian University, Lojasiewicza 6, 30-348 Krak\u00f3w, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2015,5,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"2693","DOI":"10.1109\/18.720552","article-title":"Lossy source coding","volume":"44","author":"Berger","year":"1998","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"2325","DOI":"10.1109\/18.720541","article-title":"Quantization","volume":"44","author":"Gray","year":"1998","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A mathematical theory of communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell Syst. Tech. J."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1117\/1.482609","article-title":"High quality document image compression with \u201cDjVu\u201d","volume":"7","author":"Bottou","year":"1998","journal-title":"J. Electron. Imaging"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1473","DOI":"10.1109\/18.259634","article-title":"A survey of the theory of source coding with a fidelity criterion","volume":"39","author":"Kieffer","year":"1993","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"\u015amieja, M. (2014). Weighted approach to general entropy function. IMA J. Math. Control Inf., 32.","DOI":"10.1093\/imamci\/dnt044"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2719","DOI":"10.1109\/TIT.2011.2181820","article-title":"Entropy of the mixture of sources and entropy dimension","volume":"58","author":"Tabor","year":"2012","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_8","unstructured":"\u015amieja, M., and Tabor, J. (2014, January 27\u201329). R\u00e9nyi entropy dimension of the mixture of measures. London, UK."},{"key":"ref_9","unstructured":"Berger, T. (1971). Rate-Distortion Theory, Wiley."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1109\/79.733495","article-title":"Rate-distortion methods for image and video compression","volume":"15","author":"Ortega","year":"1998","journal-title":"IEEE Signal Process. Mag."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1109\/MASSP.1984.1162229","article-title":"Vector quantization","volume":"1","author":"Gray","year":"1984","journal-title":"IEEE ASSP Mag."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1109\/26.3776","article-title":"Image coding using vector quantization: A review","volume":"36","author":"Nasrabadi","year":"1998","journal-title":"IEEE Trans. Commun."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2079","DOI":"10.1214\/aoms\/1177693077","article-title":"Epsilon entropy and data compression","volume":"42","author":"Posner","year":"1971","journal-title":"Ann. Math. Stat."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1000","DOI":"10.1214\/aoms\/1177698768","article-title":"Epsilon entropy of stochastic processes","volume":"38","author":"Posner","year":"1967","journal-title":"Ann. Math. Stat."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF02063299","article-title":"On the dimension and entropy of probability distributions","volume":"10","year":"1959","journal-title":"Acta Math. Hungar."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1385","DOI":"10.1109\/5.241504","article-title":"Signal compression based on models of human perception","volume":"81","author":"Jayant","year":"1993","journal-title":"Proc. IEEE"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/s00453-007-9076-8","article-title":"Tight results on minimum entropy set cover","volume":"51","author":"Cardinal","year":"2008","journal-title":"Algorithmica"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1016\/j.tcs.2005.09.015","article-title":"The minimum-entropy set cover problem","volume":"348","author":"Halperin","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"ref_19","unstructured":"Kingman, J.F.C., and Taylor, S.J. (1966). Introduction to measures and probability, Cambridge University Press."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"3235","DOI":"10.1016\/j.physleta.2009.07.015","article-title":"Source coding with escort distributions and R\u00e9nyi entropy bounds","volume":"373","author":"Bercher","year":"2009","journal-title":"Phys. Lett. A"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"5591","DOI":"10.1016\/j.eswa.2015.03.007","article-title":"Multithreshold entropy linear classifier: Theory and applications","volume":"42","author":"Czarnecki","year":"2015","journal-title":"Expert Syst. Appl."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/17\/5\/3400\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T20:46:27Z","timestamp":1760215587000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/17\/5\/3400"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,18]]},"references-count":21,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2015,5]]}},"alternative-id":["e17053400"],"URL":"https:\/\/doi.org\/10.3390\/e17053400","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,18]]}}}