nils-herrmann/clean_scirepeval huggingface dataset:
PhaseCode: Fast and efficient compressive phase retrieval based on sparse-graph codes

We consider the problem of recovering a complex signal x ϵ Cn from m intensity measurements of the form |aix|, 1 ≤ i ≤ m, where ai is a measurement row vector. Our main focus is on the case where the measurement vectors are unconstrained, and where x is exactly K-sparse, or the so-called general compressive phase-retrieval problem. We introduce PhaseCode, a novel family of fast and efficient algorithms (that includes Unicolor PhaseCode and Multicolor PhaseCode) that are based on a sparse-graph coding framework. As one instance, our Unicolor PhaseCode algorithm can provably recover, with high probability, all but a tiny 10-7 fraction of the significant signal components, using at most m = 14K measurements, which is a small constant factor from the fundamental limit, with an optimal O(K) decoding time and an optimal O(K) memory complexity. We provide extensive simulation results that validate the practical power of our proposed algorithms. A key contribution of our work is the novel use of coding-theoretic tools like density evolution methods for the design and analysis of fast and efficient algorithms for compressive phase-retrieval problems. This contrasts and complements popular approaches to the phase retrieval problem based on alternating-minimization, convex-relaxation, and semi-definite programming.
Distributed code constructions for the entire Slepian-Wolf rate region for arbitrarily correlated sources

The Slepian-Wolf coding problem tackles the problem of distributed encoding of correlated discrete-alphabet sources for decoding at a common receiver. In this work, we propose distributed linear block code constructions for attaining any point on the Slepian-Wolf achievable rate region for arbitrarily correlated sources. Specifically, our prescription allows for any arbitrary memoryless joint probability distribution over any arbitrary number of distributed sources, and allows for any arbitrary rate combination that lies in the Slepian-Wolf achievable region. Special cases of our framework include the single source case (wherein our construction reduces to an entropy coder), source coding with side-information at the receiver (so-called corner points of the Slepian-Wolf region), and specific source correlation models (such as induced by a virtual binary symmetric channel model). In this work, we describe how to use low density parity check (LDPC) codes into the proposed framework to solve the general Slepian-Wolf problem constructively.
Optimal supports for linear predictive models

The problem of finding the optimal set of causal pixels (support) for use in linear predictive models is addressed. After presenting counterexamples to popular intuitions about supports, a general result relating the distortion incurred with a small support to optimal coefficients of a larger support is derived. A geometrical interpretation is provided. Two algorithms that optimally increase/decrease support sizes by one at each step are presented. Experimental results illustrate the significant gains realized by the algorithms compared with commonly used supports.
A sequential approximation framework for coded distributed optimization

Building on the previous work of Lee et al.  and Ferdinand et al.  on coded computation, we propose a sequential approximation framework for solving optimization problems in a distributed manner. In a distributed computation system, latency caused by individual processors (“stragglers”) usually causes a significant delay in the overall process. The proposed method is powered by a sequential computation scheme, which is designed specifically for systems with stragglers. This scheme has the desirable property that the user is guaranteed to receive useful (approximate) computation results whenever a processor finishes its subtask, even in the presence of uncertain latency. In this paper, we give a coding theorem for sequentially computing matrix-vector multiplications, and the optimality of this coding scheme is also established. As an application of the results, we demonstrate solving optimization problems using a sequential approximation approach, which accelerates the algorithm in a distributed system with stragglers.
Deterministic algorithm for the cooperative data exchange problem

In this paper we study the problem of data exchange, where each node in the system has a number of linear combinations of the data packets. Communicating over a public channel, the goal is for all nodes to reconstruct the entire set of the data packets in minimal total number of bits exchanged over the channel. We present a novel divide and conquer based architecture that determines the number of bits each node should transmit. This along with the well known fact, that it is sufficient for the nodes to broadcast linear combinations of their local information, provides a polynomial time deterministic algorithm for reconstructing the entire set of the data packets at all nodes in minimal amount of total communication.
A low-complexity region-based video coder using backward morphological motion field segmentation

