{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:40:30Z","timestamp":1760240430276,"version":"build-2065373602"},"reference-count":35,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T00:00:00Z","timestamp":1560124800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Hongik","award":["2018 Hongik University Research Fund"],"award-info":[{"award-number":["2018 Hongik University Research Fund"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>We established a universality of logarithmic loss over a finite alphabet as a distortion criterion in fixed-length lossy compression. For any fixed-length lossy-compression problem under an arbitrary distortion criterion, we show that there is an equivalent lossy-compression problem under logarithmic loss. The equivalence is in the strong sense that we show that finding good schemes in corresponding lossy compression under logarithmic loss is essentially equivalent to finding good schemes in the original problem. This equivalence relation also provides an algebraic structure in the reconstruction alphabet, which allows us to use known techniques in the clustering literature. Furthermore, our result naturally suggests a new clustering algorithm in the categorical data-clustering problem.<\/jats:p>","DOI":"10.3390\/e21060580","type":"journal-article","created":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T11:39:47Z","timestamp":1560166787000},"page":"580","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Universality of Logarithmic Loss in Fixed-Length Lossy Compression"],"prefix":"10.3390","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6346-4182","authenticated-orcid":false,"given":"Albert","family":"No","sequence":"first","affiliation":[{"name":"Department of Electronic and Electrical Engineering, Hongik University, Seoul 04066, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,6,10]]},"reference":[{"key":"ref_1","first-page":"2040","article-title":"Multiterminal source coding with an entropy-based distortion measure","volume":"2011","author":"Courtade","year":"2011","journal-title":"Proc. IEEE Int. Symp. Inf. Theory. IEEE"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1109\/TIT.2013.2288257","article-title":"Multiterminal Source Coding Under Logarithmic Loss","volume":"60","author":"Courtade","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Ugur, Y., Aguerri, I.E., and Zaidi, A. (2018, January 25\u201329). Vector Gaussian CEO problem under logarithmic loss. Proceedings of the 2018 IEEE Information Theory Workshop, Guangzhou, China.","DOI":"10.1109\/ITW.2018.8613480"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.2017.2700860","article-title":"A single-shot approach to lossy source coding under logarithmic loss","volume":"64","author":"Shkel","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"5357","DOI":"10.1109\/TIT.2015.2462848","article-title":"Justification of logarithmic loss via the benefit of side information","volume":"61","author":"Jiao","year":"2015","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","unstructured":"Painsky, A., and Wornell, G.W. (2018). Bregman divergence bounds and the universality of the logarithmic loss. arXiv."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"No, A. (2019). Universality of Logarithmic Loss in Successive Refinement. Entropy, 21.","DOI":"10.3390\/e21020158"},{"key":"ref_8","unstructured":"Tishby, N., Pereira, F., and Bialek, W. (1999, January 22\u201324). The information bottleneck method. Proceedings of the 37th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Harremo\u00ebs, P., and Tishby, N. (2007, January 24\u201329). The information bottleneck revisited or how to choose a good distortion measure. Proceedings of the 2007 IEEE International Symposium on Information Theory, Nice, France.","DOI":"10.1109\/ISIT.2007.4557285"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Gilad-Bachrach, R., Navot, A., and Tishby, N. (2003). An information theoretic tradeoff between complexity and accuracy. Learning Theory and Kernel Machines, Springer.","DOI":"10.1007\/978-3-540-45167-9_43"},{"key":"ref_11","unstructured":"Aguerri, I.E., and Zaidi, A. (2018, January 21\u201323). Distributed Information Bottleneck Method for Discrete and Gaussian Sources. Proceedings of the International Zurich Seminar on Information and Communication, Zurich, Switzerland."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"6111","DOI":"10.1109\/TIT.2016.2562008","article-title":"Nonasymptotic noisy lossy source coding","volume":"62","author":"Kostina","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"3309","DOI":"10.1109\/TIT.2012.2186786","article-title":"Fixed-length lossy compression in the finite blocklength regime","volume":"58","author":"Kostina","year":"2012","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_14","first-page":"57","article-title":"On an extremum problem of information theory","volume":"9","year":"1974","journal-title":"Studia Scientiarum Mathematicarum Hungarica"},{"key":"ref_15","unstructured":"Cover, T.M., and Thomas, J.A. (2012). Elements of Information Theory, John Wiley & Sons. [2nd ed.]."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"No, A., and Weissman, T. (2015, January 14\u201319). Universality of logarithmic loss in lossy compression. Proceedings of the 2015 IEEE International Symposium on Information Theory, Hongkong, China.","DOI":"10.1109\/ISIT.2015.7282839"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1474","DOI":"10.1109\/TIT.2003.810633","article-title":"Information projections revisited","volume":"49","author":"Matus","year":"2003","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"No, A. (2018). Information Geometric Approach on Most Informative Boolean Function Conjecture. Entropy, 20.","DOI":"10.3390\/e20090688"},{"key":"ref_19","unstructured":"Chaffee, D.L. (1975). Applications of Rate Distortion Theory to the Bandwidth Compression of Speech Signals. [Ph.D. Thesis, University of California]."},{"key":"ref_20","unstructured":"Chen, D. (1977, January 9\u201311). On two or more dimensional optimum quantizers. Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, Hartford, CT, USA."},{"key":"ref_21","unstructured":"Gray, R., Buzo, A., Matsuyoma, Y., Gray, A., and Markel, J. (1978). Source coding and speech compression. International Telemetering Conference Proceedings, International Foundation for Telemetering."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1109\/TCOM.1980.1094577","article-title":"An algorithm for vector quantizer design","volume":"28","author":"Linde","year":"1980","journal-title":"IEEE Trans. Commun."},{"key":"ref_23","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_24","first-page":"1705","article-title":"Clustering with Bregman divergences","volume":"6","author":"Banerjee","year":"2005","journal-title":"J. Mach. Learn. Res."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","article-title":"Least squares quantization in PCM","volume":"28","author":"Lloyd","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1109\/TIT.1960.1057548","article-title":"Quantizing for minimum distortion","volume":"6","author":"Max","year":"1960","journal-title":"IRE Trans. Inf. Theory"},{"key":"ref_27","unstructured":"Kaufman, L., and Rousseeuw, P.J. (2009). Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley & Sons."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Phillips, S.J. (2002, January 4\u20135). Acceleration of k-means and related clustering algorithms. Proceedings of the Workshop on Algorithm Engineering and Experimentation, San Francisco, CA, USA.","DOI":"10.1007\/3-540-45643-0_13"},{"key":"ref_29","unstructured":"Pelleg, D., and Moore, A.W. (July, January 29). X-means: Extending k-means with efficient estimation of the number of clusters. Proceedings of the Seventeenth International Conference on Machine Learning, Stanford, CA, USA."},{"key":"ref_30","first-page":"1","article-title":"Clustering Non-Ordered Discrete Data","volume":"30","author":"Watve","year":"2014","journal-title":"J. Inf. Sci. Eng."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"2843","DOI":"10.1016\/j.patcog.2011.04.024","article-title":"A novel attribute weighting algorithm for clustering high-dimensional categorical data","volume":"44","author":"Bai","year":"2011","journal-title":"Pattern Recognit."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1003","DOI":"10.1109\/TKDE.2002.1033770","article-title":"CLARANS: A method for clustering objects for spatial data mining","volume":"14","author":"Ng","year":"2002","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Ganti, V., Gehrke, J., and Ramakrishnan, R. (1999, January 15\u201318). CACTUS\u2014clustering categorical data using summaries. Proceedings of the fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA.","DOI":"10.1145\/312129.312201"},{"key":"ref_34","first-page":"310","article-title":"CNODE: clustering of set-valued non-ordered discrete data","volume":"1","author":"Kumar","year":"2009","journal-title":"Int. J. Data Min. Model. Manag."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1109\/TIT.2013.2291007","article-title":"Optimal Lossless Data Compression: Non-Asymptotics and Asymptotics","volume":"60","author":"Kontoyiannis","year":"2014","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/6\/580\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:57:23Z","timestamp":1760187443000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/6\/580"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,10]]},"references-count":35,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2019,6]]}},"alternative-id":["e21060580"],"URL":"https:\/\/doi.org\/10.3390\/e21060580","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2019,6,10]]}}}