UNIVERSITY OF CALIFORNIA, SAN DIEGO Estimation and Compression Over Large Alphabets A dissertation submitted in partial satisfaction of the requirements for the degree Doctor of Philosophy in Electrical Engineering (Communication Theory and Systems) by Jayadev Acharya Committee in charge: Professor Alon Orlitsky, Chair Professor Sanjoy Dasgupta Professor Massimo Franceschetti Professor Alexander Vardy Professor Jacques Verstraete Professor Kenneth Zeger 2014 Copyright Jayadev Acharya, 2014 All rights reserved. The dissertation of Jayadev Acharya is approved, and it is acceptable in quality and form for publication on microfilm and electronically: Chair University of California, San Diego 2014 iii DEDICATION To my late grandfather, Mahendra Acharya iv TABLE OF CONTENTS Signature Page . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii Vita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x Abstract of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . xii Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Log-loss prediction and redundancy . . . . . . . . . . . . 2 1.2 Packing and distinguishability . . . . . . . . . . . . . . . 2 1.3 Large alphabets . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Approaches for studying large alphabets . . . . . . . . . 3 Chapter 2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Standard notation . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Universal compression, prediction and redundancy . . . . 7 2.2.1 Compression of i.i.d. sequences . . . . . . . . . . 8 2.2.2 Prediction and redundancy . . . . . . . . . . . . . 10 2.2.3 Large alphabets . . . . . . . . . . . . . . . . . . . 10 2.3 Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4 Profiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.5 Mathematical preliminaries . . . . . . . . . . . . . . . . . 12 2.5.1 Stirling’s approximation . . . . . . . . . . . . . . 12 2.5.2 Poisson distribution and tail bounds . . . . . . . . 12 2.5.3 Binary codes . . . . . . . . . . . . . . . . . . . . . 14 2.6 Poissonization . . . . . . . . . . . . . . . . . . . . . . . . 15 Chapter 3 Basic results on redundancy . . . . . . . . . . . . . . . . . . . 18 3.1 A redundancy capacity lower bound on redundancy . . . 19 3.2 Redundancy of functions . . . . . . . . . . . . . . . . . . 20 3.2.1 Redundancy of types . . . . . . . . . . . . . . . . 21 3.3 Redundancy of product distributions . . . . . . . . . . . 23 3.4 Redundancy of unions . . . . . . . . . . . . . . . . . . . 24 v Chapter 4 Efficient compression of distributions with a few modes . . . . 26 4.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.3 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3.1 Proof of Theorem 21 . . . . . . . . . . . . . . . . 31 4.3.2 Proof of Theorem 24 . . . . . . . . . . . . . . . . 35 4.3.3 m-modal distributions . . . . . . . . . . . . . . . 36 4.3.4 Lower bounds . . . . . . . . . . . . . . . . . . . . 37 4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Chapter 5 Compression of envelope classes . . . . . . . . . . . . . . . . . 40 5.1 Poisson redundancy . . . . . . . . . . . . . . . . . . . . . 42 5.2 Redundancy bounds on envelope classes . . . . . . . . . . 43 5.2.1 Redundancy of Poisson distributions . . . . . . . 44 5.2.2 General envelope class . . . . . . . . . . . . . . . 45 5.3 Applications to specific envelope classes . . . . . . . . . . 47 5.3.1 Exponential envelope . . . . . . . . . . . . . . . . 49 Chapter 6 Pattern redundancy - Tight bounds . . . . . . . . . . . . . . . 52 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.2 Pattern probability and redundancy . . . . . . . . . . . . 53 6.3 Related work and known results . . . . . . . . . . . . . . 54 6.4 Profiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 6.5 Alternate profile probability via Poissonization . . . . . . 57 6.5.1 Profile redundancy bounds . . . . . . . . . . . . . 57 6.6 Lower bound on average pattern redundancy . . . . . . . 58 6.7 Upper bound on average pattern redundancy . . . . . . . 61 6.7.1 Construction of distribution classes . . . . . . . . 63 6.7.2 Bounding redundancy of each class . . . . . . . . 64 6.7.3 Final bound . . . . . . . . . . . . . . . . . . . . . 65 6.8 Upper bound on worst-case pattern redundancy . . . . . 66 6.8.1 Overview . . . . . . . . . . . . . . . . . . . . . . . 66 6.8.2 Details . . . . . . . . . . . . . . . . . . . . . . . . 67 6.8.3 Bounding Rˆ(Ipoi(n)) . . . . . . . . . . . . . . . . . 68 Φ med Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 vi LIST OF TABLES Table 2.1: Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Table 4.1: Known bounds on R(Mn) . . . . . . . . . . . . . . . . . . . . . 30 k Table 4.2: Current bounds on R(Mn) . . . . . . . . . . . . . . . . . . . . . 38 k vii ACKNOWLEDGEMENTS I am extremely fortunate to have Alon Orlitsky as my advisor. It must have been some good deeds in a past life of mine, that I got the opportunity to meet him, know him and learn from him. He has been very supportive of me through the ups and downs of my studies. He has patiently listened to my crazy thoughts, academic and non-academic. I can never thank him enough! For example, when we wrote the first paper, he stayed up whole night working with me. Without an advisor like him, I would perhaps have never been able to write this thesis. I am thankful to my committee members Professors Sanjoy Dasgupta, Mas- simo Franceschetti, Alexander Vardy, Jacques Verstraete, and Kenneth Zeger for agreeing to be on my committee and providing valuable suggestions and feedback. I thank Professors Young-Han Kim and Ramamohan Paturi for showing interest in my work, and attending my defense talk. A good portion of this thesis is a result of the collaborations I had with my lab-mates, Hirakendu Das, Ashkan Jafarpour, Shengjun Pan, and Ananda TheerthaSuresh. Iamfortunatetohavesuchsmartpeopletobounceideasaround, and learn a lot of things in the process. I thank Narayana Santhanam, and Krish- namurthy Viswanathan for their thoughts on my research and for their advice. I thank Dr. Jaideva Goswami for being an amazing mentor, and friend throughout. I would like to thank late Ramachandra Hota, who even at 70 agreed to teach me geometry! I still do not know how he did the constructions with ruler and compass. I thank Dr. Chandra Kishore Mohapatra, and Dr. Swadhin pattanayak for their encouragement that opened many avenues for me. I thank all the friends at UCSD and from before, for all the encouragement, and fun times. This space is clearly not adequate to capture even a fraction of them. I thank my wife Snigdha for her immense support, encouragement, under- standing, and for the sacrifices, both personal and professional, that she had to make during the course of my studies. The day before my defense, I reach home at 2am, and found her waiting to warm the food, so we can have dinner together. I thank her for all this and much more. Every evening, I feel overjoyed to receive viii the widest possible smile from my daughter Saanvi when she sees me return home. It acts like an instant re-energizer. Finally, I am deeply indebted to my parents for their unconditional love and support throughout my life, for teaching me that knowledge is more important than most other things. I hope that some day I am half the engineer that my father is, and some day I can prove trigonometric identities as fast as my mother. I thank my brother Sukadeb for all the fun we have had. I hope we find time soon to do fun things, playing cricket in a 5ftx10ft balcony, and video games with bollywood songs in the background. Chapter 4 is partially adapted from Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, Ananda Theertha Suresh, “Efficient compression of monotone and m-modal distributions”, submitted to IEEE International Symposium on Informa- tion Theory (ISIT), 2014. Chapter 5 is partially adapted from Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, Ananda Theertha Suresh, “Poissonization and universal compres- sion of envelope classes”, submitted to IEEE International Symposium on Infor- mation Theory (ISIT), 2014. Chapter 6 is partially adapted from Jayadev Acharya, Hirakendu Das, Alon Orlitsky, “Tight bounds on profile redundancy and distinguishability”, Neural In- formation Processing Systems (NIPS),2012,andJayadevAcharya,HirakenduDas, Ashkan Jafarpour, Alon Orlitsky, Ananda Theertha Suresh, “Tight Bounds for Universal Compression of Large Alphabets”, IEEE International Symposium on Information Theory (ISIT), 2013. ix VITA 2007 B. Tech. in Electronics and Electrical Communication Engi- neering, Indian Institute of Technology Kharagpur 2007-2013 Graduate Student Researcher, University of California, San Diego 2009 M. S. in Electrical Engineering (Communication Theory and Systems), University of California, San Diego 2014 Ph.D.inElectricalEngineering(CommunicationTheoryand Systems), University of California, San Diego PUBLICATIONS Jayadev Acharya, Alon Orlitsky, Shengjun Pan, “The maximum likelihood prob- ability of unique-singleton, ternary, and length-7 patterns”, Proceedings of IEEE Symposium on Information Theory (ISIT), 2009. Jayadev Acharya, Hirakendu Das, Olgica Milenkovic, Alon Orlitsky, Shengjun Pan, “Recent results on pattern maximum likelihood”, IEEE Information Theory Workshop (ITW), 2009. Jayadev Acharya, Hirakendu Das, Olgica Milenkovic, Alon Orlitsky, Shengjun Pan, “String reconstruction using substring compositions”, Proceedings of IEEE Symposium on Information Theory (ISIT), 1238-1242, 2010. Jayadev Acharya, Hirakendu Das, Alon Orlitsky, Shengjun Pan, Narayana Prasad Santhanam, “Classification using pattern maximum likelihood”, Proceedings of IEEE Symposium on Information Theory (ISIT), 1493-1497, 2010. JayadevAcharya,HirakenduDas,AlonOrlitsky,ShengjunPan,“Exactcalculation of pattern probabilities”, Proceedings of IEEE Symposium on Information Theory (ISIT), 1498-1502, 2010. JayadevAcharya,HirakenduDas,AshkanJafarpour,AlonOrlitsky,ShengjunPan, “Competitive closeness testing”, Conference on Learning Theory (COLT), 47-68, 2011. Jayadev Acharya, Hirakendu Das, Alon Orlitsky, Shengjun Pan, “Algebraic com- putation of pattern maximum likelihood”, Proceedings of IEEE Symposium on Information Theory (ISIT), 400-404, 2011. x