Tsachy Weissman

Tsachy Weissman


Research Focus & Metrics

Academic Career Length

22Years (2005-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
13 March 2015 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
JJJiantao Jiao
Jiantao Jiao
KVKartik Venkat
Kartik Venkat
YHYanjun Han
Yanjun Han
TWTsachy Weissman
Tsachy Weissman
We propose a general methodology for the construction and analysis of essentially minimax estimators for a wide class of functionals of finite dimensional parameters, and elaborate on the case of discrete distributions, where the support size S is unknown and may be comparable with or even much larger than the number of observations n. We treat the respective regions where the functional is nonsmooth and smooth separately. In the nonsmooth regime, we apply an unbiased estimator for the best polynomial approximation of the functional whereas, in the smooth regime, we apply a bias-corrected version of the maximum likelihood estimator (MLE). We illustrate the merit of this approach by thoroughly analyzing the performance of the resulting schemes for estimating two important information measures: 1) the entropy H(P) = Σ S i=1 -p i ln p i and 2) F α (P) = Σ S i=1 p α i , α > 0. We obtain the minimax L 2 rates for estimating these functionals. In particular, we demonstrate that our estimator achieves the optimal sample complexity n × S/ln S for entropy estimation. We also demonstrate that the sample complexity for estimating F α (P), 0 <; α <; 1, is n×S 1/α /ln S, which can be achieved by our estimator but not the MLE. For 1 <; α <; 3/2, we show the minimax L 2 rate for estimating F α (P) is (n ln n) -2(α-1) for infinite support size, while the maximum L 2 rate for the MLE is n -2(α-1) . For all the above cases, the behavior of the minimax rate-optimal estimators with n samples is essentially that of the MLE (plug-in rule) with n ln n samples, which we term “effective sample size enlargement.” We highlight the practical advantages of our schemes for the estimation of entropy and mutual information. We compare our performance with various existing approaches, and demonstrate that our approach reduces running time and boosts the accuracy. Moreover, we show that the minimax rate-optimal mutual information estimator yielded by our framework leads to significant performance boosts over the Chow-Liu algorithm in learning graphical models. The wide use of information measure estimation suggests that the insights and estimators obtained in this paper could be broadly applicable.

20 June 2011 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
HPHaim Permuter
Haim Permuter
TWTsachy Weissman
Tsachy Weissman
We study source coding in the presence of side information, when the system can take actions that affect the availability, quality, or nature of the side information. We begin by extending the Wyner-Ziv problem of source coding with decoder side information to the case where the decoder is allowed to choose actions affecting the side information. We then consider the setting where actions are taken by the encoder, based on its observation of the source. Actions may have costs that are commensurate with the quality of the side information they yield, and an overall per-symbol cost constraint may be imposed. We characterize the achievable tradeoffs between rate, distortion, and cost in some of these problem settings. Among our findings is the fact that even in the absence of a cost constraint, greedily choosing the action associated with the “best” side information is, in general, suboptimal. A few examples are worked out.

1 January 2025 in Operations Research
Verified
Journal Article
Closed access
YHYanjun Han
Yanjun Han
TWTsachy Weissman
Tsachy Weissman
ZZZhengyuan Zhou
Zhengyuan Zhou
In “Optimal No-Regret Learning in Repeated First-Price Auctions,” Y. Han, W. Tsachy, and Z. Zhou study online learning in repeated first-price auctions where a bidder, only observing the winning bid at the end of each auction, learns to adaptively bid to maximize her cumulative payoff. To achieve this goal, the bidder faces censored feedback: If she wins the bid, then she is not able to observe the highest bid of the other bidders, which we assume is i.i.d. drawn from an unknown distribution. In this paper, they develop the first learning algorithm that achieves a near-optimal regret bound, by exploiting two structural properties of first-price auctions, that is, the specific feedback structure and payoff function.

25 July 2014 in IEEE Transactions on Information Theory
Verified
Journal Article
Open access
HPHaim Permuter
Haim Permuter
HAHimanshu Asnani
Himanshu Asnani
TWTsachy Weissman
Tsachy Weissman
We consider finite state channels, where the state of the channel is its previous output. We refer to these as Previous Output is the STate (POST) channels. We first focus on POST(α) channels. These channels have binary inputs and outputs, where the state determines if the channel behaves as a Z or an S channel, both with parameter α. We show that the nonfeedback capacity of the POST(α) channel equals its feedback capacity, despite the memory of the channel. The proof of this surprising result is based on showing that the induced output distribution, when maximizing the directed information in the presence of feedback, can also be achieved by an input distribution that does not utilize the feedback. We show that this is a sufficient condition for the feedback capacity to equal the nonfeedback capacity for any finite state channel. We show that the result carries over from the POST(α) channel to a binary POST channel, where the previous output determines whether the current channel will be binary with parameters (a, b) or (b, a). Finally, we show that, in general, feedback may increase the capacity of a POST channel.

1 June 2007
Verified
Conference Paper
Closed access
YKYoung-Han Kim
Young-Han Kim
Amos LapidothAmos Lapidoth
Amos Lapidoth
TWTsachy Weissman
Tsachy Weissman
Upper and lower bounds are derived on the reliability function of the additive white Gaussian noise channel with output fed back to the transmitter over an independent additive white Gaussian noise channel. Special attention is paid to the regime of very low feedback noise variance and it is shown that the reliability function is asymptotically inversely proportional to the feedback noise variance. This result shows that the noise in the feedback link, however small, renders the communication with noisy feedback fundamentally different from the perfect feedback case. For example, it is demonstrated that with noisy feedback, linear coding schemes fail to achieve any positive rate. In contrast, an asymptotically optimal coding scheme is devised, based on a three-phase detection/retransmission protocol, which achieves an error exponent inversely proportional to the feedback noise variance for any rate less than capacity.

8 June 2013 in BMC Bioinformatics
Verified
Journal Article
Open access
PDF file
IOIdoia Ochoa
Idoia Ochoa
HAHimanshu Asnani
Himanshu Asnani
DBDinesh Bharadia
Dinesh Bharadia
MCMainak Chowdhury
Mainak Chowdhury
TWTsachy Weissman
Tsachy Weissman
GYGolan Yona
Golan Yona
Next Generation Sequencing technologies have revolutionized many fields in biology by reducing the time and cost required for sequencing. As a result, large amounts of sequencing data are being generated. A typical sequencing data file may occupy tens or even hundreds of gigabytes of disk space, prohibitively large for many users. This data consists of both the nucleotide sequences and per-base quality scores that indicate the level of confidence in the readout of these sequences. Quality scores account for about half of the required disk space in the commonly used FASTQ format (before compression), and therefore the compression of the quality scores can significantly reduce storage requirements and speed up analysis and transmission of sequencing data. In this paper, we present a new scheme for the lossy compression of the quality scores, to address the problem of storage. Our framework allows the user to specify the rate (bits per quality score) prior to compression, independent of the data to be compressed. Our algorithm can work at any rate, unlike other lossy compression algorithms. We envisage our algorithm as being part of a more general compression scheme that works with the entire FASTQ file. Numerical experiments show that we can achieve a better mean squared error (MSE) for small rates (bits per quality score) than other lossy compression schemes. For the organism PhiX, whose assembled genome is known and assumed to be correct, we show that it is possible to achieve a significant reduction in size with little compromise in performance on downstream applications (e.g., alignment). QualComp is an open source software package, written in C and freely available for download at https://sourceforge.net/projects/qualcomp .