120 citations · 1.1k across the 101 of their papers we have counts for
75 papers · 1 filter
Toward Textual Transform Coding
Tsachy Weissman
Inspired by recent work on compression with and for young humans, the success of transform-based approaches to information processing, and the rise of powerful language-based AI, w…
Upper bounds on the Rate of Uniformly-Random Codes for the Deletion Channel
Berivan Isik, Francisco Pernice, Tsachy Weissman
We consider the maximum coding rate achievable by uniformly-random codes for the deletion channel. We prove an upper bound that's within 0.1 of the best known lower bounds for all…
Lossy Compression of Noisy Data for Private and Data-Efficient Learning
Berivan Isik, Tsachy Weissman
Storage-efficient privacy-preserving learning is crucial due to increasing amounts of sensitive user data required for modern learning tasks. We propose a framework for reducing th…
Optimal Communication Rates and Combinatorial Properties for Common Randomness Generation
Yanjun Han, Kedar Tatwawadi, Gowtham R. Kurri +3
We study common randomness generation problems where players aim to generate same sequences of random coin flips where some subsets of the players share an independent common c…
Concentration Inequalities for the Empirical Distribution
Jay Mardia, Jiantao Jiao, Ervin Tánczos +2
We study concentration inequalities for the Kullback--Leibler (KL) divergence between the empirical distribution and the true distribution. Applying a recursion technique, we impro…
Minimax redundancy for Markov chains with large state space
Kedar Shriram Tatwawadi, Jiantao Jiao, Tsachy Weissman
For any Markov source, there exist universal codes whose normalized codelength approaches the Shannon limit asymptotically as the number of samples goes to infinity. This paper inv…
Universality of Logarithmic Loss in Lossy Compression
Albert No, Tsachy Weissman
We establish two strong senses of universality of logarithmic loss as a distortion criterion in lossy compression: For any fixed length lossy compression problem under an arbitrary…
Estimating the Fundamental Limits is Easier than Achieving the Fundamental Limits
Jiantao Jiao, Yanjun Han, Irena Fischer-Hwang +1
We show through case studies that it is easier to estimate the fundamental limits of data processing than to construct explicit algorithms to achieve those limits. Focusing on bina…
Mutual Information, Relative Entropy and Estimation Error in Semi-martingale Channels
Jiantao Jiao, Kartik Venkat, Tsachy Weissman
Fundamental relations between information and estimation have been established in the literature for the continuous-time Gaussian and Poisson channels, in a long line of work start…
Dependence Measures Bounding the Exploration Bias for General Measurements
Jiantao Jiao, Yanjun Han, Tsachy Weissman
We propose a framework to analyze and quantify the bias in adaptive data analysis. It generalizes that proposed by Russo and Zou'15, applying to measurements whose moment generatin…
When is Noisy State Information at the Encoder as Useless as No Information or as Good as Noise-Free State?
Rui Xu, Jun Chen, Tsachy Weissman +1
For any binary-input channel with perfect state information at the decoder, if the mutual information between the noisy state observation at the encoder and the true channel state…
Strong Successive Refinability and Rate-Distortion-Complexity Tradeoff
Albert No, Amir Ingber, Tsachy Weissman
We investigate the second order asymptotics (source dispersion) of the successive refinement problem. Similarly to the classical definition of a successively refinable source, we s…
Does Dirichlet Prior Smoothing Solve the Shannon Entropy Estimation Problem?
Yanjun Han, Jiantao Jiao, Tsachy Weissman
The Dirichlet prior is widely used in estimating discrete distributions and functionals of discrete distributions. In terms of Shannon entropy estimation, one approach is to plug-i…
Adaptive Estimation of Shannon Entropy
Yanjun Han, Jiantao Jiao, Tsachy Weissman
We consider estimating the Shannon entropy of a discrete distribution from i.i.d. samples. Recently, Jiao, Venkat, Han, and Weissman, and Wu and Yang constructed approximat…
Minimax Estimation of Discrete Distributions under Loss
Yanjun Han, Jiantao Jiao, Tsachy Weissman
We analyze the problem of discrete distribution estimation under loss. We provide non-asymptotic upper and lower bounds on the maximum risk of the empirical distribution (…
Maximum Likelihood Estimation of Functionals of Discrete Distributions
Jiantao Jiao, Kartik Venkat, Yanjun Han +1
We consider the problem of estimating functionals of discrete distributions, and focus on tight nonasymptotic analysis of the worst case squared error risk of widely used estimator…
Minimax Estimation of Functionals of Discrete Distributions
Jiantao Jiao, Kartik Venkat, Yanjun Han +1
We propose a general methodology for the construction and analysis of minimax estimators for a wide class of functionals of finite dimensional parameters, and elaborate on the case…
Rateless Lossy Compression via the Extremes
Albert No, Tsachy Weissman
We begin by presenting a simple lossy compressor operating at near-zero rate: The encoder merely describes the indices of the few maximal source components, while the decoder's rec…
Compression for Quadratic Similarity Queries: Finite Blocklength and Practical Schemes
Fabian Steiner, Steffen Dempfle, Amir Ingber +1
We study the problem of compression for the purpose of similarity identification, where similarity is measured by the mean square Euclidean distance between vectors. While the asym…
Distortion-Rate Function of Sub-Nyquist Sampled Gaussian Sources
Alon Kipnis, Andrea J. Goldsmith, Yonina C. Eldar +1
The amount of information lost in sub-Nyquist sampling of a continuous-time Gaussian stationary process is quantified. We consider a combined source coding and sub-Nyquist reconstr…
Relations between Information and Estimation in Discrete-Time Lévy Channels
Jiantao Jiao, Kartik Venkat, Tsachy Weissman
Fundamental relations between information and estimation have been established in the literature for the discrete-time Gaussian and Poisson channels. In this work, we demonstrate t…
Information Measures: the Curious Case of the Binary Alphabet
Jiantao Jiao, Thomas Courtade, Albert No +2
Four problems related to information divergence measures defined on finite alphabets are considered. In three of the cases we consider, we illustrate a contrast which arises betwee…
Justification of Logarithmic Loss via the Benefit of Side Information
Jiantao Jiao, Thomas Courtade, Kartik Venkat +1
We consider a natural measure of relevance: the reduction in optimal prediction risk in the presence of side information. For any given loss function, this relevance measure captur…
The Minimal Compression Rate for Similarity Identification
Amir Ingber, Tsachy Weissman
Traditionally, data compression deals with the problem of concisely representing a data source, e.g. a sequence of letters, for the purpose of eventual reproduction (either exact o…