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

Emrah Akyol

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

ResearcherUnclaimed source record
Information Theorymath.ITSystems and Controlmath.OCComputer Science and Game TheorySocial and Information NetworksApplicationsCryptography and SecurityDistributed, Parallel, and Cluster Computingeess.SYMultiagent SystemsMultimediaRobotics

Catalog footprint

What is connected

33works
13topics
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

33 published item(s)

preprint2020arXiv

Impact of Confirmation Bias on Competitive Information Spread in Social Networks

This paper investigates the impact of confirmation bias on competitive information spread in the cyber-social network that comprises individuals in a social network and competitive information sources in cyber layer. We formulate the problem as a zero-sum game, which admits a unique Nash equilibrium in pure strategies. We characterize the dependence of pure Nash equilibrium on the public's innate opinions, the social network topology, as well as the parameters of confirmation bias. We uncover that confirmation bias moves the equilibrium towards the center only when the innate opinions are not neutral, and this move does not occur for the competitive information sources simultaneously. Numerical examples in the context of well-known Krackhardt's advice network are provided to demonstrate the correctness of theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Novel Stealthy Attack and Defense Strategies for Networked Control Systems

This paper studies novel attack and defense strategies, based on a class of stealthy attacks, namely the zero-dynamics attack (ZDA), for multi-agent control systems. ZDA poses a formidable security challenge since its attack signal is hidden in the null-space of the state-space representation of the control system and hence it can evade conventional detection methods. An intuitive defense strategy builds on changing the aforementioned representation via switching through a set of carefully crafted topologies. In this paper, we propose realistic ZDA variations where the attacker is aware of this topology-switching strategy, and hence employs the following policies to avoid detection: (i) pause, update and resume ZDA according to the knowledge of switching topologies; (ii) cooperate with a concurrent stealthy topology attack that alters network topology at switching times, such that the original ZDA is feasible under the corrupted topology. We first systematically study the proposed ZDA variations, and then develop defense strategies against them under the realistic assumption that the defender has no knowledge of attack starting, pausing, and resuming times and the number of misbehaving agents. Particularly, we characterize conditions for detectability of the proposed ZDA variations, in terms of the network topologies to be maintained, the set of agents to be monitored, and the measurements of the monitored agents that should be extracted, while simultaneously preserving the privacy of the states of the non-monitored agents. We then propose an attack detection algorithm based on the Luenberger observer, using the characterized detectability conditions. We provide numerical simulation results to demonstrate our theoretical findings.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Inference of Network Topology and Confirmation Bias in Cyber-Social Networks

This paper studies topology inference, from agent states, of a directed cyber-social network with opinion spreading dynamics model that explicitly takes confirmation bias into account. The cyber-social network comprises a set of partially connected directed network of agents at the social level, and a set of information sources at the cyber layer. The necessary and sufficient conditions for the existence of exact inference solution are characterized. A method for exact inference, when it is possible, of entire network topology as well as confirmation bias model parameters is proposed for the case where the bias mentioned earlier follows a piece-wise linear model. The particular case of no confirmation bias is analyzed in detail. For the setting where the model of confirmation bias is unknown, an algorithm that approximates the network topology, building on the exact inference method, is presented. This algorithm can exactly infer the weighted communication from the neighbors to the non-followers of information sources. Numerical simulations demonstrate the effectiveness of the proposed methods for different scenarios.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Deterministic Annealing Optimization for Witsenhausen's and Related Decentralized Stochastic Control Problems

This note studies the global optimization of controller mappings in discrete-time stochastic control problems including Witsenhausen's celebrated 1968 counter-example. We propose a generally applicable non-convex numerical optimization method based on the concept of deterministic annealing-which is derived from information-theoretic principles and was successfully employed in several problems including vector quantization, classification, and regression. We present comparative numerical results for two test problems that show the strict superiority of the proposed method over prior approaches in the literature.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Information-Theoretic Approach to Strategic Communication as a Hierarchical Game

