nils-herrmann/clean_scirepeval huggingface dataset:
Low-Complexity Interactive Algorithms for Synchronization From Deletions, Insertions, and Substitutions

Consider two remote nodes having binary sequences X and Y, respectively. Y is an edited version of X, where the editing involves random deletions, insertions, and substitutions, possibly in bursts. The goal is for the node with Y to reconstruct X with minimal exchange of information over a noiseless link. The communication is measured in terms of both the total number of bits exchanged and the number of interactive rounds of communication. This paper focuses on the setting where the number of edits is o(n/log n), where n is the length of X. We first consider the case where the edits are a mixture of insertions and deletions (indels), and propose an interactive synchronization algorithm with near-optimal communication rate and average computational complexity of O(n) arithmetic operations. The algorithm uses interaction to efficiently split the source sequence into substrings containing exactly one deletion or insertion. Each of these substrings is then synchronized using an optimal one-way algorithm based on the single-deletion correcting channel codes of Varshamov and Tenengolts. We then build on this synchronization algorithm in three different ways. First, it is modified to work with a single round of interaction. The reduction in the number of rounds comes at the expense of higher communication, which is quantified. Next, we present an extension to the practically important case where the insertions and deletions may 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. In addition to theoretical performance bounds, we provide several validating simulation results for the proposed algorithms.
Efficient layered data transport over multicarrier systems using optimized embedded modulation

We tackle the problem of efficient layered or multiresolution (MR) data transmission over multicarrier modulation (MCM) systems. We treat the source as being characterized by multiple layers of importance, i.e., having different bit error rate (BER) requirements. First we consider the MCM systems in a multiresolution framework using multiplexing techniques. Then we present the idea of embedded multicarrier modulation (E-MCM) as an effective way of achieving this, and introduce a fast table-lookup-based power allocation algorithm that optimizes the multicarrier constellation design in terms of maximizing the deliverable throughput bit-rate, subject to a total power constraint. Simulation results of our E-MCM system reveal substantial gains (up to about 25%) in deliverable bit-rates over optimized time-division-multiplexed-based designs.
Joint optimization of scalar and tree-structured quantization of wavelet image decompositions

Wavelet image decompositions generate a tree-structured set of coefficients, providing an hierarchical data-structure for representing images. While early wavelet-based algorithms for image compression concentrated on optimal quantization of wavelet coefficients, several recent researchers have proposed approaches which couple coefficient quantization (either scalar or vector-based) with various strategies for quantizing the tree itself. This paper proposes an image compression algorithm based on optimal bit rate allocation between scalar and tree-structured quantizers. A predictive approach to representing the pruned tree structure is presented, and the entropy of this representation is included in the optimal allocation problem. The algorithm couples Lagrangian optimization of scalar quantizers with a marginal analysis approach for optimizing the tree structure, and achieves excellent coding efficiency in the rate-distortion sense.<<ETX>>
Guest Editorial Communication Methodologies for the Next-Generation Storage Systems

This issue consists of 22 high-caliber papers with contributions from both academia and industry. The papers are organized into the following six sections: (i) Channel Modeling and Signal Processing Algorithms for Emerging Memory Technologies, (ii) Error Control Coding Techniques for Flash Memories, (iii) Algebraic Methods with Applications to Non- Volatile Memories, (iv) Polar Codes with Application to Storage, (v) Performance Limits of Storage Systems, and (vi)Codes for Distributed Network Storage.
Network Coding for Distributed Storage Systems

Peer-to-peer distributed storage systems provide reliable access to data through redundancy spread over nodes across the Internet. A key goal is to minimize the amount of bandwidth used to maintain that redundancy. Storing a file using an erasure code, in fragments spread across nodes, promises to require less redundancy and hence less maintenance bandwidth than simple replication to provide the same level of reliability. However, since fragments must be periodically replaced as nodes fail, a key question is how to generate a new fragment in a distributed way while transferring as little data as possible across the network. In this paper, we introduce a general technique to analyze storage architectures that combine any form of coding and replication, as well as presenting two new schemes for maintaining redundancy using erasure codes. First, we show how to optimally generate MDS fragments directly from existing fragments in the system. Second, we introduce a new scheme called regenerating codes which use slightly larger fragments than MDS but have lower overall bandwidth use. We also show through simulation that in realistic environments, regenerating codes can reduce maintenance bandwidth use by 25% or more compared with the best previous design - a hybrid of replication and erasure codes - while simplifying system architecture.
On joint classification and compression in a distributed source coding framework

