nils-herrmann/clean_scirepeval huggingface dataset:
A Graph-Based Framework for Transmission of Correlated Sources Over Multiple-Access Channels

In this paper, we consider a graph-based framework for transmission of correlated sources over multiple-access channels. It is well known that the separation approach is not optimal for this multiuser communication. Our objective in this work is to reintroduce modularity in this problem using a graph-based discrete interface and to minimize the performance loss as compared to the optimal joint source-channel coding scheme. The proposed framework envisages a transmission systems with two modules: a source-coding module and a channel-coding module. In the former module, the correlated sources are encoded distributively into correlated messages whose correlation structure can be associated with a bipartite graph. These correlated messages are then encoded by using correlated codewords and are reliably transmitted over the multiple-access channel in the latter module. This leads to performance gains in terms of enlarging the class of correlated sources that can be reliably transmitted over a multiple-access channel as compared to the conventional separation approach. We provide an information-theoretic characterization of 1) the rate of exponential growth (as a function of the number of channel uses) of the size of the bipartite graphs whose edges can be reliably transmitted over a multiuser channel and 2) the rate of exponential growth (as a function of the number of source samples) of the size of the bipartite graphs which can reliably represent a pair of correlated sources to be transmitted over a multiuser channel.
Distributed source coding using syndromes (DISCUS): design and construction

We address the problem of compressing correlated distributed sources, i.e., correlated sources which are not co-located or which cannot cooperate to directly exploit their correlation. We consider the related problem of compressing a source which is correlated with another source that is available only at the decoder. This problem has been studied in the information theory literature under the name of the Slepian-Wolf (1973) source coding problem for the lossless coding case, and as "rate-distortion with side information" for the lossy coding case. We provide a constructive practical framework based on algebraic trellis codes dubbed as DIstributed Source Coding Using Syndromes (DISCUS), that can be applicable in a variety of settings. Simulation results are presented for source coding of independent and identically distributed (i.i.d.) Gaussian sources with side information available at the decoder in the form of a noisy version of the source to be coded. Our results reveal the promise of this approach: using trellis-based quantization and coset construction, the performance of the proposed approach is 2-5 dB from the Wyner-Ziv (1976) bound.
Secrecy via Sources and Channels

Alice and Bob want to share a secret key and to communicate an independent message, both of which they desire to be kept secret from an eavesdropper Eve. This problem of secret communication and secret-key generation when two resources are available-correlated sources at Alice, Bob, and Eve, and a noisy broadcast channel from Alice to Bob and Eve which is independent of the sources is studied. The goal is to characterize the fundamental tradeoff between the rates of the secret message and secret key. An achievable solution and proof of its optimality for the parallel channels and sources case when each subchannel and source component satisfies a degradation order (either in favor of the legitimate receiver or the eavesdropper) is presented. This includes the case of jointly Gaussian sources and an additive Gaussian channel, for which the secrecy region is evaluated.
Secrecy via sources and channels — A secret key - Secret message rate tradeoff region

Alice and Bob want to share a secret key and to communicate an independent message, both of which they desire to be kept secret from an eavesdropper Eve. We study this problem of secret communication and secret key generation when two resources are available - correlated sources at Alice, Bob, and Eve, and a noisy broadcast channel from Alice to Bob and Eve. No other resource, in particular, no other channel is available. We are interested in characterizing the fundamental trade-off between the rates of the secret message and secret key. We present an achievable solution based on a separation architecture and prove its optimality under three settings: when Eve's source and channel are degraded versions of Bob's, and either Bob's source or channel is by itself useless in generating a secret key.
Hierarchical backward motion compensation for wavelet video coding using optimized interpolation filters

We describe a spatially scalable video coding framework in which motion correspondences between successive video frames are exploited in the wavelet transform domain in a purely backward fashion. The basic motivation for our coder is that motion fields are typically smooth and therefore can be efficiently captured through a multiresolutional framework. A wavelet decomposition is applied on each video frame and the coefficients at each level are predicted from the coarser level through backward motion compensation. To remove the aliasing effects caused by downsampling in the transform, a special interpolation filter is designed with the weighted aliasing energy as part of the optimization goal, and motion estimation is carried out with lowpass filtering and interpolation in the estimation loop. A novel adaptive quantization scheme is then applied to code the motion predicted residue wavelet coefficients in each band. Experimental results reveal typically a 0.5-2 dB increase on coded PSNR at 24-48 kb/s over the state-of-the-art H.263 standard, with also a considerable improvement in subjective reconstruction quality.
Causal and Strictly Causal Estimation for Jump Linear Systems: An LMI Analysis