This paper analyzes the information disclosure problems originated in economics through the lens of information theory. Such problems are radically different from the conventional communication paradigms in information theory since they involve different objectives for the encoder and the decoder, which are aware of this mismatch and act accordingly. This leads, in our setting, to a hierarchical communication game, where the transmitter announces an encoding strategy with full commitment, and its distortion measure depends on a private information sequence whose realization is available at the transmitter. The receiver decides on its decoding strategy that minimizes its own distortion based on the announced encoding map and the statistics. Three problem settings are considered, focusing on the quadratic distortion measures, and jointly Gaussian source and private information: compression, communication, and the simple equilibrium conditions without any compression or communication. The equilibrium strategies and associated costs are characterized. The analysis is then extended to the receiver side information setting and the major changes in the structure of optimal strategies are identified. Finally, an extension of the results to the broader context of decentralized stochastic control is presented.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Role of Side Information In Strategic Communication

This paper analyzes the fundamental limits of strate- gic communication in network settings. Strategic communication differs from the conventional communication paradigms in in- formation theory since it involves different objectives for the encoder and the decoder, which are aware of this mismatch and act accordingly. This leads to a Stackelberg game where both agents commit to their mappings ex-ante. Building on our prior work on the point-to-point setting, this paper studies the compression and communication problems with the receiver and/or transmitter side information setting. The equilibrium strategies and associated costs are characterized for the Gaussian variables with quadratic cost functions. Several questions on the benefit of side information in source and joint source-channel coding in such strategic settings are analyzed. Our analysis has uncovered an interesting result on optimality of uncoded mappings in strategic source-channel coding in networks.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Structure of Equilibrium Strategies in Dynamic Gaussian Signaling Games

This paper analyzes a finite horizon dynamic signaling game motivated by the well-known strategic information transmission problems in economics. The mathematical model involves information transmission between two agents, a sender who observes two Gaussian processes, state and bias, and a receiver who takes an action based on the received message from the sender. The players incur quadratic instantaneous costs as functions of the state, bias and action variables. Our particular focus is on the Stackelberg equilibrium, which corresponds to information disclosure and Bayesian persuasion problems in economics. Prior work solved the static game, and showed that the Stackelberg equilibrium is achieved by pure strategies that are linear functions of the state and the bias variables. The main focus of this work is on the dynamic (multi-stage) setting, where we show that the existence of a pure strategy Stackelberg equilibrium, within the set of linear strategies, depends on the problem parameters. Surprisingly, for most problem parameters, a pure linear strategy does not achieve the Stackelberg equilibrium which implies the existence of a trade-off between exploiting and revealing information, which was also encountered in several other asymmetric information games.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal Communication Scheduling and Remote Estimation over an Additive Noise Channel

This paper considers a sequential sensor scheduling and remote estimation problem with one sensor and one estimator. The sensor makes sequential observations about the state of an underlying memoryless stochastic process and makes a decision as to whether or not to send this measurement to the estimator. The sensor and the estimator have the common objective of minimizing expected distortion in the estimation of the state of the process, over a finite time horizon. The sensor is either charged a cost for each transmission or constrained on transmission times. As opposed to the prior work where communication between the sensor and the estimator was assumed to be perfect (noiseless), in this work an additive noise channel with fixed power constraint is considered; hence, the sensor has to encode its message before transmission. Under some technical assumptions, we obtain the optimal encoding and estimation policies in conjunction with the optimal transmission schedule. The impact of the presence of a noisy channel is analyzed numerically based on dynamic programming. This analysis yields some rather surprising results such as a phase transition phenomenon in the number of used transmission opportunities, which was not encountered in the noiseless communication setting.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Power-Distortion Metrics for Path Planning over Gaussian Sensor Networks

Path planning is an important component of au- tonomous mobile sensing systems. This paper studies upper and lower bounds of communication performance over Gaussian sen- sor networks, to drive power-distortion metrics for path planning problems. The Gaussian multiple-access channel is employed as a channel model and two source models are considered. In the first setting, the underlying source is estimated with minimum mean squared error, while in the second, reconstruction of a random spatial field is considered. For both problem settings, the upper and the lower bounds of sensor power-distortion curve are derived. For both settings, the upper bounds follow from the amplify-and-forward scheme and the lower bounds admit a unified derivation based on data processing inequality and tensorization property of the maximal correlation measure. Next, closed-form solutions of the optimal power allocation problems are obtained under a weighted sum-power constraint. The gap between the upper and the lower bounds is analyzed for both weighted sum and individual power constrained settings. Finally, these metrics are used to drive a path planning algorithm and the effects of power-distortion metrics, network parameters, and power optimization on the optimized path selection are analyzed.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Price of Transparency in Strategic Machine Learning