We introduce a novel region-based video compression framework based on morphology to efficiently capture motion correspondences between consecutive frames in an image sequence. Our coder is built on the observation that the motion field associated with typical image sequences can be segmented into component motion subfield "clusters" associated with distinct objects or regions in the scene, and further, that these clusters can be efficiently captured using morphological operators in a "backward" framework that avoids the need to send region shape information. Region segmentation is performed directly on the motion field by introducing a small "core" for each cluster that captures the essential features of the cluster and reliably represents its motion behavior. Cluster matching is used in lieu of the conventional block matching methods of standard video coders to define a cluster motion representation paradigm. Furthermore, a region-based pel-recursive approach is applied to find the refinement motion field for each cluster and the cluster motion prediction error image is coded by a novel adaptive scalar quantization method. Experimental results reveal a 10-20% reduction in prediction error energy and 1-3 dB gain in the final reconstructed peak signal-to-noise ratio (PSNR) over the standard MPEG-1 coder at typical bit rates of 500 Kb/s to 1 Mb/s on standard test sequences, while also requiring lower computational complexity.
Network coding for distributed storage systems

Distributed storage systems provide reliable access to data through redundancy spread over individually unreliable nodes. Application scenarios include data centers, peer-to-peer storage systems, and storage in wireless networks. Storing data using an erasure code, in fragments spread across nodes, requires less redundancy than simple replication for the same level of reliability. However, since fragments must be periodically replaced as nodes fail, a key question is how to generate encoded fragments in a distributed way while transferring as little data as possible across the network. For an erasure coded system, a common practice to repair from a single node failure is for a new node to reconstruct the whole encoded data object to generate just one encoded block. We show that this procedure is sub-optimal. We introduce the notion of regenerating codes, which allow a new node to communicate functions of the stored data from the surviving nodes. We show that regenerating codes can significantly reduce the repair bandwidth. Further, we show that there is a fundamental tradeoff between storage and repair bandwidth which we theoretically characterize using flow arguments on an appropriately constructed graph. By invoking constructive results in network coding, we introduce regenerating codes that can achieve any point in this optimal tradeoff.
A compression algorithm using mis-aligned side-information

We study the problem of compressing a source sequence in the presence of side-information that is related to the source via insertions, deletions and substitutions. We propose a simple algorithm to compress the source sequence when the side-information is present at both the encoder and decoder. A key attribute of the algorithm is that it encodes the edits contained in runs of different extents separately. For small insertion and deletion probabilities, the compression rate of the algorithm is shown to be asymptotically optimal.
Robust predictive quantization: a new analysis and optimization framework

This work is focused on computing-via a deterministic optimization with linear matrix inequality (LMI) constraints, rather than a pseudorandom simulation-the performance of predictive quantization schemes under various scenarios for loss and degradation of encoded prediction error samples. The ability to make this computation then allows for the optimization of prediction filters with the aim of minimizing overall mean squared error (including the effects of losses) rather than to minimize the variance of the unquantized prediction error sequence. The main tools are recent characterizations of asymptotic state estimation error covariance and output estimation error variance in terms of LMIs. These characterizations apply to discrete-time jump linear systems in which the discrete portion of the system state is a Markov chain. Translating to the signal processing terminology, this means that the signal model is "piecewise ARMA," as is standard in many forms of speech processing.
Cognitive Radio Through Primary Control Feedback

A fundamental problem in dynamic frequency reuse is that the cognitive radio is ignorant of the amount of interference it inflicts on the primary license holder. Policies that attempt to limit interference without the active participation of the primary are thus difficult to implement. However, many wireless systems use flow control feedback such as ARQs. By listening to these control signals, a cognitive radio can obtain indirect information about the interference it generates and thus behave in an acceptable manner. This paper introduces an information-theoretic model of this basic observation and develops and analyzes algorithms that can exploit it. In particular, a simple generic strategy is proposed where the cognitive radio monitors the primary's effective packet rate and only transmits when that rate is above a threshold. The strategy is shown to have important universality properties with respect to unknown time-varying interference characteristics as well as favorable delay properties.
Nonlinear constrained least squares estimation to reduce artifacts in block transform-coded images

This paper introduces a novel estimation scheme for reducing blocking artifacts in highly compressed, block-transformed images, such as those in JPEG or MPEG. We tackle the blockiness problem by performing constrained least squares (CLS) in the transform domain. Although the CLS approach has been addressed in previous work, we introduce a different approach with many desirable properties, including simple nonlinear processing to protect edges, efficient characterization of blockiness, and fast convergence. Using this new approach, we have obtained significant objective PSNR improvement over previous CLS work. Perceptually, we find significantly reduced blockiness by estimating only a few key transform coefficients per block, giving good visual quality with quick estimation.
High capacity audio data hiding for noisy channels