Jump linear systems are linear state-space systems with random time variations driven by a finite Markov chain. These models are widely used in nonlinear control, and more recently, in the study of communication over lossy channels. This paper considers a general jump linear estimation problem of estimating an unknown signal from an observed signal, where both signals are described as outputs of a jump linear system. A bound on the minimum achievable estimation error in terms of linear matrix inequalities (LMIs) is presented, along with a simple jump linear estimator that achieves this bound. While previous analysis has considered only the strictly causal estimation problem, this work presents both strictly causal and causal solutions.
A binary Markov model for the quantized images and its rate/distortion optimization

Zerotree based algorithms represent the state of the art in wavelet based image coding. At a high level, these algorithms can be described as first sending a map of the locations of the zero coefficients (the set of zerotree symbols), and then sending the value of nonzero coefficients. However, the decision of what map to send is typically made using some simplifying assumption on the structure of the map, motivated by some empirically observed property of the data (e.g., that zero coefficients are likely to appear in tree structured sets). In this article, the map of the locations of the zero coefficients is optimally estimated as a hidden binary Markov random field (MRF). Algorithms are presented for the estimation of the hidden field given the observed wavelet coefficients, for encoding the field, and for encoding the data given the field estimate. Simulation results show a very competitive rate/distortion performance of the coding algorithm, equal or superior to any published zerotree based image coder: this fact provides conclusive empirical evidence that the proposed model is appropriate for the data.
Optimal demand response with energy storage management

We consider the problem of optimal demand response with energy storage management for a power consuming entity. The entity's objective is to find an optimal control policy for deciding how much load to consume, how much power to purchase from/sell to the power grid, and how to use the finite capacity energy storage device and renewable energy, so as to minimize his average cost, being the disutility due to load-shedding and cost for purchasing power. Due to the coupling effect of the finite size energy storage, such problems are challenging and are typically tackled using dynamic programming, which is often complex in computation and requires substantial statistical information of the system dynamics. We instead develop a low-complexity algorithm called Demand Response with Energy Storage Management (DR-ESM). DR-ESM does not require any statistical knowledge of the system dynamics, including the renewable energy and the power prices. It only requires the entity to solve a small convex optimization program with 6 variables and 6 linear constraints every time for decision making. We prove that DR-ESM is able to achieve near-optimal performance and explicitly compute the required energy storage size.
Distributed beamforming with binary signaling

We consider a distributed beamforming problem where nodes are restricted to sending binary phases to a receiver that has access to a one-bit feedback channel. Our simplified model allows us to prove a rigorous lower bound on the running time and to explore algorithmic techniques and analyses. We demonstrate both upper and lower bounds on the convergence time that are linear in the number of nodes in the system. Our upper bound is given by analyzing a simple randomized algorithm. We also discuss methods for accurately approximating the convergence time numerically that apply to this algorithm, as well as more general algorithms. Finally, we investigate modifications of the basic algorithm which improve the constant factor in the running time.
Regenerating codes for errors and erasures in distributed storage

Regenerating codes are a class of codes proposed for providing reliability of data and efficient repair of failed nodes in distributed storage systems. In this paper, we address the fundamental problem of handling errors and erasures at the nodes or links, during the data-reconstruction and node-repair operations. We provide explicit regenerating codes that are resilient to errors and erasures, and show that these codes are optimal with respect to storage and bandwidth requirements. As a special case, we also establish the capacity of a class of distributed storage systems in the presence of malicious adversaries. While our code constructions are based on previously constructed Product-Matrix codes, we also provide necessary and sufficient conditions for introducing resilience in any regenerating code.
A novel hybrid technique for discrete rate-distortion optimization with applications to fast codebook search for SVQ