Based on the observation that the transparency of an algorithm comes with a cost for the algorithm designer when the users (data providers) are strategic, this paper studies the impact of strategic intent of the users on the design and performance of transparent ML algorithms. We quantitatively study the {\bf price of transparency} in the context of strategic classification algorithms, by modeling the problem as a nonzero-sum game between the users and the algorithm designer. The cost of having a transparent algorithm is measured by a quantity, named here as price of transparency which is the ratio of the designer cost at the Stackelberg equilibrium, when the algorithm is transparent (which allows users to be strategic) to that of the setting where the algorithm is not transparent.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Scalar Quadratic-Gaussian Soft Watermarking Games

We introduce the zero-sum game problem of soft watermarking: The hidden information (watermark) comes from a continuum and has a perceptual value; the receiver generates an estimate of the embedded watermark to minimize the expected estimation error (unlike the conventional watermarking schemes where both the hidden information and the receiver output are from a discrete finite set). Applications include embedding a multimedia content into another. We consider in this paper the scalar Gaussian case and use expected mean-squared distortion. We formulate the resulting problem as a zero-sum game between the encoder & receiver pair and the attacker. We show that for the lin- ear encoder, the optimal attacker is Gaussian-affine, derive the optimal system parameters in that case, and discuss the corresponding system behavior. We also provide numerical results to gain further insight and understanding of the system behavior at optimality.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Analog Multiple Descriptions: A Zero-Delay Source-Channel Coding Approach

This paper extends the well-known source coding problem of multiple descriptions, in its general and basic setting, to analog source-channel coding scenarios. Encoding-decoding functions that optimally map between the (possibly continuous valued) source and the channel spaces are numerically derived. The main technical tool is a non-convex optimization method, namely, deterministic annealing, which has recently been successfully used in other mapping optimization problems. The obtained functions exhibit several interesting structural properties, map multiple source intervals to the same interval in the channel space, and consistently outperform the known competing mapping techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Combinatorial Message Sharing and a New Achievable Region for Multiple Descriptions

This paper presents a new achievable rate-distortion region for the general L channel multiple descriptions problem. A well known general region for this problem is due to Venkataramani, Kramer and Goyal (VKG) [1]. Their encoding scheme is an extension of the El-Gamal-Cover (EC) and Zhang- Berger (ZB) coding schemes to the L channel case and includes a combinatorial number of refinement codebooks, one for each subset of the descriptions. As in ZB, the scheme also allows for a single common codeword to be shared by all descriptions. This paper proposes a novel encoding technique involving Combinatorial Message Sharing (CMS), where every subset of the descriptions may share a distinct common message. This introduces a combinatorial number of shared codebooks along with the refinement codebooks of [1]. We derive an achievable rate-distortion region for the proposed technique, and show that it subsumes the VKG region for general sources and distortion measures. We further show that CMS provides a strict improvement of the achievable region for any source and distortion measures for which some 2-description subset is such that ZB achieves points outside the EC region. We then show a more surprising result: CMS outperforms VKG for a general class of sources and distortion measures, including scenarios where the ZB and EC regions coincide for all 2-description subsets. In particular, we show that CMS strictly improves on VKG, for the L-channel quadratic Gaussian MD problem, for all L greater than or equal to 3, despite the fact that the EC region is complete for the corresponding 2-descriptions problem. Using the encoding principles derived, we show that the CMS scheme achieves the complete rate-distortion region for several asymmetric cross-sections of the L-channel quadratic Gaussian MD problem.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Deterministic Annealing Based Optimization for Zero-Delay Source-Channel Coding in Networks