We combine theoretical and algorithmic advances in the area of information-hiding with the current mature knowledge-base in the human audio perception system to propose a novel audio data hiding technique that significantly pushes the state-of-the-art in the field. Our work is based on a combination of advances in two disjoint fields: information hiding and human auditory masking. The field of information hiding has seen a resurgence due to advances in the understanding of fundamental bounds from information theory. By integrating this with the human perceptual system knowledge that has been successfully exploited for several years in the audio compression community, we derive a new and improved audio data hiding technique that finds application in a number of exciting scenarios like music enhancement and digital communications over analog data channels. Our preliminary results show that we can embed data at an order of magnitude higher rate than existing audio data hiding systems, while being robust to channel noise.
Robust Distributed Multiview Video Compression for Wireless Camera Networks

We present a novel framework for robustly delivering video data from distributed wireless camera networks that are characterized by packet drops. The main focus in this work is on robustness which is imminently needed in a wireless setting. We propose two alternative models to capture interview correlation among cameras with overlapping views. The view-synthesis-based correlation model requires at least two other camera views and relies on both disparity estimation and view interpolation. The disparity-based correlation model requires only one other camera view and makes use of epipolar geometry. With the proposed models, we show how interview correlation can be exploited for robustness through the use of distributed source coding. The proposed approach has low encoding complexity, is robust while satisfying tight latency constraints and requires no intercamera communication. Our experiments show that on bursty packet erasure channels, the proposed H.263+1 based method outperforms baseline methods such as H.263+ with forward error correction and H.263+ with intra refresh by up to 2.5 dB. Empirical results further support the relative insensitivity of our proposed approach to the number of additional available camera views or their placement density.
Density evolution on a class of smeared random graphs

We introduce a new ensemble of random bipartite graphs, which we term the ‘smearing ensemble’, where each left node is connected to some number of consecutive right nodes. Such graphs arise naturally in recovering sparse wavelet coefficients when signal acquisition is in the Fourier domain, such as in magnetic resonance imaging (MRI). Graphs from this ensemble exhibit small, structured cycles with high probability, rendering current techniques for determining iterative decoding thresholds inapplicable. In this paper, we develop a theoretical platform to analyze and evaluate the power of smearing-based structure. Despite the existence of these small cycles, we derive exact density evolution recurrences for iterative decoding on graphs with smear-length two. Furthermore, we give lower bounds on the performance of a much larger class from the smearing ensemble, and provide numerical experiments showing tight agreement between empirical thresholds and those determined by our bounds. We additionally detail a system architecture to recover sparse wavelet representations in the MRI setting, and show that K-sparse 1-stage Haar wavelet coefficients of an n-dimensional signal can be recovered using 2.63K Fourier domain samples asymptotically using O(K log K) operations.
n-channel symmetric multiple descriptions: new rate regions

A new achievable region for the symmetric n-channel multiple descriptions (MD) problem (n>2) is presented. This is derived from our recent result for the problem of information theoretic characterization of maximum distance separable erasure codes in a source-channel coding framework. The rate region presented here is a generalization of the ElGamal and Cover region for the case of n=2 descriptions and achieves points that have not been known in the literature previously.
Private Stream Search at the same communication cost as a regular search: Role of LDPC codes

Private Stream Search allows users to perform keyword-based queries to a database without revealing any information about the keywords they are searching. Using homomorphic encryption, Ostrovsky and Skeith proposed a computationally secure solution to this problem in 2005. However, their solution requires the server to send an answer of size O(mS log m) bits when m documents of S bits match the query, while a non-private query only requires mS bits. In this work we propose two new communication optimal constructions, both allowing a communication expansion factor (compared to a non-private query) asymptotically equal to 1 when m and S increase. More precisely, our first scheme requires m(S + O(log t)) bits (where t is the size of the database) and our second scheme m(S +C) where C is a constant depending on the chosen computational security level.
On the optimality of block orthogonal transforms for multiple description coding of Gaussian vector sources

In this work, we consider the application of unitary filter banks for multiple description coding of independent, identically distributed Gaussian vector sources. We derive the redundancy-rate-distortion bound for this class of signals. It is shown that for two-dimensional (2-D) Gaussian vector sources (resulting in a two-description system), 2/spl times/2 block transforms give all the achievable optimal points in the redundancy-rate-distortion function among the class of all unitary filter banks. Similar results can be obtained for higher-dimensional transforms.
VSYNC: Bandwidth-Efficient and Distortion-Tolerant Video File Synchronization