In many classification problems of interest, it is desirable to not only classify accurately but also to have access to the "raw data" that was used to do the classification. This naturally leads to the concept of joint classification and compression under system communication (or bandwidth) constraints. A typical system involves a complexity-constrained remote sensing unit and a central processing unit. In this paper, we will address the case of a single remote sensing unit (encoder) and a central processing unit (decoder) and a finite bit rate constraint to abstract the bandwidth-limited channel between the encoder and decoder. The goal is to spend this bit budget in the optimal sense, in terms of classification performance (minimize probability of classification error) as well as to enable reconstruction of the raw data with maximum fidelity (in the rate-distortion sense).
On the transmission of a class of hidden Markov sources over Gaussian channels with applications to image communication

We address the problem of transmission of a useful class of hidden Markov sources with Gaussian observations over a discrete-time power-constrained AWGN channel. Our source model approximates the wavelet representation of natural images, and is motivated by the successful modeling approaches in the state-of-the-art image compression and restoration methods. We derive information-theoretic performance bounds, and propose a simple yet efficient joint source-channel coding solution which combines analog and digital modes of transmission. Our results indicate the promise of the proposed approach to the problem of robust image communication.
Wireless image transmission using multiple-description based concatenated codes

This work introduces a multiple-description product code which aims at optimally generating multiple, equally-important wavelet image descriptions from an image encoded by the popular SPIHT image coder. Because the SPIHT image coder is highly sensitive to errors, forward error correction is used to protect the image against bit errors occurring in the channel. The error-correction code is a concatenated channel code including a row (outer) code based on RCPC codes with CRC error detection and a source-channel column (inner) code consisting of the scalable SPIHT image coder and an optimized array of unequal protection Reed-Solomon erasure-correction codes. By matching the unequal protection codes to the embedded source bitstream using our simple, fast optimizer, we maximize expected image quality and provide for graceful degradation of the received image during fades. To achieve unequal protection, each packet is split into many Reed-Solomon symbols. The i/sup th/ symbol in each packet forms an (n,k) Reed-Solomon code or "column". A fast, nearly-optimal optimizer, based on Lagrange multipliers and optimal to within convex hull and discretization approximations, chooses k for each Reed-Solomon "column" to minimize the expected mean-square error at the receiver. We validated our use of this structure by evaluating its performance in the context of transmitting images over a wireless fading channel. The performance of this scheme was evaluated by simulating the transmission of the Lena image over a Clarke flat-fading channel with an average SNR of 10 dB and a normalized Doppler frequency of 10/sup -5/ Hz.
Spline-Like Wavelet Filterbanks for Multiresolution Analysis of Graph-Structured Data

Multiresolution analysis is important for understanding graph signals, which represent graph-structured data. Wavelet filterbanks permit multiscale analysis and processing of graph signals-particularly, useful for harvesting large-scale data. Inspired by first-order spline wavelets in classical signal processing, we introduce two-channel (low-pass and high-pass) wavelet filterbanks for graph signals. This class of filterbanks boasts several useful properties, such as critical sampling, perfect reconstruction, and graph invariance. We consider an application in graph semi-supervised learning and propose a wavelet-regularized semi-supervised learning algorithm that is competitive for certain synthetic and real-world data.
Rate-constrained robust estimation for unreliable sensor networks

We consider the problem of rate-constrained robust estimation of noisy sensor measurements in an unreliable sensor network. Noisy measurements of some physical process (e.g., temperature) made by individual sensors need to be communicated to a central observer over unreliable channels. Limited power resources of the sensors place a strong limit on the resolution with which the noisy sensor readings can be transmitted. Both, the sensors and the communication links can breakdown. However, the central observer is guaranteed to reliably receive readings from a certain minimum number of sensors. The goal of the central observer is to estimate the observed physical process from the received transmissions where a specified distortion metric provides an objective measure of estimation quality. In this work, we present an information-theoretic achievable rate-distortion region for this problem when the sensor measurement noise statistics are symmetric with respect to the sensors. Our results are optimal when the physical process and sensor noise are independent, i.i.d. Gaussian, and the sensor network is only as reliable as guaranteed.
Wavelet denoising by recursive cycle spinning