This paper studies the problem of global optimization of zero-delay source-channel codes that map between the source space and the channel space, under a given transmission power constraint and for the mean square error distortion. Particularly, we focus on two well known network settings: the Wyner-Ziv setting where only a decoder has access to side information and the distributed setting where independent encoders transmit over independent channels to a central decoder. Prior work derived the necessary conditions for optimality of the encoder and decoder mappings, along with a greedy optimization algorithm that imposes these conditions iteratively, in conjunction with the heuristic noisy channel relaxation method to mitigate poor local minima. While noisy channel relaxation is arguably effective in simple settings, it fails to provide accurate global optimization in more complicated settings considered in this paper. We propose a powerful non-convex optimization method based on the concept of deterministic annealing -- which is derived from information theoretic principles and was successfully employed in several problems including vector quantization, classification and regression. We present comparative numerical results that show strict superiority of the proposed method over greedy optimization methods as well as prior approaches in literature.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On Remote Estimation with Multiple Communication Channels

This paper considers a sequential estimation and sensor scheduling problem in the presence of multiple communication channels. As opposed to the classical remote estimation problem that involves one perfect (noiseless) channel and one extremely noisy channel (which corresponds to not transmitting the observed state), a more realistic additive noise channel with fixed power constraint along with a more costly perfect channel is considered. It is shown, via a counter-example, that the common folklore of applying symmetric threshold policy, which is well known to be optimal (for unimodal state densities) in the classical two-channel remote estimation problem, can be suboptimal for the setting considered. Next, in order to make the problem tractable, a side channel which signals the sign of the underlying state is considered. It is shown that, under some technical assumptions, threshold-in-threshold communication scheduling is optimal for this setting. The impact of the presence of a noisy channel is analyzed numerically based on dynamic programming. This numerical analysis uncovers some rather surprising results inheriting known properties from the noisy and noiseless settings.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal Estimation with Limited Measurements and Noisy Communication

This paper considers a sequential estimation and sensor scheduling problem with one sensor and one estimator. The sensor makes sequential observations about the state of an underlying memoryless stochastic process, and makes a decision as to whether or not to send this measurement to the estimator. The sensor and the estimator have the common objective of minimizing expected distortion in the estimation of the state of the process, over a finite time horizon, with the constraint that the sensor can transmit its observation only a limited number of times. As opposed to the prior work where communication between the sensor and the estimator was assumed to be perfect (noiseless), in this work an additive noise channel with fixed power constraint is considered; hence, the sensor has to encode its message before transmission. For some specific source and channel noise densities, we obtain the optimal encoding and estimation policies in conjunction with the optimal transmission schedule. The impact of the presence of a noisy channel is analyzed numerically based on dynamic programming. This analysis yields some rather surprising results such as a phase-transition phenomenon in the number of used transmission opportunities, which was not encountered in the noiseless communication setting.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal Sensor Scheduling and Remote Estimation over an Additive Noise Channel

We consider a sensor scheduling and remote estimation problem with one sensor and one estimator. At each time step, the sensor makes an observation on the state of a source, and then decides whether to transmit its observation to the estimator or not. The sensor is charged a cost for each transmission. The remote estimator generates a real-time estimate on the state of the source based on the messages received from the sensor. The estimator is charged for estimation error. As compared with previous works from the literature, we further assume that there is an additive communication channel noise. As a consequence, the sensor needs to encode the message before transmitting it to the estimator. For some specific distributions of the underlying random variables, we obtain the optimal solution to the problem of minimizing the expected value of the sum of communication cost and estimation cost over the time horizon.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Privacy Constrained Information Processing

This paper studies communication scenarios where the transmitter and the receiver have different objectives due to privacy concerns, in the context of a variation of the strategic information transfer (SIT) model of Sobel and Crawford. We first formulate the problem as the minimization of a common distortion by the transmitter and the receiver subject to a privacy constrained transmitter. We show the equivalence of this formulation to a Stackelberg equilibrium of the SIT problem. Assuming an entropy based privacy measure, a quadratic distortion measure and jointly Gaussian variables, we characterize the Stackelberg equilibrium. Next, we consider asymptotically optimal compression at the transmitter which inherently provides some level of privacy, and study equilibrium conditions. We finally analyze the impact of the presence of an average power constrained Gaussian communication channel between the transmitter and the receiver on the equilibrium conditions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Deterministic Annealing Approach to Witsenhausen's Counterexample