We introduce video-sync (VSYNC), a video file synchronization system that efficiently uses a bidirectional communications link to maintain up-to-date video sources at remote ends to a desired resolution and distortion level. By automatically detecting and transmitting only the differences between video files, VSYNC is able to avoid unnecessary re-transmission of the entire video when there are only minor differences between video copies. A hierarchical hashing scheme is designed to allow synchronization to within some user-defined distortion, white being rate-efficient and computationally tractable. Distributed video coding is used to realize further rate savings when transmitting video updates. VSYNC is bandwidth-efficient and is useful in many scenarios including video backup, video sharing, and video authentication applications. Experimental results show that rate-savings ranging from 2× to 10× can be obtained by VSYNC with about 10% of the frames being edited, compared to re- transmitting the compressed video or using a file synchronization utility such as rsync.
Design and analysis of a forward-adaptive wavelet image coder

We introduce a new wavelet image coder which is the forward-adaptive counterpart of the state-of-the-art backward-adaptive estimation-quantization coder. The variance field associated with the wavelet coefficients is estimated, lossily compressed, and transmitted as side information. Next, the wavelet coefficients are compressed using that side information. We optimize the resulting two-part coder based on an information-theoretic analysis. The performance of the forward-and backward-adaptive compression algorithms is compared based on several numerical experiments.
Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions

Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any arbitrary k of n nodes. However regenerating codes possess in addition, the ability to repair a failed node by connecting to any arbitrary d nodes and downloading an amount of data that is typically far less than the size of the data file. This amount of download is termed the repair bandwidth. Minimum storage regenerating (MSR) codes are a subclass of regenerating codes that require the least amount of network storage; every such code is a maximum distance separable (MDS) code. Further, when a replacement node stores data identical to that in the failed node, the repair is termed as exact. The four principal results of the paper are (a) the explicit construction of a class of MDS codes for d = n - 1 ≥ 2k - 1 termed the MISER code, that achieves the cut-set bound on the repair bandwidth for the exact repair of systematic nodes, (b) proof of the necessity of interference alignment in exact-repair MSR codes, (c) a proof showing the impossibility of constructing linear, exact-repair MSR codes for d <; 2k - 3 in the absence of symbol extension, and (d) the construction, also explicit, of high-rate MSR codes for d = k + 1. Interference alignment (IA) is a theme that runs throughout the paper: the MISER code is built on the principles of IA and IA is also a crucial component to the nonexistence proof for d <; 2k - 3. To the best of our knowledge, the constructions presented in this paper are the first explicit constructions of regenerating codes that achieve the cut-set bound.
Computationally-efficient blind sub-Nyquist sampling for sparse spectra

The sampling of spectrally sparse high-bandwidth signals below the Nyquist rate is of importance in many applications. In order to keep the front-end analog-to-digital converter sampling rate low, there has been a lot of recent interest in the literature to develop efficient and practical architectures for low-rate sampling and recovery of spectrally sparse signals. Our main contribution is a simple, implementation-friendly front-end sampling-architecture and a computationally efficient back-end algorithm for blind sub-Nyquist sampling of a class of band-limited sparse signals. In particular, we show that signals band-limited to W Hz consisting of k tones can be reliably recovered from sets of uniform samples obtained at a rate 4k Hz for asymptotic values of k and W, when k is sub-linear in W for noiseless observations of the signal. Further, the proposed reconstruction algorithm is computationally efficient, requiring only O(k log k) computations to recover the sinusoidal components. Our algorithm succeeds with high probability, with the probability of failure vanishing to zero asymptotically in the number of samples acquired. We provide simulation results that corroborate our theoretical findings, and also analyze the noise-robustness of the system.
Efficient terrain data representation for 3D rendering using the generalized BFOS algorithm

Digital terrain data has widespread applications in areas such as the military, geographic information systems (GIS), and flight simulator video games. The combination of the abundance of terrain data with the limited rendering capabilities of computer graphics machines creates the necessity for algorithms which generate efficient representations of the data for rendering. This paper presents such an algorithm. Terrain data is tessellated using a regular triangular grid, and the regular grid is represented using a binary tree. The generalized BFOS algorithm, a well-known optimal tree-pruning method for regression and quantization trees, is used to prune the tree optimally, resulting in a far more efficient representation of this data than known in the literature. In addition to its optimal properties, the representation is also embedded, making it suitable for displays at multiple resolutions.