检索结果-内蒙古大学图书馆

Lossy Computing of Correlated Sources with Fractional Sampling

IEEE TRANSACTIONS ON COMMUNICATIONS 2013年第9期61卷 3685-3696页

作者： Liu, Xi Simeone, Osvaldo Erkip, Elza Broadcom Matawan NJ 07747 USA New Jersey Inst Technol ECE Dept Newark NJ 07102 USA NYU Polytech Inst ECE Dept Brooklyn NY 11201 USA

This paper considers the problem of lossy compression for the computation of a function of two correlated sources, both of which are observed at the encoder. Due to presence of observation costs, the encoder is allowed to observe only subsets of the samples from both sources, with a fraction of such sample pairs possibly overlapping. The rate-distortion function is characterized for memoryless sources, and then specialized to Gaussian and binary sources for selected functions and with quadratic and Hamming distortion metrics, respectively. The optimal measurement overlap fraction is shown to depend on the function to be computed by the decoder, on the source statistics, including the correlation, and on the link rate. Special cases are discussed in which the optimal overlap fraction is the maximum or minimum possible value given the sampling budget, illustrating non-trivial performance trade-offs in the design of the sampling strategy. Finally, the analysis is extended to the multi-hop set-up with jointly Gaussian sources, where each encoder can observe only one of the sources.

关键词： Multi-terminal rate-distortion theory function computation fractional sampling

来源：评论

学校读者我要写书评

暂无评论

The Infinite-Message Limit of Two-Terminal Interactive Source Coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2013年第7期59卷 4071-4094页

作者： Ma, Nan Ishwar, Prakash Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94709 USA Boston Univ Dept Elect & Comp Engn Boston MA 02215 USA

A two-terminal interactive function computation problem with alternating messages is studied within the framework of distributed block source coding theory. For any finite number of messages, a single-letter characterization of the sum-rate-distortion function was established in previous works using standard information-theoretic techniques. This, however, does not provide a satisfactory characterization of the infinite-message limit, which is a new, unexplored dimension for asymptotic analysis in distributed block source coding involving potentially an infinite number of infinitesimal-rate messages. In this paper, the infinite-message sum-rate-distortion function, viewed as a functional of the joint source distribution and the distortion levels, is characterized as the least element of a partially ordered family of functionals having certain convex-geometric properties. The new characterization does not involve evaluating the infinite-message limit of a finite-message sum-rate-distortion expression. This characterization leads to a family of lower bounds for the infinite-message sum-rate-distortion expression and a simple criterion to test the optimality of any achievable infinite-message sum-rate-distortion expression. The new convex-geometric characterization is used to develop an iterative algorithm for evaluating any finite-message sum-rate-distortion function. It is also used to construct the first examples which demonstrate that for lossy source reproduction, two messages can strictly improve the one-message Wyner-Ziv rate-distortion function settling an unresolved question from a 1985 paper. It is shown that a single backward message of arbitrarily small rate can lead to an arbitrarily large gain in the sum-rate.

关键词： Alternating convexification Boolean AND communication complexity distributed source coding function computation interactive coding Wyner-Ziv coding

来源：评论

学校读者我要写书评

暂无评论

Linear Codes, Target function Classes, and Network Computing Capacity

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2013年第9期59卷 5741-5753页

作者： Appuswamy, Rathinakumar Franceschetti, Massimo Karamchandani, Nikhil Zeger, Kenneth IBM Res Almaden San Jose CA 95120 USA Univ Calif San Diego Dept Elect & Comp Engn La Jolla CA 92093 USA Univ Calif Los Angeles Dept Elect Engn Los Angeles CA 90095 USA

We study the use of linear codes for network computing in single-receiver networks with various classes of target functions of the source messages. Such classes include reducible, semi-injective, and linear target functions over finite fields. Computing capacity bounds and achievability are given with respect to these target function classes for network codes that use routing, linear coding, or nonlinear coding.

关键词： Capacity cut-set bound function computation information theory network coding

来源：评论

学校读者我要写书评

暂无评论

Optimal computation of Symmetric Boolean functions in Collocated Networks

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2013年第4期31卷 639-654页

作者： Kowshik, Hemant Kumar, P. R. Amazon Dev Ctr Advertising Optimizat Grp Bangalore Karnataka India Texas A&M Univ Dept Elect & Comp Engn College Stn TX USA