This paper proposes a numerical method, based on information theoretic ideas, to a class of distributed control problems. As a particular test case, the well-known and numerically "over-mined" problem of decentralized control and implicit communication, commonly referred to as Witsenhausen's counterexample, is considered. The method provides a small improvement over the best numerical result so far for this benchmark problem. The key idea is to randomize the zero-delay mappings. which become "soft", probabilistic mappings to be optimized in a deterministic annealing process, by incorporating a Shannon entropy constraint in the problem formulation. The entropy of the mapping is controlled and gradually lowered to zero to obtain deterministic mappings, while avoiding poor local minima. Proposed method obtains new mappings that shed light on the structure of the optimal solution, as well as achieving a small improvement in total cost over the state of the art in numerical approaches to this problem.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Deterministic Annealing Optimization Approach for Witsenhausen's and Related Decentralized Control Settings

This paper studies the problem of mapping optimization in decentralized control problems. A global optimization algorithm is proposed based on the ideas of ``deterministic annealing" - a powerful non-convex optimization framework derived from information theoretic principles with analogies to statistical physics. The key idea is to randomize the mappings and control the Shannon entropy of the system during optimization. The entropy constraint is gradually relaxed in a deterministic annealing process while tracking the minimum, to obtain the ultimate deterministic mappings. Deterministic annealing has been successfully employed in several problems including clustering, vector quantization, regression, as well as the Witsenhausen's counterexample in our recent work[1]. We extend our method to a more involved setting, a variation of Witsenhausen's counterexample, where there is a side channel between the two controllers. The problem can be viewed as a two stage cancellation problem. We demonstrate that there exist complex strategies that can exploit the side channel efficiently, obtaining significant gains over the best affine and known non-linear strategies.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Lossy Common Information of Correlated Sources

The two most prevalent notions of common information (CI) are due to Wyner and Gacs-Korner and both the notions can be stated as two different characteristic points in the lossless Gray-Wyner region. Although the information theoretic characterizations for these two CI quantities can be easily evaluated for random variables with infinite entropy (eg., continuous random variables), their operational significance is applicable only to the lossless framework. The primary objective of this paper is to generalize these two CI notions to the lossy Gray-Wyner network, which hence extends the theoretical foundation to general sources and distortion measures. We begin by deriving a single letter characterization for the lossy generalization of Wyner's CI, defined as the minimum rate on the shared branch of the Gray-Wyner network, maintaining minimum sum transmit rate when the two decoders reconstruct the sources subject to individual distortion constraints. To demonstrate its use, we compute the CI of bivariate Gaussian random variables for the entire regime of distortions. We then similarly generalize Gacs and Korner's definition to the lossy framework. The latter half of the paper focuses on studying the tradeoff between the total transmit rate and receive rate in the Gray-Wyner network. We show that this tradeoff yields a contour of points on the surface of the Gray-Wyner region, which passes through both the Wyner and Gacs-Korner operating points, and thereby provides a unified framework to understand the different notions of CI. We further show that this tradeoff generalizes the two notions of CI to the excess sum transmit rate and receive rate regimes, respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Deterministic Annealing Approach to Optimization of Zero-delay Source-Channel Codes

This paper studies optimization of zero-delay source-channel codes, and specifically the problem of obtaining globally optimal transformations that map between the source space and the channel space, under a given transmission power constraint and for the mean square error distortion. Particularly, we focus on the setting where the decoder has access to side information, whose cost surface is known to be riddled with local minima. Prior work derived the necessary conditions for optimality of the encoder and decoder mappings, along with a greedy optimization algorithm that imposes these conditions iteratively, in conjunction with the heuristic "noisy channel relaxation" method to mitigate poor local minima. While noisy channel relaxation is arguably effective in simple settings, it fails to provide accurate global optimization results in more complicated settings including the decoder with side information as considered in this paper. We propose a global optimization algorithm based on the ideas of "deterministic annealing"- a non-convex optimization method, derived from information theoretic principles with analogies to statistical physics, and successfully employed in several problems including clustering, vector quantization and regression. We present comparative numerical results that show strict superiority of the proposed algorithm over greedy optimization methods as well as over the noisy channel relaxation.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Gaussian Sensor Networks with Adversarial Nodes