Coupling the periodic time-invariance of the wavelet transform, with a view to thresholding as a projection, yields a simple, recursive, wavelet-based technique for denoising signals. Estimating a signal from a noise-corrupted observation is a fundamental problem of signal processing which has been addressed via many techniques. Previously,  Donoho (see Wavelets and Statistics,  1995) introduced cycle spinning, a technique of estimating the true signal as the linear average of individual estimates derived from wavelet-thresholded translated versions of the noisy signal. We demonstrate that such an average can be improved upon dramatically. The proposed algorithm recursively "cycle spins" by repeatedly translating and denoising the input via basic wavelet denoising and then translating back; at each iteration, the output of the previous iteration is used as input. Exploiting the convergence properties of projections, our algorithm can be regarded as a sequence of denoising projections that converge to the projection of the original noisy signal to a small subspace containing the true signal. It is proven that the algorithm is guaranteed to converge globally, and simulations on piecewise polynomial signals show marked improvement over both basic wavelet thresholding and standard cycle spinning.
Lower bounds on the rate-distortion function of LDGM codes

We analyze the performance of low-density generator matrix (LDGM) codes for lossy source coding. We first develop a generic technique for deriving lower bounds on the effective rate-distortion functions of binary linear codes. This result provides a source coding analog of a classical result due to Gallager for channel coding over the binary symmetric channel. We illustrate this method for the ensemble of check-regular low- density generator matrix (LDGM) codes by deriving an explicit lower bound on its rate-distortion performance as a function of the check degree.
Non-line-of-sight localization using low-rank + sparse matrix decomposition

We consider the problem of estimating the locations of a set of points in a k-dimensional euclidean space given a subset of the pairwise distance measurements between the points. We focus on the case when some fraction of these measurements can be arbitrarily corrupted by large additive noise. This is motivated by applications like sensor networks, molecular conformation and manifold learning where the measurement process can induce large bias errors in some fraction of the distance measurements due to physical effects like multipath, spin-diffusion etc. Given the NP-completeness of the problem, we propose a convex relaxation that involves decomposing the partially observed matrix of distance measurements into low-rank and sparse components, wherein the low-rank component corresponds to the Euclidean Distance Matrix and the sparse component is a matrix of biases. Using recent results from the literature, we show that this convex relaxation yields the exact solution for the class of fixed radius random geometric graphs. We evaluate the performance of the algorithm on an experimental data set obtained from a network of 44 nodes in an indoor environment and show that the algorithm is robust to non-line-of-sight bias errors.
Robust Video Transmission With Distributed Source Coded Auxiliary Channel

We propose a novel solution to the problem of robust, low-latency video transmission over lossy channels. Predictive video codecs, such as MPEG and H.26x, are very susceptible to prediction mismatch between encoder and decoder or ldquodriftrdquo when there are packet losses. These mismatches lead to a significant degradation in the decoded quality. To address this problem, we propose an auxiliary codec system that sends additional information alongside an MPEG or H.26x compressed video stream to correct for errors in decoded frames and mitigate drift. The proposed system is based on the principles of distributed source coding and uses the (possibly erroneous) MPEG/H.26x decoder reconstruction as side information at the auxiliary decoder. The distributed source coding framework depends upon knowing the statistical dependency (or correlation) between the source and the side information. We propose a recursive algorithm to analytically track the correlation between the original source frame and the erroneous MPEG/H.26x decoded frame. Finally, we propose a rate-distortion optimization scheme to allocate the rate used by the auxiliary encoder among the encoding blocks within a video frame. We implement the proposed system and present extensive simulation results that demonstrate significant gains in performance both visually and objectively (on the order of 2 dB in PSNR over forward error correction based solutions and 1.5 dB in PSNR over intrarefresh based solutions for typical scenarios) under tight latency constraints.
Watermarking based on duality with distributed source coding and robust optimization principles

Inspired by a previously proposed constructive framework for the distributed source coding problem. We propose a powerful constructive approach to the watermarking problem, emphasizing the dual rules of distributed source coding with side information at the decoder and channel coding with side information at the encoder. In our framework, we explore various source and channel codes to close the gap on the achievable capacity of watermarking systems. We propose two methods of solution, one which is based on optimal rate-distortion quantizers and the other based on robust optimization and convex programming. The resulting watermarking schemes, when subjected to additive white gaussian noise (AWGN) attacks, achieve results which are comparable to or better than the best watermarking schemes in the literature.
Information-theoretic bounds on model selection for Gaussian Markov random fields