A key part of any efficient source coder involves the optimal allocation of bit rate among a discrete set of competing quantization choices, as employed in the selected coding paradigm. This can be classified under the general label of budget-constrained discrete optimization, with coding applications including optimal bit allocation in scalar or vector quantizer based frameworks, entropy-constrained quantization frameworks, and codebook search for scalar-vector quantization (SVQ). For this class of problems dynamic programming (DP) methods (such as the Viterbi algorithm) provide the optimal solution. However DP is typically very costly computationally. An alternate technique to solving this class of problems uses Lagrange multipliers. This approach is much more efficient than DP but cannot guarantee optimality in general as it limits itself to convex-hull operating points, which may be sparse in many applications. We propose a novel hybrid technique that combines the speed of the Lagrangian approach with the versatility of the DP technique that is aimed at extracting the "best of both worlds". We present an application of our hybrid technique to the codebook search problem for SVQ, demonstrating significantly improved speed over the previously proposed DP-based search methods while mitigating the suboptimality of the Lagrangian based approach.
Efficient interactive algorithms for file synchronization under general edits

This paper considers the problem of synchronizing of two remotely located data sources, which are mis-synchronized due to deletions, insertions and substitutions (collectively called `edits'). We focus on the following model. There are two distant nodes, with one having a binary sequence X, and the other having Y. Y is an edited version of X, where the editing involves random deletions, insertions, and substitutions, possibly in bursts. The problem is to synchronize Y with X with minimal exchange of information over a noiseless link. The amount of information exchanged is measured in terms of both the average communication rate and the average number of interactive rounds of communication. The goal is to synchronize Y to X, either exactly or within a target Hamming distance. We build on earlier work  which introduced an interactive algorithm based on Varshamov-Tenengolts codes to synchronize from insertion and deletion edits (indels). The assumption is that the number of edits is small (o(n) where n is the file size). First, we show how the original algorithm can be modified to work with a limited number of rounds, and quantify the trade-off between the number of rounds and the communication rate. Next, we present an extension of the algorithm to deal with the practically important case where the insertions and deletions occur in (potentially large) bursts. Finally, we show how to synchronize the sources to within a target Hamming distance. This feature can be used to differentiate between substitution and indel edits.
Multiresolution graph signal processing via circulant structures

We use circulant structures to present a new framework for multiresolution analysis and processing of graph signals. Among the essential features of circulant graphs is that they accommodate fundamental signal processing operations, such as linear shift-invariant filtering, downsampling, upsampling, and reconstruction-features that offer substantial advantage. We design two-channel, critically-sampled, perfect-reconstruction, orthogonal lattice-filter structures to process signals defined on circulant graphs. To extend our reach to noncirculant graphs, we present a method to decompose a connected, undirected graph into a combination of circulant graphs. To evaluate our proposed framework, we offer examples of synthetic and real-world graph signal data and their multiscale decompositions.
An integrated source coding and congestion control framework for video streaming in the Internet

We describe a framework for video transmission over the Internet that features the coordinated operation of an application-layer video source coding algorithm and a transport-layer rate control mechanism. The proposed video coding scheme operates on a progressively encoded video stream and provides graceful resilience to network packet drops. The robustness is enabled through a generalized multiple description (MD) coding strategy, architectured as an adaptive array of packet-erasure correction codes. The video coding algorithm is matched to an efficient and reactive rate control mechanism that minimizes the fluctuation of rate and uses the profile of past losses to adjust the rate in a TCP-friendly manner. While the two constituent algorithms identified above are interesting in their own right, a key feature of this work is the integration of these algorithms in a simple framework that seeks to maximize the expected delivered video quality at the receiver through coordinated adaptation of the two components. We present simple simulation results to illustrate the utility of our approach.
Wavelet-regularized graph semi-supervised learning

Graph semi-supervised learning (GSSL) is a technique that uses a combination of labeled and unlabeled nodes on a graph to determine a classifier for new, incoming data. This problem can be analyzed through the lens of graph signal processing. In particular, the penalty functions used in the optimization formulation of standard GSSL algorithms can be interpreted as appropriately-defined filters in the Graph Fourier domain. We propose a wavelet-regularized semi-supervised learning algorithm using suitably-defined spline-like graph wavelets. These wavelets are critically-sampled, perfect-reconstruction basis representations, in contrast to much of the existing work proposing overcomplete representations. Critical sampling is essential for controlling the complexity in applications dealing with large scale datasets. We are also interested in understanding when wavelet-regularized approaches perform better than traditional Fourier-based regularizers. We compare the performance of our proposed spline-like, wavelet-regularized learning algorithm (as well as other existing graph wavelet designs) to some standard graph semi-supervised learning techniques on synthetic and real-world datasets.
On scheduling redundant requests with cancellation overheads

Reducing latency in distributed computing and data storage systems is gaining increasing importance. Several empirical works have reported on the efficacy of scheduling redundant requests in such systems. That is, one may reduce job latency by 1) scheduling the same job at more than one server and 2) waiting only until the fastest of them responds. Inspired by the empirically observed gains of such schemes, several theoretical models have been proposed to explain the power of using redundant requests. Although the proposed models in the literature provide useful insights such as when scheduling redundant requests can be beneficial, all these results rely heavily on a common assumption: all redundant requests of a job can be immediately cancelled as soon as one of them is completed. In this paper, we study how one should schedule redundant requests when such assumption does not hold. This is of great importance in practice since cancellation of running jobs typically incurs non-negligible delays. In order to bridge the gap between the existing models and practice, we propose a new queueing model that captures such cancellation delays. We then find how one can schedule redundant requests to achieve the optimal average job latency when cancellation delay is considered and accounted for. Our results show that even with a small cancellation overhead, the actual optimal scheduling policy differs significantly from the optimal scheduling policy when the overhead is zero. Further, we study optimal dynamic scheduling policies, which appropriately schedule redundant requests based on the number of jobs in the system. Our analysis reveals that for the twoserver case, the optimal dynamic scheduler can achieve 7% to 16% lower average job latency, compared with the optimal static scheduler. This observation is in stark contrast to the known fact that the optimal static scheduler performs as well as the optimal dynamic scheduler when cancellation overhead is ignored, affirming that misleading conclusions result if the cancellation overhead is ignored completely.
PRISM: an error-resilient video coding paradigm for wireless networks

We describe PRISM (power-efficient, robust, high-compression, syndrome-based multimedia coding), an error-resilient video-coding paradigm built on the principles of distributed source coding from multi-user information theory. PRISM represents a radical departure from the current state-of-the-art video coding architectures, like MPEG, that are based on a motion-compensated prediction framework. These are hampered by: (i) a rigid computational complexity partition between encoder (heavy) and decoder (light); and (U) high fragility to drift between encoder and decoder in the face of prediction mismatch due to channel loss. In contrast, PRISM's architectural goals are: (i) to have a channel-adaptive distribution of computational complexity between encoder and decoder; and (ii) to have built-in robustness to drift between encoder and decoder due to wireless channel loss. These features make PRISM ideally suited for low-latency multimedia transmission over wireless networks, particularly for uplink-rich applications.
Information-theoretic limits on sparse support recovery: Dense versus sparse measurements

We study the information-theoretic limits of exactly recovering the support of a sparse signal using noisy projections defined by various classes of measurement matrices. Our analysis is high-dimensional in nature, in which the number of observations n, the ambient signal dimension p, and the signal sparsity k are all allowed to tend to infinity in a general manner. This paper makes two novel contributions. First, we provide sharper necessary conditions for exact support recovery using general (non-Gaussian) dense measurement matrices. Combined with previously known sufficient conditions, this result yields a sharp characterization of when the optimal decoder can recover a signal with linear sparsity (k = Theta(p)) using a linear scaling of observations (n = Theta(p)) in the presence of noise. Our second contribution is to prove necessary conditions on the number of observations n required for asymptotically reliable recovery using a class of gamma-sparsified measurement matrices, where the measurement sparsity gamma(n, p, k) isin (0,1] corresponds to the fraction of non-zero entries per row. Our analysis allows general scaling of the quadruplet (n, p, k, gamma), and reveals three different regimes, corresponding to whether measurement sparsity has no effect, a minor effect, or a dramatic effect on the information theoretic limits of the subset recovery problem.
Joint source channel matching for a wireless communications link

With the rapid growth of wireless communications systems there is an increasing demand for efficient image and video transmission. Significant performance gains can be obtained from joint source channel matching where system resources are assigned based on the tradeoff between data and redundancy. We develop a more general approach for joint source channel matching based on a parametric distortion model that incorporates the flexibility and constraints of both the source and the channel. We use parametric models describing source and channel. We use parametric models describing source and channel characteristics that can be accurately applied to most classes of source and channel coders. To show the generality of our approach, we applied it to the familiar Said-Pearlman progressive image coder with two types of channel coders, a coder with orthogonal symbols of different power, and fixed-rate BPSK modulation overlaid with Reed Solomon codes.