This paper studies a particular sensor network model which involves one single Gaussian source observed by many sensors, subject to additive independent Gaussian observation noise. Sensors communicate with the receiver over an additive Gaussian multiple access channel. The aim of the receiver is to reconstruct the underlying source with minimum mean squared error. The scenario of interest here is one where some of the sensors act as adversary (jammer): they strive to maximize distortion. We show that the ability of transmitter sensors to secretly agree on a random event, that is "coordination", plays a key role in the analysis. Depending on the coordination capability of sensors and the receiver, we consider two problem settings. The first setting involves transmitters with coordination capabilities in the sense that all transmitters can use identical realization of randomized encoding for each transmission. In this case, the optimal strategy for the adversary sensors also requires coordination, where they all generate the same realization of independent and identically distributed Gaussian noise. In the second setting, the transmitter sensors are restricted to use fixed, deterministic encoders and this setting, which corresponds to a Stackelberg game, does not admit a saddle-point solution. We show that the the optimal strategy for all sensors is uncoded communications where encoding functions of adversaries and transmitters are in opposite directions. For both settings, digital compression and communication is strictly suboptimal.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Large Scale Distributed Compression and Dispersive Information Routing for Networks

This paper considers the problem of distributed source coding for a large network. A major obstacle that poses an existential threat to practical deployment of conventional approaches to distributed coding is the exponential growth of the decoder complexity with the number of sources and the encoding rates. This growth in complexity renders many traditional approaches impractical even for moderately sized networks. In this paper, we propose a new decoding paradigm for large scale distributed compression wherein the decoder complexity is explicitly controlled during the design. Central to our approach is a module called the "bit-subset selector" whose role is to judiciously extract an appropriate subset of the received bits for decoding per individual source. We propose a practical design strategy, based on deterministic annealing (DA) for the joint design of the system components, that enables direct optimization of the decoder complexity-distortion trade-off, and thereby the desired scalability. We also point out the direct connections between the problem of large scale distributed compression and a related problem in sensor networks, namely, dispersive information routing of correlated sources. This allows us to extend the design principles proposed in the context of large scale distributed compression to design efficient routers for minimum cost communication of correlated sources across a network. Experiments on both real and synthetic data-sets provide evidence for substantial gains over conventional approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Optimal Jamming Over an Additive Noise Channel

This paper considers the problem of optimal zero-delay jamming over an additive noise channel. Early work had already solved this problem for a Gaussian source and channel. Building on a sequence of recent results on conditions for linearity of optimal estimation, and of optimal mappings in source-channel coding, we derive the saddle-point solution to the jamming problem for general sources and channels, without recourse to Gaussian assumptions. We show that linearity conditions play a pivotal role in jamming, in the sense that the optimal jamming strategy is to effectively force both transmitter and receiver to default to linear mappings, i.e., the jammer ensures, whenever possible, that the transmitter and receiver cannot benefit from non-linear strategies. This result is shown to subsume the known result for Gaussian source and channel. We analyze conditions and general settings where such unbeatable strategy can indeed be achieved by the jammer. Moreover, we provide the procedure to approximate optimal jamming in the remaining (source-channel) cases where the jammer cannot impose linearity on the transmitter and the receiver.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the Role of Common Codewords in Quadratic Gaussian Multiple Descriptions Coding

