BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Haim Permuter

Haim Permuter appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITMachine Learning

Catalog footprint

What is connected

22works
3topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

22 published item(s)

preprint2023arXiv

Data-Driven Optimization of Directed Information over Discrete Alphabets

Directed information (DI) is a fundamental measure for the study and analysis of sequential stochastic models. In particular, when optimized over input distributions it characterizes the capacity of general communication channels. However, analytic computation of DI is typically intractable and existing optimization techniques over discrete input alphabets require knowledge of the channel model, which renders them inapplicable when only samples are available. To overcome these limitations, we propose a novel estimation-optimization framework for DI over discrete input spaces. We formulate DI optimization as a Markov decision process and leverage reinforcement learning techniques to optimize a deep generative model of the input process probability mass function (PMF). Combining this optimizer with the recently developed DI neural estimator, we obtain an end-to-end estimation-optimization algorithm which is applied to estimating the (feedforward and feedback) capacity of various discrete channels with memory. Furthermore, we demonstrate how to use the optimized PMF model to (i) obtain theoretical bounds on the feedback capacity of unifilar finite-state channels; and (ii) perform probabilistic shaping of constellations in the peak power-constrained additive white Gaussian noise channel.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Neural Estimation and Optimization of Directed Information over Continuous Spaces

This work develops a new method for estimating and optimizing the directed information rate between two jointly stationary and ergodic stochastic processes. Building upon recent advances in machine learning, we propose a recurrent neural network (RNN)-based estimator which is optimized via gradient ascent over the RNN parameters. The estimator does not require prior knowledge of the underlying joint and marginal distributions. The estimator is also readily optimized over continuous input processes realized by a deep generative model. We prove consistency of the proposed estimation and optimization methods and combine them to obtain end-to-end performance guarantees. Applications for channel capacity estimation of continuous channels with memory are explored, and empirical results demonstrating the scalability and accuracy of our method are provided. When the channel is memoryless, we investigate the mapping learned by the optimized input generator.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Feedback Capacity of Noisy Output is the STate (NOST) Channels