We consider collocated wireless sensor networks, where each node's transmissions can be heard by every other node. Each node has a Boolean measurement and the goal of the network is to compute a given Boolean function of these measurements. We first consider the worst case setting and study optimal block computation strategies for computing symmetric Boolean functions. We study three classes of functions: threshold functions, delta functions and interval functions. We provide optimal strategies for the first two classes, and a scaling law order-optimal strategy with optimal preconstant for interval functions. We extend the results to the case of integer measurements and certain integer-valued functions. Next, we address the problem of minimizing the expected total number of bits that are transmitted when node measurements are random and drawn from independent Bernoulli distributions. In the case of computing a single instance of a Boolean threshold function, the problem reduces to one of determining the optimal order in which the nodes should transmit. We show that the optimal order of transmissions depends in an extremely simple way on the values of previously transmitted bits and the ordering of the marginal probabilities of the Boolean variables according to the k-th least likely rule: At any transmission, the node that transmits is the one that has the k-th least likely value of its Boolean variable, where k reduces by one whenever a node transmits a one. Initially the value of k is (n + 1 - Threshold). Interestingly, the order of transmissions does not depend on the exact values of the probabilities of the Boolean variables. In the case of identically distributed measurements, we further show that the average-case complexity of block computation of a Boolean threshold function is O(theta), where theta is the threshold. We further show how to generalize to a pulse model of communication. One can also consider the related problem of approximate computation given

关键词： In-network computation function computation Communication Complexity Sequential Decision-making

来源：评论

学校读者我要写书评

暂无评论

Communicating the Sum of Sources Over a Network

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2013年第4期31卷 655-665页

作者： Ramamoorthy, Aditya Langberg, Michael Iowa State Univ Dept Elect & Comp Engn Ames IA 50011 USA Open Univ Israel Div Comp Sci IL-43107 Raanana Israel

We consider the network communication scenario, over directed acyclic networks with unit capacity edges in which a number of sources s(i) each holding independent unit-entropy information X-i wish to communicate the sum Sigma X-i to a set of terminals t(j). We show that in the case in which there are only two sources or only two terminals, communication is possible if and only if each source terminal pair s(i)/t(j) is connected by at least a single path. For the more general communication problem in which there are three sources and three terminals, we prove that a single path connecting the source terminal pairs does not suffice to communicate Sigma X-i. We then present an efficient encoding scheme which enables the communication of Sigma X-i for the three sources, three terminals case, given that each source terminal pair is connected by two edge disjoint paths.

关键词： Network coding function computation multicast distributed source coding

来源：评论

学校读者我要写书评

暂无评论

On Network Coding for Sum-Networks

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2012年第1期58卷 50-63页

作者： Rai, Brijesh Kumar Dey, Bikash Kumar Indian Inst Technol Dept Elect Engn Bombay Maharashtra India

A directed acyclic network is considered where all the terminals need to recover the sum of the symbols generated at all the sources. We call such a network a sum-network. It is shown that there exists a solvably (and linear solvably) equivalent sum-network for any multiple-unicast network, and thus for any directed acyclic communication network. It is also shown that there exists a linear solvably equivalent multiple-unicast network for every sum-network. It is shown that for any set of polynomials having integer coefficients, there exists a sum-network which is scalar linear solvable over a finite field if and only if the polynomials have a common root in. For any finite or cofinite set of prime numbers, a network is constructed which has a vector linear solution of any length if and only if the characteristic of the alphabet field is in the given set. The insufficiency of linear network coding and unachievability of the network coding capacity are proved for sum-networks by using similar known results for communication networks. Under fractional vector linear network coding, a sum-network and its reverse network are shown to be equivalent. However, under nonlinear coding, it is shown that there exists a solvable sum-network whose reverse network is not solvable.

关键词： function computation linear network coding network coding polynomial equations solvability

来源：评论

学校读者我要写书评

暂无评论

Distributed symmetric function computation in noisy wireless sensor networks

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2007年第12期53卷 4826-4833页

作者： Ying, Lei Srikant, R. Dullerud, Geir E. Univ Illinois Dept Elect & Comp Engn Coordinated Sci Lab Urbana IL 61801 USA Univ Illinois Dept Mech & Ind Engn Coordinated Sci Lab Urbana IL 61801 USA