This paper focuses on the problem of $L-$channel quadratic Gaussian multiple description (MD) coding. We recently introduced a new encoding scheme in [1] for general $L-$channel MD problem, based on a technique called `Combinatorial Message Sharing' (CMS), where every subset of the descriptions shares a distinct common message. The new achievable region subsumes the most well known region for the general problem, due to Venkataramani, Kramer and Goyal (VKG) [2]. Moreover, we showed in [3] that the new scheme provides a strict improvement of the achievable region for any source and distortion measures for which some 2-description subset is such that the Zhang and Berger (ZB) scheme achieves points outside the El-Gamal and Cover (EC) region. In this paper, we show a more surprising result: CMS outperforms VKG for a general class of sources and distortion measures, which includes scenarios where for all 2-description subsets, the ZB and EC regions coincide. In particular, we show that CMS strictly extends VKG region, for the $L$-channel quadratic Gaussian MD problem for all $L\geq3$, despite the fact that the EC region is complete for the corresponding 2-descriptions problem. Using the encoding principles derived, we show that the CMS scheme achieves the complete rate-distortion region for several asymmetric cross-sections of the $L-$channel quadratic Gaussian MD problem, which have not been considered earlier.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Zero Delay Source-Channel Coding

In this paper, we study the zero-delay source-channel coding problem, and specifically the problem of obtaining the vector transformations that optimally map between the m-dimensional source space and the k-dimensional channel space, under a given transmission power constraint and for the mean square error distortion. We first study the functional properties of this problem and show that the objective is concave in the source and noise densities and convex in the density of the input to the channel. We then derive the necessary conditions for optimality of the encoder and decoder mappings. A well known result in information theory pertains to the linearity of optimal encoding and decoding mappings in the scalar Gaussian source and channel setting, at all channel signal-to-noise ratios (CSNRs). In this paper, we study this result more generally, beyond the Gaussian source and channel, and derive the necessary and sufficient condition for linearity of optimal mappings, given a noise (or source) distribution, and a specified power constraint. We also prove that the Gaussian source-channel pair is unique in the sense that it is the only source-channel pair for which the optimal mappings are linear at more than one CSNR values. Moreover, we show the asymptotic linearity of optimal mappings for low CSNR if the channel is Gaussian regardless of the source and, at the other extreme, for high CSNR if the source is Gaussian, regardless of the channel. Our numerical results show strict improvement over prior methods. The numerical approach is extended to the scenario of source-channel coding with decoder side information. The resulting encoding mappings are shown to be continuous relatives of, and in fact subsume as special case, the Wyner-Ziv mappings encountered in digital distributed source coding systems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Optimization of zero-delay mappings for distributed coding by deterministic annealing

This paper studies the optimization of zero-delay analog mappings in a network setting that involves distributed coding. The cost surface is known to be non-convex, and known greedy methods tend to get trapped in poor locally optimal solutions that depend heavily on initialization. We derive an optimization algorithm based on the principles of "deterministic annealing", a powerful global optimization framework that has been successfully employed in several disciplines, including, in our recent work, to a simple zero-delay analog communications problem. We demonstrate strict superiority over the descent based methods, as well as present example mappings whose properties lend insights on the workings of the solution and relations with digital distributed coding.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Minimum Communication Cost for Joint Distributed Source Coding and Dispersive Information Routing

This paper considers the problem of minimum cost communication of correlated sources over a network with multiple sinks, which consists of distributed source coding followed by routing. We introduce a new routing paradigm called dispersive information routing, wherein the intermediate nodes are allowed to `split' a packet and forward subsets of the received bits on each of the forward paths. This paradigm opens up a rich class of research problems which focus on the interplay between encoding and routing in a network. Unlike conventional routing methods such as in [1], dispersive information routing ensures that each sink receives just the information needed to reconstruct the sources it is required to reproduce. We demonstrate using simple examples that our approach offers better asymptotic performance than conventional routing techniques. This paradigm leads to a new information theoretic setup, which has not been studied earlier. We propose a new coding scheme, using principles from multiple descriptions encoding [2] and Han and Kobayashi decoding [3]. We show that this coding scheme achieves the complete rate region for certain special cases of the general setup and thereby achieves the minimum communication cost under this routing paradigm.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On Conditions for Linearity of Optimal Estimation