We consider finite-state channels (FSCs) where the channel state is stochastically dependent on the previous channel output. We refer to these as Noisy Output is the STate (NOST) channels. We derive the feedback capacity of NOST channels in two scenarios: with and without causal state information (CSI) available at the encoder. If CSI is unavailable, the feedback capacity is $C_{\text{FB}}= \max_{P(x|y')} I(X;Y|Y')$, while if it is available at the encoder, the feedback capacity is $C_{\text{FB-CSI}}= \max_{P(u|y'),x(u,s')} I(U;Y|Y')$, where $U$ is an auxiliary RV with finite cardinality. In both formulas, the output process is a Markov process with stationary distribution. The derived formulas generalize special known instances from the literature, such as where the state is i.i.d. and where it is a deterministic function of the output. $C_{\text{FB}}$ and $C_{\text{FB-CSI}}$ are also shown to be computable via convex optimization problem formulations. Finally, we present an example of an interesting NOST channel for which CSI available at the encoder does not increase the feedback capacity.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Amended Cross Entropy Cost: Framework For Explicit Diversity Encouragement

Cross Entropy (CE) has an important role in machine learning and, in particular, in neural networks. It is commonly used in neural networks as the cost between the known distribution of the label and the Softmax/Sigmoid output. In this paper we present a new cost function called the Amended Cross Entropy (ACE). Its novelty lies in its affording the capability to train multiple classifiers while explicitly controlling the diversity between them. We derived the new cost by mathematical analysis and "reverse engineering" of the way we wish the gradients to behave, and produced a tailor-made, elegant and intuitive cost function to achieve the desired result. This process is similar to the way that CE cost is picked as a cost function for the Softmax/Sigmoid classifiers for obtaining linear derivatives. By choosing the optimal diversity factor we produce an ensemble which yields better results than the vanilla one. We demonstrate two potential usages of this outcome, and present empirical results. Our method works for classification problems analogously to Negative Correlation Learning (NCL) for regression problems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Can Feedback Increase the Capacity of the Energy Harvesting Channel?

We investigate if feedback can increase the capacity of an energy harvesting communication channel where a transmitter powered by an exogenous energy arrival process and equipped with a finite battery communicates to a receiver over a memoryless channel. For a simple special case where the energy arrival process is deterministic and the channel is a BEC, we explicitly compute the feed-forward and feedback capacities and show that feedback can strictly increase the capacity of this channel. Building on this example, we also show that feedback can increase the capacity when the energy arrivals are i.i.d. known noncausally at the transmitter and the receiver.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Cooperative Binning for Semideterministic Channels

The capacity regions of semideterministic multiuser channels, such as the semideterministic relay channel and the multiple access channel with partially cribbing encoders, have been characterized using the idea of partial-decode-forward. However, the requirement to explicitly decode part of the message at intermediate nodes can be restrictive in some settings; for example, when nodes have different side information regarding the state of the channel. In this paper, we generalize this scheme to $\textit{cooperative-bin-forward}$ by building on the observation that explicit recovering of part of the message is not needed to induce cooperation. Instead, encoders can bin their received signals and cooperatively forward the bin index to the decoder. The main advantage of this new scheme is illustrated by considering state-dependent extensions of the aforementioned semideterministic setups. While partial-decode-forward is not applicable in these new setups, cooperative-bin-forward continues to achieve capacity.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Multicoding Schemes for Interference Channels

The best known inner bound for the 2-user discrete memoryless interference channel is the Han-Kobayashi rate region. The coding schemes that achieve this region are based on rate-splitting and superposition coding. In this paper, we develop a multicoding scheme to achieve the same rate region. A key advantage of the multicoding nature of the proposed coding scheme is that it can be naturally extended to more general settings, such as when encoders have state information or can overhear each other. In particular, we extend our coding scheme to characterize the capacity region of the state-dependent deterministic Z-interference channel when noncausal state information is available at the interfering transmitter. We specialize our results to the case of the linear deterministic model with on/off interference which models a wireless system where a cognitive transmitter is noncausally aware of the times it interferes with a primary transmission. For this special case, we provide an explicit expression for the capacity region and discuss some interesting properties of the optimal strategy. We also extend our multicoding scheme to find the capacity region of the deterministic Z-interference channel when the signal of the interfering transmitter can be overheard at the other transmitter (a.k.a. unidirectional partial cribbing).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Multiple Access Channels with Combined Cooperation and Partial Cribbing

In this paper we study the multiple access channel (MAC) with combined cooperation and partial cribbing and characterize its capacity region. Cooperation means that the two encoders send a message to one another via a rate-limited link prior to transmission, while partial cribbing means that each of the two encoders obtains a deterministic function of the other encoder's output with or without delay. Prior work in this field dealt separately with cooperation and partial cribbing. However, by combining these two methods we can achieve significantly higher rates. Remarkably, the capacity region does not require an additional auxiliary random variable (RV) since the purpose of both cooperation and partial cribbing is to generate a common message between the encoders. In the proof we combine methods of block Markov coding, backward decoding, double rate-splitting, and joint typicality decoding. Furthermore, we present the Gaussian MAC with combined one-sided cooperation and quantized cribbing. For this model, we give an achievability scheme that shows how many cooperation or quantization bits are required in order to achieve a Gaussian MAC with full cooperation/cribbing capacity region. After establishing our main results, we consider two cases where only one auxiliary RV is needed. The first is a rate distortion dual setting for the MAC with a common message, a private message and combined cooperation and cribbing. The second is a state-dependent MAC with cooperation, where the state is known at a partially cribbing encoder and at the decoder. However, there are cases where more than one auxiliary RV is needed, e.g., when the cooperation and cribbing are not used for the same purposes. We present a MAC with an action-dependent state, where the action is based on the cooperation but not on the cribbing. Therefore, in this case more than one auxiliary RV is needed.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Channel Coding and Source Coding with Increased Partial Side Information

Let (S1,i, S2,i), distributed according to i.i.d p(s1, s2), i = 1, 2, . . . be a memoryless, correlated partial side information sequence. In this work we study channel coding and source coding problems where the partial side information (S1, S2) is available at the encoder and the decoder, respectively, and, additionally, either the encoder's or the decoder's side information is increased by a limited-rate description of the other's partial side information. We derive six special cases of channel coding and source coding problems and we characterize the capacity and the rate-distortion functions for the different cases. We present a duality between the channel capacity and the rate-distortion cases we study. In order to find numerical solutions for our channel capacity and rate-distortion problems, we use the Blahut-Arimoto algorithm and convex optimization tools. As a byproduct of our work, we found a tight lower bound on the Wyner-Ziv solution by formulating its Lagrange dual as a geometric program. Previous results in the literature provide a geometric programming formulation that is only a lower bound, but not necessarily tight. Finally, we provide several examples corresponding to the channel capacity and the rate-distortion cases we presented.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Capacity and coding for the Ising Channel with Feedback

The Ising channel, which was introduced in 1990, is a channel with memory that models Inter-Symbol interference. In this paper we consider the Ising channel with feedback and find the capacity of the channel together with a capacity-achieving coding scheme. To calculate the channel capacity, an equivalent dynamic programming (DP) problem is formulated and solved. Using the DP solution, we establish that the feedback capacity is the expression $C=(\frac{2H_b(a)}{3+a})\approx 0.575522$ where $a$ is a particular root of a fourth-degree polynomial and $H_b(x)$ denotes the binary entropy function. Simultaneously, $a=\arg \max_{0\leq x \leq 1} (\frac{2H_b(x)}{3+x})$. Finally, a simple, error-free, capacity-achieving coding scheme is provided together with outlining a strong connection between the DP results and the coding scheme.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Successive Refinement with Decoder Cooperation and its Channel Coding Duals

We study cooperation in multi terminal source coding models involving successive refinement. Specifically, we study the case of a single encoder and two decoders, where the encoder provides a common description to both the decoders and a private description to only one of the decoders. The decoders cooperate via cribbing, i.e., the decoder with access only to the common description is allowed to observe, in addition, a deterministic function of the reconstruction symbols produced by the other. We characterize the fundamental performance limits in the respective settings of non-causal, strictly-causal and causal cribbing. We use a new coding scheme, referred to as Forward Encoding and Block Markov Decoding, which is a variant of one recently used by Cuff and Zhao for coordination via implicit communication. Finally, we use the insight gained to introduce and solve some dual channel coding scenarios involving Multiple Access Channels with cribbing.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

To Feed or Not to Feed Back

We study the communication over Finite State Channels (FSCs), where the encoder and the decoder can control the availability or the quality of the noise-free feedback. Specifically, the instantaneous feedback is a function of an action taken by the encoder, an action taken by the decoder, and the channel output. Encoder and decoder actions take values in finite alphabets, and may be subject to average cost constraints. We prove capacity results for such a setting by constructing a sequence of achievable rates, using a simple scheme based on 'code tree' generation, that generates channel input symbols along with encoder and decoder actions. We prove that the limit of this sequence exists. For a given block length and probability of error, we give an upper bound on the maximum achievable rate. Our upper and lower bounds coincide and hence yield the capacity for the case where the probability of initial state is positive for all states. Further, for stationary indecomposable channels without intersymbol interference (ISI), the capacity is given as the limit of normalized directed information between the input and output sequence, maximized over an appropriate set of causally conditioned distributions. As an important special case, we consider the framework of 'to feed or not to feed back' where either the encoder or the decoder takes binary actions, which determine whether current channel output will be fed back to the encoder, with a constraint on the fraction of channel outputs that are fed back. As another special case of our framework, we characterize the capacity of 'coding on the backward link' in FSCs, i.e. when the decoder sends limited-rate instantaneous coded noise-free feedback on the backward link. Finally, we propose an extension of the Blahut-Arimoto algorithm for evaluating the capacity when actions can be cost constrained, and demonstrate its application on a few examples.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Capacity Region of Finite State Multiple-Access Channel with Delayed State Information at the Transmitters

A single-letter characterization is provided for the capacity region of finite-state multiple access channels. The channel state is a Markov process, the transmitters have access to delayed state information, and channel state information is available at the receiver. The delays of the channel state information are assumed to be asymmetric at the transmitters. We apply the result to obtain the capacity region for a finite-state Gaussian MAC, and for a finite-state multiple-access fading channel. We derive power control strategies that maximize the capacity region for these channels.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Computable Bounds for Rate Distortion with Feed-Forward for Stationary and Ergodic Sources

In this paper we consider the rate distortion problem of discrete-time, ergodic, and stationary sources with feed forward at the receiver. We derive a sequence of achievable and computable rates that converge to the feed-forward rate distortion. We show that, for ergodic and stationary sources, the rate {align} R_n(D)=\frac{1}{n}\min I(\hat{X}^n\rightarrow X^n){align} is achievable for any $n$, where the minimization is taken over the transition conditioning probability $p(\hat{x}^n|x^n)$ such that $\ex{}{d(X^n,\hat{X}^n)}\leq D$. The limit of $R_n(D)$ exists and is the feed-forward rate distortion. We follow Gallager's proof where there is no feed-forward and, with appropriate modification, obtain our result. We provide an algorithm for calculating $R_n(D)$ using the alternating minimization procedure, and present several numerical examples. We also present a dual form for the optimization of $R_n(D)$, and transform it into a geometric programming problem.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Multiple Access Channel with Partial and Controlled Cribbing Encoders

In this paper we consider a multiple access channel (MAC) with partial cribbing encoders. This means that each of two encoders obtains a deterministic function of the other encoder output with or without delay. The partial cribbing scheme is especially motivated by the additive noise Gaussian MAC since perfect cribbing results in the degenerated case of full cooperation between the encoders and requires an infinite entropy link. We derive a single letter characterization of the capacity of the MAC with partial cribbing for the cases of causal and strictly causal partial cribbing. Several numerical examples, such as quantized cribbing, are presented. We further consider and derive the capacity region where the cribbing depends on actions that are functions of the previous cribbed observations. In particular, we consider a scenario where the action is "to crib or not to crib" and show that a naive time-sharing strategy is not optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Cascade and Triangular Source Coding with Side Information at the First Two Nodes

We consider the cascade and triangular rate-distortion problem where side information is known to the source encoder and to the first user but not to the second user. We characterize the rate-distortion region for these problems. For the quadratic Gaussian case, we show that it is sufficient to consider jointly Gaussian distributions, a fact that leads to an explicit solution.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Cascade, Triangular and Two Way Source Coding with degraded side information at the second user

We consider the Cascade and Triangular rate-distortion problems where the same side information is available at the source node and User 1, and the side information available at User 2 is a degraded version of the side information at the source node and User 1. We characterize the rate-distortion region for these problems. For the Cascade setup, we showed that, at User 1, decoding and re-binning the codeword sent by the source node for User 2 is optimum. We then extend our results to the Two way Cascade and Triangular setting, where the source node is interested in lossy reconstruction of the side information at User 2 via a rate limited link from User 2 to the source node. We characterize the rate distortion regions for these settings. Complete explicit characterizations for all settings are also given in the Quadratic Gaussian case. We conclude with two further extensions: A triangular source coding problem with a helper, and an extension of our Two Way Cascade setting in the Quadratic Gaussian case.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Coordination Capacity

We develop elements of a theory of cooperation and coordination in networks. Rather than considering a communication network as a means of distributing information, or of reconstructing random processes at remote nodes, we ask what dependence can be established among the nodes given the communication constraints. Specifically, in a network with communication rates {R_{i,j}} between the nodes, we ask what is the set of all achievable joint distributions p(x1, ..., xm) of actions at the nodes of the network. Several networks are solved, including arbitrarily large cascade networks. Distributed cooperation can be the solution to many problems such as distributed games, distributed control, and establishing mutual information bounds on the influence of one part of a physical system on another.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Extension of the Blahut-Arimoto algorithm for maximizing directed information

We extend the Blahut-Arimoto algorithm for maximizing Massey's directed information. The algorithm can be used for estimating the capacity of channels with delayed feedback, where the feedback is a deterministic function of the output. In order to do so, we apply the ideas from the regular Blahut-Arimoto algorithm, i.e., the alternating maximization procedure, onto our new problem. We provide both upper and lower bound sequences that converge to the optimum value. Our main insight in this paper is that in order to find the maximum of the directed information over causal conditioning probability mass function (PMF), one can use a backward index time maximization combined with the alternating maximization procedure. We give a detailed description of the algorithm, its complexity, the memory needed, and several numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Message and state cooperation in multiple access channels

We investigate the capacity of a multiple access channel with cooperating encoders where partial state information is known to each encoder and full state information is known to the decoder. The cooperation between the encoders has a two-fold purpose: to generate empirical state coordination between the encoders, and to share information about the private messages that each encoder has. For two-way cooperation, this two-fold purpose is achieved by double-binning, where the first layer of binning is used to generate the state coordination similarly to the two-way source coding, and the second layer of binning is used to transmit information about the private messages. The complete result provides the framework and perspective for addressing a complex level of cooperation that mixes states and messages in an optimal way.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Probing Capacity

We consider the problem of optimal probing of states of a channel by transmitter and receiver for maximizing rate of reliable communication. The channel is discrete memoryless (DMC) with i.i.d. states. The encoder takes probing actions dependent on the message. It then uses the state information obtained from probing causally or non-causally to generate channel input symbols. The decoder may also take channel probing actions as a function of the observed channel output and use the channel state information thus acquired, along with the channel output, to estimate the message. We refer to the maximum achievable rate for reliable communication for such systems as the 'Probing Capacity'. We characterize this capacity when the encoder and decoder actions are cost constrained. To motivate the problem, we begin by characterizing the trade-off between the capacity and fraction of channel states the encoder is allowed to observe, while the decoder is aware of channel states. In this setting of 'to observe or not to observe' state at the encoder, we compute certain numerical examples and note a pleasing phenomenon, where encoder can observe a relatively small fraction of states and yet communicate at maximum rate, i.e. rate when observing states at encoder is not cost constrained.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Feedback Capacity of the Compound Channel

In this work we find the capacity of a compound finite-state channel with time-invariant deterministic feedback. The model we consider involves the use of fixed length block codes. Our achievability result includes a proof of the existence of a universal decoder for the family of finite-state channels with feedback. As a consequence of our capacity result, we show that feedback does not increase the capacity of the compound Gilbert-Elliot channel. Additionally, we show that for a stationary and uniformly ergodic Markovian channel, if the compound channel capacity is zero without feedback then it is zero with feedback. Finally, we use our result on the finite-state channel to show that the feedback capacity of the memoryless compound channel is given by $\inf_θ \max_{Q_X} I(X;Y|θ)$.

0 citations0 reviewsNo code linkedOpen access