The problem of graphical model selection is to estimate the graph structure of an unknown Markov random field based on observed samples from the graphical model. For Gaussian Markov random fields, this problem is closely related to the problem of estimating the inverse covariance matrix of the underlying Gaussian distribution. This paper focuses on the information-theoretic limitations of Gaussian graphical model selection and inverse covariance estimation in the high-dimensional setting, in which the graph size p and maximum node degree d are allowed to grow as a function of the sample size n. Our first result establishes a set of necessary conditions on n(p, d) for any recovery method to consistently estimate the underlying graph. Our second result provides necessary conditions for any decoder to produce an estimate Θ̂ Θ of the true inverse covariance matrix T satisfying ‖ Θ̂-Θ ‖ < δin the elementwise ℓ∞-norm (which implies analogous results in the Frobenius norm as well). Combined with previously known sufficient conditions for polynomial-time algorithms, these results yield sharp characterizations in several regimes of interest.
A Multi-Antenna Framework for Spectrum Reuse Based on Primary-Secondary Cooperation

This paper proposes a new framework for spectrum reuse. Existing architectures have centered on secondary users (cognitive radios) that can reliably sense primary users and opportunistically transmit, without directly interacting with the primary system. We present a paradigm in which the primary and secondary systems cooperate, to minimize interference to primary users and provide predictable access for secondary users. Because this architecture gives the primary system full control over spectrum sharing, it could be more favorable in the current economic and political environment. We illustrate a concrete instance of our framework by showing how secondary radios can reuse the entire uplink channel of a cellular network, with only modest changes to the primary infrastructure.
When do redundant requests reduce latency ?

Several systems possess the flexibility to serve requests in more than one way. For instance, a distributed storage system storing multiple replicas of the data can serve a request from any of the multiple servers that store the requested data, or a computational task may be performed in a compute-cluster by any one of multiple processors. In such systems, the latency of serving the requests may potentially be reduced by sending redundant requests: a request may be sent to an excess number of servers, and it is deemed served when the requisite number of servers complete service. Such a mechanism trades off the possibility of faster execution of at least one copy of the request with the increase in the delay due to an increased load on the system. Due to this tradeoff, it is unclear when redundant requests may actually help. Several recent works empirically evaluate the latency performance of redundant requests in diverse settings. This work aims at a rigorous analytical study of the latency performance of redundant requests, with the primary goals of characterizing the situations when sending redundant requests will help (and when not), and designing optimal redundant-requesting policies. We first present a model that captures the key features of such systems. We show that when service times are i.i.d. memoryless or “heavy”, and when the additional copies of already-completed jobs can be removed with negligible costs, redundant requests reduce the average latency. On the other hand, when service times are “light” or when service times are memoryless and removal of jobs results in a non-negligible penalty, not having any redundancy in the request is optimal under high loads. Our results hold for arbitrary arrival processes.
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.
Estimation error bounds for denoising by sparse approximation

If a signal is known to have a sparse representation with respect to a given frame, the signal can be estimated from a noise-corrupted observation of the signal by finding the best sparse approximation to the observation. The ability to remove noise in this manner depends on the frame being designed to efficiently represent the signal while it inefficiently represents the noise. This paper gives bounds to show how inefficiently white Gaussian noise is represented by sparse linear combinations of frame vectors. Combined with knowledge of the approximation efficiency of a given family of frames for a given signal class, this work leads to a better understanding of the merits of frame denoising.
High-Resolution Distributed Sampling of Bandlimited Fields With Low-Precision Sensors

The problem of sampling a discrete-time sequence of spatially bandlimited fields, with a bounded dynamic range, in a distributed, communication-constrained processing environment is studied. A central unit having access to the data gathered by a dense network of low-precision sensors, is required to reconstruct the field snapshots to maximum accuracy. Both deterministic and stochastic field models are considered. For stochastic fields, results are established in the almost-sure sense. The feasibility of having a flexible tradeoff between the oversampling rate (sensor density) and the analog-to-digital converter (ADC) precision, while achieving an exponential accuracy in the number of bits per Nyquist-interval per snapshot is demonstrated. This exposes an underlying “conservation of bits” principle: the bit-budget per Nyquist-interval per snapshot (the rate) can be distributed along the amplitude axis (sensor-precision) and space (sensor density) in an almost arbitrary discrete-valued manner, while retaining the same (exponential) distortion-rate characteristics.