When is optimal estimation linear? It is well known that, when a Gaussian source is contaminated with Gaussian noise, a linear estimator minimizes the mean square estimation error. This paper analyzes, more generally, the conditions for linearity of optimal estimators. Given a noise (or source) distribution, and a specified signal to noise ratio (SNR), we derive conditions for existence and uniqueness of a source (or noise) distribution for which the $L_p$ optimal estimator is linear. We then show that, if the noise and source variances are equal, then the matching source must be distributed identically to the noise. Moreover, we prove that the Gaussian source-channel pair is unique in the sense that it is the only source-channel pair for which the mean square error (MSE) optimal estimator is linear at more than one SNR values. Further, we show the asymptotic linearity of MSE optimal estimators for low SNR if the channel is Gaussian regardless of the source and, vice versa, for high SNR if the source is Gaussian regardless of the channel. The extension to the vector case is also considered where besides the conditions inherited from the scalar case, additional constraints must be satisfied to ensure linearity of the optimal estimator.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Subset Typicality Lemmas and Improved Achievable Regions in Multiterminal Source Coding

Consider the following information theoretic setup wherein independent codebooks of N correlated random variables are generated according to their respective marginals. The problem of determining the conditions on the rates of codebooks to ensure the existence of at least one codeword tuple which is jointly typical with respect to a given joint density (called the multivariate covering lemma) has been studied fairly well and the associated rate regions have found applications in several source coding scenarios. However, several multiterminal source coding applications, such as the general multi-user Gray-Wyner network, require joint typicality only within subsets of codewords transmitted. Motivated by such applications, we ask ourselves the conditions on the rates to ensure the existence of at least one codeword tuple which is jointly typical within subsets according to given per subset joint densities. This report focuses primarily on deriving a new achievable rate region for this problem which strictly improves upon the direct extension of the multivariate covering lemma, which has quite popularly been used in several earlier work. Towards proving this result, we derive two important results called `subset typicality lemmas' which can potentially have broader applicability in more general scenarios beyond what is considered in this report. We finally apply the results therein to derive a new achievable region for the general multi-user Gray-Wyner network.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Towards Optimality in Transform Coding

It is well-known for transform coding of multivariate Gaussian sources, that the Karhunen-Loève transform (KLT) minimizes the mean square error distortion. However, finding the optimal transform for general non-Gaussian sources has been an open problem for decades, despite several important advances that provide some partial answers regarding KLT optimality. In this paper, we present a necessary and sufficient condition for optimality of a transform when high resolution, variable rate quantizers are employed. We hence present not only a complete characterization of when KLT is optimal, but also a determining condition for optimality of a general (non-KLT) transform. This necessary and sufficient condition is shown to have direct connections to the well studied source separation problem. This observation can impact source separation itself, as illustrated with a new optimality result. We combine the transform optimality condition with algorithmic tools from source separation, to derive a practical numerical method to search for the optimal transform in source coding. Then, we focus on multiterminal settings, for which {\it conditional} KLT was shown to possess certain optimality properties for Gaussian sources. We derive the optimal orthogonal transform for the setting where side information is only available to the decoder, along with new specialized results specific to the conditions for optimality of conditional KLT. Finally, we consider distributed source coding where two correlated sources are to be transform coded separately but decoded jointly. We derive the necessary and sufficient condition of optimality of the orthogonal transforms. We specialize to find the optimal orthogonal transforms, in this setting, for specific source densities, including jointly Gaussian sources.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A Strictly Improved Achievable Region for Multiple Descriptions Using Combinatorial Message Sharing

We recently proposed a new coding scheme for the L-channel multiple descriptions (MD) problem for general sources and distortion measures involving `Combinatorial Message Sharing' (CMS) [7] leading to a new achievable rate-distortion region. Our objective in this paper is to establish that this coding scheme strictly subsumes the most popular region for this problem due to Venkataramani, Kramer and Goyal (VKG) [3]. In particular, we show that for a binary symmetric source under Hamming distortion measure, the CMS scheme provides a strictly larger region for all L>2. The principle of the CMS coding scheme is to include a common message in every subset of the descriptions, unlike the VKG scheme which sends a single common message in all the descriptions. In essence, we show that allowing for a common codeword in every subset of descriptions provides better freedom in coordinating the messages which can be exploited constructively to achieve points outside the VKG region.

0 citations0 reviewsNo code linkedOpen access