In this correspondence, we consider a wireless sensor network consisting of n sensors, and each sensor has a measurement, which is an integer value belonging to the set {0,..., m - 1}, so that it can be represented by [log(2) m] bits. The network has a special node called the fusion center whose goal is to compute a symmetric function of these measurements. The problem studied is to minimize the total transmission energy used by the network when computing this function, subject to the constraint that this computation be correct with high probability. We assume the wireless channels are binary symmetric channels with a probability of error p, and that each sensor uses r(alpha) units of energy to transmit each bit, where r is the transmission range of the sensor. For constant m, the main result in this correspondence is an algorithm whose energy usage is k [log(2) m] n (log log n) (8 root log n/n)(alpha), where k = [4/- log(4p(1-p))]. Then, we consider the case where the sensor network observes N events. In this case, we demonstrate a network algorithm which has energy usage circle minus (n(root log n/n)(alpha)) per event if the number of events satisfies N = Omega(log logn).

关键词： binary symmetric channel function computation reception diversity sensor network wireless network

来源：评论

学校读者我要写书评

暂无评论

Network Coding for Computing: Cut-Set Bounds

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第2期57卷 1015-1030页

作者： Appuswamy, Rathinakumar Franceschetti, Massimo Karamchandani, Nikhil Zeger, Kenneth Univ Calif San Diego Dept Elect & Comp Engn La Jolla CA 92093 USA

The following network computing problem is considered. Source nodes in a directed acyclic network generate independent messages and a single receiver node computes a target function of the messages. The objective is to maximize the average number of times can be computed per network usage, i.e., the "computing capacity". The network coding problem for a single-receiver network is a special case of the network computing problem in which all of the source messages must be reproduced at the receiver. For network coding with a single receiver, routing is known to achieve the capacity by achieving the network min-cut upper bound. We extend the definition of min-cut to the network computing problem and show that the min-cut is still an upper bound on the maximum achievable rate and is tight for computing (using coding) any target function in multi-edge tree networks. It is also tight for computing linear target functions in any network. We also study the bound's tightness for different classes of target functions. In particular, we give a lower bound on the computing capacity in terms of the Steiner tree packing number and a different bound for symmetric functions. We also show that for certain networks and target functions, the computing capacity can be less than an arbitrarily small fraction of the min-cut bound.

关键词： Capacity cut-set bound function computation information theory network coding throughput

来源：评论

学校读者我要写书评

暂无评论

When Is a function Securely Computable?

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第10期57卷 6337-6350页

作者： Tyagi, Himanshu Narayan, Prakash Gupta, Piyush Univ Maryland Dept Elect & Comp Engn College Pk MD 20742 USA Univ Maryland Syst Res Inst College Pk MD 20742 USA Alcatel Lucent Bell Labs Murray Hill NJ 07974 USA

A subset of a set of terminals that observe correlated signals seek to compute a function of the signals using public communication. It is required that the value of the function be concealed from an eavesdropper with access to the communication. We show that the function is securely computable if and only if its entropy is less than the capacity of a new secrecy generation model, for which a single-letter characterization is provided.

关键词： Aided secret key balanced coloring lemma function computation maximum common function omniscience secret key capacity secure computability

来源：评论

学校读者我要写书评

暂无评论

In-Network computation in Random Wireless Networks: A PAC Approach to Constant Refresh Rates with Lower Energy Costs

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2011年第1期10卷 146-155页

作者： Iyer, Srikanth K. Manjunath, D. Sundaresan, Rajesh Indian Inst Sci Dept Math Bangalore 560012 Karnataka India Indian Inst Technol Dept Elect Engn Bombay 400076 Maharashtra India Indian Inst Sci Dept Elect Commun Engn Bangalore 560012 Karnataka India

We propose a method to compute a probably approximately correct (PAC) normalized histogram of observations with a refresh rate of Theta(1) time units per histogram sample on a random geometric graph with noise-free links. The delay in computation is Theta(root n) time units. We further extend our approach to a network with noisy links. While the refresh rate remains Theta(1) time units per sample, the delay increases to Theta(root n log n). The number of transmissions in both cases is Theta(n) per histogram sample. The achieved Theta(1) refresh rate for PAC histogram computation is a significant improvement over the refresh rate of Theta(1/log n) for histogram computation in noiseless networks. We achieve this by operating in the supercritical thermodynamic regime where large pathways for communication build up, but the network may have more than one component. The largest component however will have an arbitrarily large fraction of nodes in order to enable approximate computation of the histogram to the desired level of accuracy. Operation in the supercritical thermodynamic regime also reduces energy consumption. A key step in the proof of our achievability result is the construction of a connected component having bounded degree and any desired fraction of nodes. This construction may also prove useful in other communication settings on the random geometric graph.

关键词： Ad hoc network wireless sensor network function computation PAC computation percolation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：