Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInformation-Theoretic Caching: Sequential Coding for Computing
162
0
0.0
(
0
)
Added by
Chien-Yi Wang
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Under the paradigm of caching, partial data is delivered before the actual requests of users are known. In this paper, this problem is modeled as a canonical distributed source coding problem with side information, where the side information represents the users requests. For the single-user case, a single-letter characterization of the optimal rate region is established, and for several important special cases, closed-form solutions are given, including the scenario of uniformly distributed user requests. In this case, it is shown that the optimal caching strategy is closely related to total correlation and Wyners common information. Using the insight gained from the single-user case, three two-user scenarios admitting single-letter characterization are considered, which draw connections to existing source coding problems in the literature: the Gray--Wyner system and distributed successive refinement. Finally, the model studied by Maddah-Ali and Niesen is rephrased to make a comparison with the considered information-theoretic model. Although the two caching models have a similar behavior for the single-user case, it is shown through a two-user example that the two caching models behave differently in general.
rate research
Read More
Motivated by applications in distributed storage, the storage capacity of a graph was recently defined to be the maximum amount of information that can be stored across the vertices of a graph such that the information at any vertex can be recovered from the information stored at the neighboring vertices. Computing the storage capacity is a fundamental problem in network coding and is related, or equivalent, to some well-studied problems such as index coding with side information and generalized guessing games. In this paper, we consider storage capacity as a natural information-theoretic analogue of the minimum vertex cover of a graph. Indeed, while it was known that storage capacity is upper bounded by minimum vertex cover, we show that by treating it as such we can get a 3/2 approximation for planar graphs, and a 4/3 approximation for triangle-free planar graphs. Since the storage capacity is intimately related to the index coding rate, we get a 2 approximation of index coding rate for planar graphs and 3/2 approximation for triangle-free planar graphs. We also show a polynomial time approximation scheme for the index coding rate when the alphabet size is constant. We then develop a general method of gadget covering to upper bound the storage capacity in terms of the average of a set of vertex covers. This method is intuitive and leads to the exact characterization of storage capacity for various families of graphs. As an illustrative example, we use this approach to derive the exact storage capacity of cycles-with-chords, a family of graphs related to outerplanar graphs. Finally, we generalize the storage capacity notion to include recovery from partial node failures in distributed storage. We show tight upper and lower bounds on this partial recovery capacity that scales nicely with the fraction of failures in a vertex.
This work is an extension of our earlier article, where a well-known integral representation of the logarithmic function was explored, and was accompanied with demonstrations of its usefulness in obtaining compact, easily-calculable, exact formulas for quantities that involve expectations of the logarithm of a positive random variable. Here, in the same spirit, we derive an exact integral representation (in one or two dimensions) of the moment of a nonnegative random variable, or the sum of such independent random variables, where the moment order is a general positive noninteger real (also known as fractional moments). The proposed formula is applied to a variety of examples with an information-theoretic motivation, and it is shown how it facilitates their numerical evaluations. In particular, when applied to the calculation of a moment of the sum of a large number, $n$, of nonnegative random variables, it is clear that integration over one or two dimensions, as suggested by our proposed integral representation, is significantly easier than the alternative of integrating over $n$ dimensions, as needed in the direct calculation of the desired moment.
Computation task service delivery in a computing-enabled and caching-aided multi-user mobile edge computing (MEC) system is studied in this paper, where a MEC server can deliver the input or output datas of tasks to mobile devices over a wireless multicast channel. The computing-enabled and caching-aided mobile devices are able to store the input or output datas of some tasks, and also compute some tasks locally, reducing the wireless bandwidth consumption. The corresponding framework of this system is established, and under the latency constraint, we jointly optimize the caching and computing policy at mobile devices to minimize the required transmission bandwidth. The joint policy optimization problem is shown to be NP-hard, and based on equivalent transformation and exact penalization of the problem, a stationary point is obtained via concave convex procedure (CCCP). Moreover, in a symmetric scenario, gains offered by this approach are derived to analytically understand the influences of caching and computing resources at mobile devices, multicast transmission, the number of mobile devices, as well as the number of tasks on the transmission bandwidth. Our results indicate that exploiting the computing and caching resources at mobile devices can provide significant bandwidth savings.
Virtual reality (VR) over wireless is emerging as an important use case of 5G networks. Immersive VR experience requires the delivery of huge data at ultra-low latency, thus demanding ultra-high transmission rate. This challenge can be largely addressed by the recent network architecture known as mobile edge computing (MEC), which enables caching and computing capabilities at the edge of wireless networks. This paper presents a novel MEC-based mobile VR delivery framework that is able to cache parts of the field of views (FOVs) in advance and run certain post-processing procedures at the mobile VR device. To optimize resource allocation at the mobile VR device, we formulate a joint caching and computing decision problem to minimize the average required transmission rate while meeting a given latency constraint. When FOVs are homogeneous, we obtain a closed-form expression for the optimal joint policy which reveals interesting communications-caching-computing tradeoffs. When FOVs are heterogeneous, we obtain a local optima of the problem by transforming it into a linearly constrained indefinite quadratic problem then applying concave convex procedure. Numerical results demonstrate great promises of the proposed mobile VR delivery framework in saving communication bandwidth while meeting low latency requirement.
While Shannons mutual information has widespread applications in many disciplines, for practical applications it is often difficult to calculate its value accurately for high-dimensional variables because of the curse of dimensionality. This paper is focused on effective approximation methods for evaluating mutual information in the context of neural population coding. For large but finite neural populations, we derive several information-theoretic asymptotic bounds and approximation formulas that remain valid in high-dimensional spaces. We prove that optimizing the population density distribution based on these approximation formulas is a convex optimization problem which allows efficient numerical solutions. Numerical simulation results confirmed that our asymptotic formulas were highly accurate for approximating mutual information for large neural populations. In special cases, the approximation formulas are exactly equal to the true mutual information. We also discuss techniques of variable transformation and dimensionality reduction to facilitate computation of the approximations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
