We consider an assortment selection and pricing problem in which a seller has $N$ different items available for sale. In each round, the seller observes a $d$-dimensional contextual preference information vector for the user, and offers to the user an assortment of $K$ items at prices chosen by the seller. The user selects at most one of the products from the offered assortment according to a multinomial logit choice model whose parameters are unknown. The seller observes which, if any, item is chosen at the end of each round, with the goal of maximizing cumulative revenue over a selling horizon of length $T$. For this problem, we propose an algorithm that learns from user feedback and achieves a revenue regret of order $\widetilde{\mathcal{O}}(d \sqrt{K T} / L_0 )$ where $L_0$ is the minimum price sensitivity parameter. We also obtain a lower bound of order $\Omega(d \sqrt{T}/ L_0)$ for the regret achievable by any algorithm.

Recent work has shown that Transformers trained from scratch can successfully solve various arithmetic and algorithmic tasks, such as adding numbers and computing parity. While these Transformers generalize well on unseen inputs of the same length, they struggle with length generalization, i.e., handling inputs of unseen lengths. In this work, we demonstrate that looped Transformers with an adaptive number of steps significantly improve length generalization. We focus on tasks with a known iterative solution, involving multiple iterations of a RASP-L operation—a length-generalizable operation that can be expressed by a finite-sized Transformer. We train looped Transformers using our proposed learning algorithm and observe that they learn highly length-generalizable solutions for various tasks.

With hundreds of thousands of language models available on Huggingface today, efficiently evaluating and utilizing these models across various downstream tasks has become increasingly critical. Many existing methods repeatedly learn task-specific representations of Large Language Models (LLMs), which leads to inefficiencies in both time and computational resources. To address this, we propose EmbedLLM, a framework designed to learn compact vector representations of LLMs that facilitate downstream applications involving many models, such as model routing. We introduce an encoder-decoder approach for learning such embedding, along with a systematic framework to evaluate their effectiveness. Empirical results show that EmbedLLM outperforms prior methods in model routing. Additionally, we demonstrate that our method can forecast a model's performance on multiple benchmarks, without incurring additional inference cost. Extensive probing experiments validate that the learned embeddings capture key model characteristics, e.g. whether the model is specialized for coding tasks, even without being explicitly trained on them. We open source our dataset, code and embedder to facilitate further research and application.

Process Reward Models (PRMs) have proven effective at enhancing mathematical reasoning for Large Language Models (LLMs) by leveraging increased inference-time computation. However, they are predominantly trained on mathematical data and their generalizability to non-mathematical domains has not been rigorously studied. In response, this work first shows that current PRMs have poor performance in other domains. To address this limitation, we introduce ***VersaPRM***, a multi-domain PRM trained on synthetic reasoning data generated using our novel data generation and annotation method. VersaPRM achieves consistent performance gains across diverse domains. For instance, in the MMLU-Pro category of Law, VersaPRM via weighted majority voting, achieves a 7.9% performance gain over the majority voting baseline–surpassing Qwen2.5-Math-PRM's gain of 1.3%. We further contribute to the community by open-sourcing all data, code and models for VersaPRM.

Large language models (LLMs) have revolutionized machine learning due to their ability to capture complex interactions between input features. Popular post-hoc explanation methods like SHAP provide marginal feature attributions, while their extensions to interaction importances only scale to small input lengths ($\approx 20$). We propose Spectral Explainer (SPEX), a model-agnostic interaction attribution algorithm that efficiently scales to large input lengths ($\approx 1000)$. SPEX exploits underlying natural sparsity among interactions—common in real-world data—and applies a sparse Fourier transform using a channel decoding algorithm to efficiently identify important interactions. We perform experiments across three difficult long-context datasets that require LLMs to utilize interactions between inputs to complete the task. For large inputs, SPEX outperforms marginal attribution methods by up to 20% in terms of faithfully reconstructing LLM outputs. Further, SPEX successfully identifies key features and interactions that strongly influence model output. For one of our datasets, HotpotQA, SPEX provides interactions that align with human annotations. Finally, we use our model-agnostic approach to generate explanations to demonstrate abstract reasoning in closed-source LLMs (GPT-4o mini) and compositional reasoning in vision-language models.

Large Language Models (LLMs) have achieved remarkable performance by capturing complex interactions between input features. To identify these interactions, most existing approaches require enumerating all possible combinations of features up to a given order, causing them to scale poorly with the number of inputs $n$. Recently, Kang et al. (2025) proposed SPEX, an information-theoretic approach that uses interaction sparsity to scale to $n \approx 10^3$ features. SPEX greatly improves upon prior methods but requires tens of thousands of model inferences, which can be prohibitive for large models. In this paper, we observe that LLM feature interactions are often *hierarchical*—higher-order interactions are accompanied by their lower-order subsets—which enables more efficient discovery. To exploit this hierarchy, we propose ProxySPEX, an interaction attribution algorithm that first fits gradient boosted trees to masked LLM outputs and then extracts the important interactions. Experiments across four challenging high-dimensional datasets show that ProxySPEX more faithfully reconstructs LLM outputs by 20\% over marginal attribution approaches while using *$10\times$ fewer inferences* than SPEX. By accounting for interactions, ProxySPEX efficiently identifies the most influential features, providing a scalable approximation of their Shapley values. Further, we apply ProxySPEX to two interpretability tasks. *Data attribution*, where we identify interactions among CIFAR-10 training samples that influence test predictions, and *mechanistic interpretability*, where we uncover interactions between attention heads, both within and across layers, on a question-answering task. The ProxySPEX algorithm is available at <https://github.com/mmschlk/shapiq>.

Despite enthusiasm for Multi-Agent LLM Systems (MAS), their performance gains on popular benchmarks are often minimal. This gap highlights a critical need for a principled understanding of why MAS fail. Addressing this question requires systematic identification and analysis of failure patterns. We introduce MAST-Data, a comprehensive dataset of 1600+ annotated traces collected across 7 popular MAS frameworks. MAST-Data is the first multi-agent system dataset to outline the failure dynamics in MAS for guiding the development of better future systems. To enable systematic classification of failures for MAST-Data, we build the first Multi-Agent System Failure Taxonomy (MAST). We develop MAST through rigorous analysis of 150 traces, guided closely by expert human annotators andvalidated by high inter-annotator agreement (κ = 0.88). This process identifies 14 unique modes, clustered into 3 categories: (i) system design issues, (ii) inter-agent misalignment, and (iii) task verification. To enable scalable annotation, we develop an LLM-as-a-Judge pipeline with high agreement with human annotations. We leverage MAST and MAST-Data to analyze failure patterns across models (GPT4, Claude 3, Qwen2.5, CodeLlama) and tasks (coding, math, general agent), demonstrating improvement headrooms from better MAS design. Our analysis provides insights revealing that identified failures require more sophisticated solutions, highlighting a clear roadmap for future research. We publicly release our comprehensive dataset (MAST-Data), the MAST, and our LLM annotator to facilitate widespread research and development in MAS.

One of the key challenges in machine learning is to find interpretable representations of learned functions. The Möbius transform is essential for this purpose, as its coefficients correspond to unique *importance scores* for *sets of input variables*. This transform is closely related to widely used game-theoretic notions of importance like the *Shapley* and *Bhanzaf value*, but it also captures crucial higher-order interactions. Although computing the Möbius Transform of a function with $n$ inputs involves $2^n$ coefficients, it becomes tractable when the function is *sparse* and of *low-degree* as we show is the case for many real-world functions. Under these conditions, the complexity of the transform computation is significantly reduced. When there are $K$ non-zero coefficients, our algorithm recovers the Möbius transform in $O(Kn)$ samples and $O(Kn^2)$ time asymptotically under certain assumptions, the first non-adaptive algorithm to do so. We also uncover a surprising connection between group testing and the Möbius transform. For functions where all interactions involve at most $t$ inputs, we use group testing results to compute the Möbius transform with $O(Kt\log n)$ sample complexity and $O(K\mathrm{poly}(n))$ time. A robust version of this algorithm withstands noise and maintains this complexity. This marks the first $n$ sub-linear query complexity, noise-tolerant algorithm for the Möbius transform. While our algorithms are conceptualized in an idealized setting, they indicate that the Möbius transform is a potent tool for interpreting deep learning models.

Attention-based transformers have been remarkably successful at modeling generative processes across various domains and modalities. In this paper, we study the behavior of transformers on data drawn from $k^{\text{th}}$-order Markov processes, where the conditional distribution of the next symbol in a sequence depends on the previous $k$ symbols observed. We observe a surprising phenomenon empirically which contradicts previous findings: when trained for sufficiently long, a transformer with a fixed depth and $1$ head per layer is able to achieve low test loss on sequences drawn from $k^{\text{th}}$-order Markov sources, even as $k$ grows. Furthermore, this low test loss is achieved by the transformer’s ability to represent and learn the in-context conditional empirical distribution. On the theoretical side, we prove that a transformer with $O(\log_2(k))$ layers can represent the in-context conditional empirical distribution by composing induction heads to track the previous $k$ symbols in the sequence. Surprisingly, with the addition of layer normalization, we show that a transformer with a constant number of layers can represent the in-context conditional empirical distribution, concurring with our empirical observations. This result provides more insight into the benefit of soft-attention and non-linearities in the transformer architecture.

While there has been a large body of research attempting to circumvent tokenization for language modeling (Clark et al. 2022, Xue et al. 2022), the current consensus is that it is a necessary initial step for designing state-of-the-art performant language models. In this paper, we investigate tokenization from a theoretical point of view by studying the behavior of transformers on simple data generating processes. When trained on data drawn from certain simple $k^{\text{th}}$-order Markov processes for $k > 1$, transformers exhibit a surprising phenomenon - in the absence of tokenization, they empirically are incredibly slow or fail to learn the right distribution and predict characters according to a unigram model (Makkuva et al. 2024). With the addition of tokenization, however, we empirically observe that transformers break through this barrier and are able to model the probabilities of sequences drawn from the source near-optimally, achieving small cross-entropy loss. With this observation as starting point, we study the end-to-end cross-entropy loss achieved by transformers with and without tokenization. With the appropriate tokenization, we show that even the simplest unigram models (over tokens) learnt by transformers are able to model the probability of sequences drawn from $k^{\text{th}}$-order Markov sources near optimally. Our analysis provides a justification for the use of tokenization in practice through studying the behavior of transformers on Markovian data.

We consider the problem of model selection for the general stochastic contextual bandits under the realizability assumption. We propose a successive refinement based algorithm called Adaptive Contextual Bandit (ACB), that works in phases and successively eliminates model classes that are too simple to fit the given instance. We prove that this algorithm is adaptive, i.e., the regret rate order-wise matches that of any provable contextual bandit algorithm, that needs the knowledge of the true model class. The price of not knowing the correct model class turns out to be only an additive term contributing to the second order term in the regret bound. This cost possess the intuitive property that it becomes smaller as the model class becomes easier to identify, and vice-versa. We also show that a much simpler explore-then-commit (ETC) style algorithm also obtains similar regret bound, despite not knowing the true model class. However, the cost of model selection is higher in ETC as opposed to inACB, as expected. Furthermore, for the special case of linear contextual bandits, we propose specialized algorithms that obtain sharper guarantees compared to the generic setup.

Understanding complex dynamics of two-sided online matching markets, where the demand-side agents compete to match with the supply-side (arms), has recently received substantial interest. To that end, in this paper, we introduce the framework of decentralized two-sided matching market under non stationary (dynamic) environments. We adhere to the serial dictatorship setting, where the demand-side agents have unknown and different preferences over the supply-side (arms), but the arms have fixed and known preference over the agents. We propose and analyze an asynchronous and decentralized learning algorithm, namely Non-Stationary Competing Bandits (NSCB), where the agents play (restrictive) successive elimination type learning algorithms to learn their preference over the arms. The complexity in understanding such a system stems from the fact that the competing bandits choose their actions in an asynchronous fashion, and the lower ranked agents only get to learn from a set of arms, not dominated by the higher ranked agents, which leads toforced exploration. With carefully defined complexity parameters, we characterize thisforced explorationand obtain sub-linear (logarithmic) regret of NSCB. Furthermore, we validate our theoretical findings via experiments.

Large-scale online recommendation systems must facilitate the allocation of a limited number of items among competing users while learning their preferences from user feedback. As a principled way of incorporating market constraints and user incentives in the design, we consider our objectives to be two-fold: maximal social welfare with minimal instability. To maximize social welfare, our proposed framework enhances the quality of recommendations by exploring allocations that optimistically maximize the rewards. To minimize instability, a measure of users’ incentives to deviate from recommended allocations, the algorithm prices the items based on a scheme derived from the Walrasian equilibria. Though it is known that these equilibria yield stable prices for markets with known user preferences, our approach accounts for the inherent uncertainty in the preferences and further ensures that the users accept most of their recommendations under offered prices. To the best of our knowledge, our approach is the first to integrate techniques from combinatorial bandits, optimal resource allocation, and collaborative filtering to obtain an algorithm that achieves sub-linear social welfare regret as well as sub-linear instability. Empirical studies on synthetic and real-world data also demonstrate the efficacy of our strategy compared to approaches that do not fully incorporate all these aspects.

Fourier transformations of pseudo-Boolean functions are popular tools for analyzing functions of binary sequences. Real-world functions often have structures that manifest in a sparse Fourier transform, and previous works have shown that under the assumption of sparsity the transform can be computed efficiently. But what if we want to compute the Fourier transform of functions defined over a q-ary alphabet? These types of functions arise naturally in many areas including biology. A typical workaround is to encode the q-ary sequence in binary however, this approach is computationally inefficient and fundamentally incompatible with the existing sparse Fourier transform techniques. Herein, we develop a sparse Fourier transform algorithm specifically for q-ary functions of length n sequences, dubbed q-SFT, which provably computes an S-sparse transform with vanishing error as qn→ ∞ in O(Sn) function evaluations and O(Sn2log q) computations, where S = qnδfor some δ2) and a computational complexity of O(Sn3) with the same asymptotic guarantees. We present numerical simulations on synthetic and real-world RNA data, demonstrating the scalability of q-SFT to massively high dimensional q-ary functions.

Selecting suitable architecture parameters and training hyperparameters is essential for enhancing machine learning (ML) model performance. Several recent empirical studies conduct large-scale correlational analysis on neural networks (NNs) to search for effective generalization metrics that can guide this type of model selection. Effective metrics are typically expected to correlate strongly with test performance. In this paper, we expand on prior analyses by examining generalization-metric-based model selection with the following objectives: (i) focusing on natural language processing (NLP) tasks, as prior work primarily concentrates on computer vision (CV) tasks; (ii) considering metrics that directly predict test error instead of the generalization gap; (iii) exploring metrics that do not need access to data to compute. From these objectives, we are able to provide the first model selection results on large pretrained Transformers from Huggingface using generalization metrics. Our analyses consider (I) hundreds of Transformers trained in different settings, in which we systematically vary the amount of data, the model size and the optimization hyperparameters, (II) a total of 51 pretrained Transformers from eight families of Huggingface NLP models, including GPT2, BERT, etc., and (III) a total of 28 existing and novel generalization metrics. Despite their niche status, we find that metrics derived from the heavy-tail (HT) perspective are particularly useful in NLP tasks, exhibiting stronger correlations than other, more popular metrics. To further examine these metrics, we extend prior formulations relying on power law (PL) spectral distributions to exponential (EXP) and exponentially-truncated power law (E-TPL) families.

Online pricing has been the focus of extensive research in recent years, particularly in the context of selling an item to sequentially arriving users. However, what if a provider wants to maximize revenue by selling multiple items to multiple users in each round? This presents a complex problem, as the provider must intelligently offer the items to those users who value them the most without exceeding their highest acceptable prices. In this study, we tackle this challenge by designing online algorithms that can efficiently offer and price items while learning user valuations from accept/reject feedback. We focus on three user valuation models (fixed valuations, random experiences, and random valuations) and provide algorithms with nearly-optimal revenue regret guarantees. In particular, for any market setting with $N$ users, $M$ items, and load $L$ (which roughly corresponds to the maximum number of simultaneous allocations possible), our algorithms achieve regret of order $O(NM\log\log(LT))$ under fixed valuations model, $\widetilde{O}(\sqrt{NMLT})$ under random experiences model and $\widetilde{O}(\sqrt{NMLT})$ under random valuations model in $T$ rounds.

A conditional generative model is a method for sampling from a conditional distribution $p(y \mid x)$. For example, one may want to sample an image of a cat given the label ``cat''. A feed-forward conditional generative model is a function $g(x, z)$ that takes the input $x$ and a random seed $z$, and outputs a sample $y$ from $p(y \mid x)$. Ideally the distribution of outputs $(x, g(x, z))$ would be close in total variation to the ideal distribution $(x, y)$. Generalization bounds for other learning models require assumptions on the distribution of $x$, even in simple settings like linear regression with Gaussian noise. We show these assumptions are unnecessary in our model, for both linear regression and single-layer ReLU networks. Given samples $(x, y)$, we show how to learn a 1-layer ReLU conditional generative model in total variation. As our result has no assumption on the distribution of inputs $x$, if we are given access to the internal activations of a deep generative model, we can compose our 1-layer guarantee to progressively learn the deep model using a near-linear number of samples.

Pruning schemes have been widely used in practice to reduce the complexity of trained models with a massive number of parameters. In fact, several practical studies have shown that if the pruned model is fine-tuned with some gradient-based updates it generalizes well to new samples. Although the above pipeline, which we refer to as pruning + fine-tuning, has been extremely successful in lowering the complexity of trained models, there is very little known about the theory behind this success. In this paper we address this issue by investigating the pruning + fine-tuning framework on the overparameterized matrix sensing problem with the ground truth denoted $U_\star \in \mathbb{R}^{d \times r}$ and the overparameterized model $U \in \mathbb{R}^{d \times k}$ with $k \gg r$. We study the approximate local minima of the mean square error, augmented with a smooth version of a group Lasso regularizer, $\sum_{i=1}^{k} \lVert Ue_i \rVert_2 $. In particular, we provably show that pruning all the columns below a certain explicit $\ell_2$-norm threshold results in a solution $U_{\text{prune}}$ which has the minimum number of columns $r$, yet close to the ground truth in training loss. Moreover, in the subsequent fine-tuning phase, gradient descent initialized at $U_{\text{prune}}$ converges at a linear rate to its limit. While our analysis provides insights into the role of regularization in pruning, we also show that running gradient descent in the absence of regularization results in models which {are not suitable for greedy pruning}, i.e., many columns could have their $\ell_2$ norm comparable to that of the maximum. Lastly, we show that our results also extend for the training and pruning of two-layer neural networks with quadratic activation functions. To the best of our knowledge, our results provide the first rigorous insights on why greedy pruning + fine-tuning leads to smaller models which also generalize well.

Federated learning (FL) systems have an inherent vulnerability to adversarial backdoor attacks during training due to their decentralized nature. The goal of the attacker is to implant backdoors in the learned model with poisoned updates such that at test time, the model’s outputs can be fixed to a given target for certain inputs (e.g., if a user types “people from New York” into a mobile keyboard app that uses a backdoored next word prediction model, the model will autocomplete their sentence to “people in New York are rude”). Prior work has shown that backdoors can be inserted in FL, but these backdoors are not durable: they do not remain in the model after the attacker stops uploading poisoned updates because training continues, and in production FL systems an inserted backdoor may not survive until deployment. We propose Neurotoxin, a simple one-line backdoor attack that functions by attacking parameters that are changed less in magnitude during training. We conduct an exhaustive evaluation across ten natural language processing and computer vision tasks and find that we can double the durability of state of the art backdoors by adding a single line with Neurotoxin.

Online imitation learning is the problem of how best to mimic expert demonstrations, given access to the environment or an accurate simulator. Prior work has shown that in the \textit{infinite} sample regime, exact moment matching achieves value equivalence to the expert policy. However, in the \textit{finite} sample regime, even if one has no optimization error, empirical variance can lead to a performance gap that scales with $H^2 / N_{\text{exp}}$ for behavioral cloning and $H / N_{\text{exp}}$ for online moment matching, where $H$ is the horizon and $N_{\text{exp}}$ is the size of the expert dataset. We introduce the technique of ``replay estimation'' to reduce this empirical variance: by repeatedly executing cached expert actions in a stochastic simulator, we compute a smoother expert visitation distribution estimate to match. In the presence of general function approximation, we prove a meta theorem reducing the performance gap of our approach to the \textit{parameter estimation error} for offline classification (i.e. learning the expert policy). In the tabular setting or with linear function approximation, our meta theorem shows that the performance gap incurred by our approach achieves the optimal $\widetilde{O} \left( \min( H^{3/2} / N_{\text{exp}}, H / \sqrt{N_{\text{exp}}} \right)$ dependency, under significantly weaker assumptions compared to prior work. We implement multiple instantiations of our approach on several continuous control tasks and find that we are able to significantly improve policy performance across a variety of dataset sizes.

We address the problem of federated learning (FL) where users are distributed and partitioned into clusters. This setup captures settings where different groups of users have their own objectives (learning tasks) but by aggregating their data with others in the same cluster (same learning task), they can leverage the strength in numbers in order to perform more efficient federated learning. For this new framework of clustered federated learning, we propose the Iterative Federated Clustering Algorithm (IFCA), which alternately estimates the cluster identities of the users and optimizes model parameters for the user clusters via gradient descent. We analyze the convergence rate of this algorithm first in a linear model with squared loss and then for generic strongly convex and smooth loss functions. We show that in both settings, with good initialization, IFCA is guaranteed to converge, and discuss the optimality of the statistical error rate. In particular, for the linear model with two clusters, we can guarantee that our algorithm converges as long as the initialization is slightly better than random. When the clustering structure is ambiguous, we propose to train the models by combining IFCA with the weight sharing technique in multi-task learning. In the experiments, we show that our algorithm can succeed even if we relax the requirements on initialization with random initialization and multiple restarts. We also present experimental results showing that our algorithm is efficient in non-convex problems such as neural networks. We demonstrate the benefits of IFCA over the baselines on several clustered FL benchmarks.

Max-affine regression refers to a model where the unknown regression function is modeled as a maximum of$k$unknown affine functions for a fixed$k \geq 1$. This generalizes linear regression and (real) phase retrieval, and is closely related to convex regression. We study this problem in the high-dimensional setting assuming that$k$is a fixed constant, and focus on the estimation of the unknown coefficients of the affine functions underlying the model. We analyze a natural alternating minimization (AM) algorithm for the non-convex least squares objective when the design is Gaussian. We show that the AM algorithm, when initialized suitably, converges with high probability and at a geometric rate to a small ball around the optimal coefficients. In order to initialize the algorithm, we propose and analyze a combination of a spectral method and a search algorithm in a low-dimensional space, which may be of independent interest. The final rate that we obtain is near-parametric and minimax optimal (up to a polylogarithmic factor) as a function of the dimension, sample size, and noise variance. In that sense, our approach should be viewed as adirectand implementable method of enforcing regularization to alleviate the curse of dimensionality in problems of the convex regression type. Numerical experiments illustrate the sharpness of our bounds in the various problem parameters.

In the above article[1], we introduced two scheduling policies and analyzed their average job latencies. With an implicit assumption that the scheduling policies provide sample-path bounds by construction, we claimed that their average job latencies serve as upper and lower bounds on that of a centralized MDS queue. In this note, we present recently discovered counterexamples, disproving the assumption. We replace the assumption with a conjecture that the average latency bounds still hold. We also provide an erratum to the original article to correct any confusing or misleading statements.

We consider the problem of model selection for two popular stochastic linear bandit settings, and propose algorithms that adapts to the unknown problem complexity. In the first setting, we consider the $K$ armed mixture bandits, where the mean reward of arm $i \in [K]$ is $\mu_i+ ⟨\alpha_{i,t},\theta^* ⟩$, with $\alpha_{i,t} \in \mathbb{R}^d$ being the known context vector and $\mu_i \in [-1,1]$ and $\theta^*$ are unknown parameters. We define $\|\theta^*\|$ as the problem complexity and consider a sequence of nested hypothesis classes, each positing a different upper bound on $\|\theta^*\|$. Exploiting this, we propose Adaptive Linear Bandit (ALB), a novel phase based algorithm that adapts to the true problem complexity, $\|\theta^*\|$. We show that ALB achieves regret scaling of $\widetilde{O}(\|\theta^*\|\sqrt{T})$, where $\|\theta^*\|$ is apriori unknown. As a corollary, when $\theta^*=0$, ALB recovers the minimax regret for the simple bandit algorithm without such knowledge of $\theta^*$. ALB is the first algorithm that uses parameter norm as model section criteria for linear bandits. Prior state of art algorithms achieve a regret of $\widetilde{O}(L\sqrt{T})$, where $L$ is the upper bound on $\|\theta^*\|$, fed as an input to the problem. In the second setting, we consider the standard linear bandit problem (with possibly an infinite number of arms) where the sparsity of $\theta^*$, denoted by $d^* \leq d$, is unknown to the algorithm. Defining $d^*$ as the problem complexity (similar to Foster et. al ’19), we show that ALB achieves $\widetilde{O}(d^*\sqrt{T})$ regret, matching that of an oracle who knew the true sparsity level. This methodology is then extended to the case of finitely many arms and similar results are proven. We further verify through synthetic and real-data experiments that the performance gains are fundamental and not artifacts of mathematical bounds. In particular, we show $1.5-3$x drop in cumulative regret over non-adaptive algorithms.

Federated learning (FL) is a promising way to use the computing power of mobile devices while maintaining the privacy of users. Current work in FL, however, makes the unrealistic assumption that the users have ground-truth labels on their devices, while also assuming that the server has neither data nor labels. In this work, we consider the more realistic scenario where the users have only unlabeled data, while the server has some labeled data, and where the amount of labeled data is smaller than the amount of unlabeled data. We call this learning problem semi-supervised federated learning (SSFL). For SSFL, we demonstrate that a critical issue that affects the test accuracy is the large gradient diversity of the models from different users. Based on this, we investigate several design choices. First, we find that the so-called consistency regularization loss (CRL), which is widely used in semi-supervised learning, performs reasonably well but has large gradient diversity. Second, we find that Batch Normalization (BN) increases gradient diversity. Replacing BN with the recently-proposed Group Normalization (GN) can reduce gradient diversity and improve test accuracy. Third, we show that CRL combined with GN still has a large gradient diversity when the number of users is large. Based on these results, we propose a novel grouping-based model averaging method to replace the FedAvg averaging method. Overall, our grouping-based averaging, combined with GN and CRL, achieves better test accuracy than not just a contemporary paper on SSFL in the same settings (>10%), but also four supervised FL algorithms.

Shamir's secret sharing scheme is widely used in many cryptographic protocols such as secure multi-party computation. It allows a secret to be distributed to$n$parties such that any$t$parties learn no information about the secret, whereas any$t+1$parties can recover the secret. However, the worst-case recovery guarantees come at the price of$O(n^{2})$computation cost. This quadratic cost limits its scalability to applications involving only a small number of participants. This paper presents a framework, called FastShare, for designing secret sharing schemes that ensures worst-case security guarantees at a lower computation cost by relaxing the recovery constraint from worst-case to average-case in a statistical sense. In particular, FastShare considers the setup where each party takes part in the recovery process with some probability$\rho$, independently of others. The core idea of FastShare is to construct a ‘signal’ using the secret and random masks by inserting zeros at judiciously chosen locations, and take its finite field fast Fourier transform (FFT) to generate the shares. We present a scheme designed using FastShare where the judicious zero placement ensures that the shares form a codeword of a locally recoverable code. The locality property along with the FFT allows us to recover the secret with$O(n\log n)$computational complexity, from a ‘random’ subset of shares of large enough size. We analyze its security and recovery thresholds, and characterize a trade-off between$\rho$and the probability of successfully recovering the secret. Further, we carry out numerical simulations to demonstrate the applicability of the proposed scheme for a wide range of values of$n$.

In this paper, we consider hybrid parallelism---a paradigm that employs both Data Parallelism (DP) and Model Parallelism (MP)---to scale distributed training of large recommendation models. We propose a compression framework called Dynamic Communication Thresholding (DCT) for communication-efficient hybrid training. DCT filters the entities to be communicated across the network through a simple hard-thresholding function, allowing only the most relevant information to pass through. For communication efficient DP, DCT compresses the parameter gradients sent to the parameter server during model synchronization. The threshold is updated only once every few thousand iterations to reduce the computational overhead of compression. For communication efficient MP, DCT incorporates a novel technique to compress the activations and gradients sent across the network during the forward and backward propagation, respectively. This is done by identifying and updating only the most relevant neurons of the neural network for each training sample in the data. We evaluate DCT on publicly available natural language processing and recommender models and datasets, as well as recommendation systems used in production at Facebook. DCT reduces communication by at least 100x and 20x during DP and MP, respectively. The algorithm has been deployed in production, and it improves end-to-end training time for a state-of-the-art industrial recommender model by 37%, without any loss in performance.

We study the statistical guarantees for the Imitation Learning (IL) problem in episodic MDPs.Rajaraman et al. (2020) show an information theoretic lower bound that in the worst case, a learner which can even actively query the expert policy suffers from a suboptimality growing quadratically in the length of the horizon, $H$. We study imitation learning under the $\mu$-recoverability assumption of Ross et al. (2011) which assumes that the difference in the $Q$-value under the expert policy across different actions in a state do not deviate beyond $\mu$ from the maximum. We show that the reduction proposed by Ross et al. (2010) is statistically optimal: the resulting algorithm upon interacting with the MDP for $N$ episodes results in a suboptimality bound of $\widetilde{\mathcal{O}} \left( \mu |\mathcal{S}| H / N \right)$ which we show is optimal up to log-factors. In contrast, we show that any algorithm which does not interact with the MDP and uses an offline dataset of $N$ expert trajectories must incur suboptimality growing as $\gtrsim |\mathcal{S}| H^2/N$ even under the $\mu$-recoverability assumption. This establishes a clear and provable separation of the minimax rates between the active setting and the no-interaction setting. We also study IL with linear function approximation. When the expert plays actions according to a linear classifier of known state-action features, we use the reduction to multi-class classification to show that with high probability, the suboptimality of behavior cloning is $\widetilde{O}(dH^2/N)$ given $N$ rollouts from the optimal policy. This is optimal up to log-factors but can be improved to $\widetilde{O}(dH/N)$ if we have a linear expert with parameter-sharing across time steps. In contrast, when the MDP transition structure is known to the learner such as in the case of simulators, we demonstrate fundamental differences compared to the tabular setting in terms of the performance of an optimal algorithm, Mimic-MD (Rajaraman et al. (2020)) when extended to the function approximation setting. Here, we introduce a new problem called confidence set linear classification, that can be used to construct sample-efficient IL algorithms.

Viewing neural network models in terms of their loss landscapes has a long history in the statistical mechanics approach to learning, and in recent years it has received attention within machine learning proper. Among other things, local metrics (such as the smoothness of the loss landscape) have been shown to correlate with global properties of the model (such as good generalization performance). Here, we perform a detailed empirical analysis of the loss landscape structure of thousands of neural network models, systematically varying learning tasks, model architectures, and/or quantity/quality of data. By considering a range of metrics that attempt to capture different aspects of the loss landscape, we demonstrate that the best test accuracy is obtained when: the loss landscape is globally well-connected; ensembles of trained models are more similar to each other; and models converge to locally smooth regions. We also show that globally poorly-connected landscapes can arise when models are small or when they are trained to lower quality data; and that, if the loss landscape is globally poorly-connected, then training to zero loss can actually lead to worse test accuracy. Our detailed empirical results shed light on phases of learning (and consequent double descent behavior), fundamental versus incidental determinants of good generalization, the role of load-like and temperature-like parameters in the learning process, different influences on the loss landscape from model and data, and the relationships between local and global metrics, all topics of recent interest.

To address the communication bottleneck problem in distributed optimization within a master-worker framework, we propose LocalNewton, a distributed second-order algorithm with local averaging. In LocalNewton, the worker machines update their model in every iteration by finding a suitable second-order descent direction using only the data and model stored in their own local memory. We let the workers run multiple such iterations locally and communicate the models to the master node only once every few (say $L$) iterations. LocalNewton is highly practical since it requires only one hyperparameter, the number $L$ of local iterations. We use novel matrix concentration based techniques to obtain theoretical guarantees for LocalNewton, and we validate them with detailed empirical evaluation. To enhance practicability, we devise an adaptive scheme to choose $L$, and we show that this reduces the number of local iterations in worker machines between two model synchronizations as the training proceeds, successively refining the model quality at the master. Via extensive experiments using several real-world datasets with AWS Lambda workers and an AWS EC2 master, we show that LocalNewton requires fewer than $60%$ of the communication rounds (between master and workers) and less than $40%$ of the end-to-end running time, compared to state-of-the-art algorithms, to reach the same training loss.

We address the problem of solving mixed random linear equations. In this problem, we have unlabeled observations coming from multiple linear regressions, and each observation corresponds to exactly one of the regression models. The goal is to learn the linear regressors from the observations. Classically, Alternating Minimization (AM) (which may be thought as a variant of Expectation Maximization (EM)) is used to solve this problem. AM iteratively alternates between the estimation of labels and solving the regression problems with the estimated labels. Empirically, it is observed that, for a large variety of non-convex problems including mixed linear regression, AM converges at a much faster rate compared to gradient based algorithms. However, the existing theory suggests similar rate of convergence, failing to capture this empirical behavior. In this paper, we close this gap between theory and practice for the special case of a mixture of $2$ linear regressions. We show that, provided initialized properly, AM enjoys a \emph{super-linear} rate of convergence. To the best of our knowledge, this is the first work that theoretically establishes such rate for AM. Hence, if we want to recover the unknown regressors upto an error (in $\ell_2$ norm) of $\epsilon$, AM only takes $\mathcal{O}(\log \log (1/\epsilon))$ iterations.

Motivated by recent developments in serverless systems for large-scale computation as well as improvements in scalable randomized matrix algorithms, we develop OverSketched Newton, a randomized Hessian-based optimization algorithm to solve large-scale convex optimization problems in serverless systems. OverSketched Newton leverages matrix sketching ideas from Randomized Numerical Linear Algebra to compute the Hessian approximately. These sketching methods lead to inbuilt resiliency against stragglers that are a characteristic of serverless architectures. Depending on whether or not the problem is strongly convex, we propose different iteration updates using the approximate Hessian. For both cases, we establish convergence guarantees for OverSketched Newton, and we empirically validate our results by solving large-scale supervised learning problems on real-world datasets. Experiments demonstrate a reduction of ~50% in total running time on AWS Lambda, compared to state-of-the-art distributed optimization schemes.

Inexpensive cloud services, such as serverless computing, are often vulnerable to straggling nodes that increase the end-to-end latency for distributed computation. We propose and implement simple yet principled approaches for straggler mitigation in serverless systems for matrix multiplication and evaluate them on several common applications from machine learning and high-performance computing. The proposed schemes are inspired by error-correcting codes and employ parallel encoding and decoding over the data stored in the cloud using serverless workers. This creates a fully distributed computing framework without using a master node to conduct encoding or decoding, which removes the computation, communication and storage bottleneck at the master. On the theory side, we establish that our proposed scheme is asymptotically optimal in terms of decoding time and provide a lower bound on the number of stragglers it can tolerate with high probability. Through extensive experiments, we show that our scheme outperforms existing schemes such as speculative execution and other coding theoretic methods by at least 25%.

We develop a communication-efficient distributed learning algorithm that is robust against Byzantine worker machines. We propose and analyze a distributed gradient-descent algorithm that performs a simple thresholding based on gradient norms to mitigate Byzantine failures. We show the (statistical) error-rate of our algorithm matches that of Yin et al., 2018, which uses more complicated schemes (like coordinate-wise median or trimmed mean). Furthermore, for communication efficiency, we consider a generic class of δ-approximate compressors from Karimireddy et al., 2019, that encompasses sign-based compressors and top-k sparsification. Our algorithm uses compressed gradients and gradient norms for aggregation and Byzantine removal respectively. We establish the statistical error rate of the algorithm for arbitrary (convex or non-convex) smooth loss function. We show that, in certain regime of δ, the rate of convergence is not affected by the compression operation. We have experimentally validated our results and shown good performance in convergence for convex (least-square regression) and non-convex (neural network training) problems.

In this paper, we develop a communication efficient second order distributed Newton-type algorithm. For communication efficiency, we consider a generic class of δ-approximate compressors (Karimireddy et al., 2019), which includes sign-based compression and top-k sparsification. We provide three potential settings where compression can be employed; and provide rate of convergence for smooth objectives. We show that, in the regime where δ is constant, our theoretical convergence rate matches that of a state-of-the-art distributed second order algorithm called DINGO (Crane and Roosta, 2019). This implies that we get the compression for free in this regime. The full paper can be found at https://tinyurl.com/ujnpt4c.

We study the max-affine regression model, where the unknown regression function is modeled as a maximum of a fixed number of affine functions. In recent work [1], we showed that end-to-end parameter estimates were obtainable using this model with an alternating minimization (AM) algorithm provided the covariates (or designs) were normally distributed, and chosen independently of the underlying parameters. In this paper, we show that AM is significantly more robust than the setting of [1]: It converges locally under small-ball design assumptions (which is a much broader class, including bounded log-concave distributions), and even when the underlying parameters are chosen with knowledge of the realized covariates. Once again, the final rate obtained by the procedure is near-parametric and minimax optimal (up to a polylogarithmic factor) as a function of the dimension, sample size, and noise variance. As a by-product of our analysis, we obtain convergence guarantees on a classical algorithm for the (real) phase retrieval problem in the presence of noise under considerably weaker assumptions on the design distribution than was previously known.

We analyze the performance of the LASSO algorithm (basis pursuit, Tibshirani et. al, '96) for a class of structured matrices known as convolutional sparse matrix. Analyzing such matrices is of paramount interest since in many signal processing applications (including computer vision, image and audio processing), a global analysis of the underlying signal often entails understanding the behavior of convolutional sparse matrix. We show that LASSO (ℓ1regularized least squares) with such matrices succeeds under a constraint on local sparsity, as opposed to global sparsity. This conversion from global to local constraint has crucial significance in the above mentioned applications. Under sufficiency conditions like Restricted Eigen-value (RE) and Exact Recovery Coefficient (ERC), we obtain the prediction (in ℓ2norm) error and estimation error rate for LASSO estimator with local sparsity constraints. Furthermore, we obtain an estimation error rate for LASSO estimator in ℓ∞norm under a gaussian noise model. A full version of this paper is accessible at: https://tinyurl.com/rwy2l3o.

Distributed implementations of gradient-based methods, wherein a server distributes gradient computations across worker machines, need to overcome two limitations: delays caused by slow running machines called stragglers, and communication overheads. Recently, Ye and Abbe [ICML 2018] proposed a coding-theoretic paradigm to characterize a fundamental trade-off between computation load per worker, communication overhead per worker, and straggler tolerance. However, their proposed coding schemes suffer from heavy decoding complexity and poor numerical stability. In this paper, we develop a communication-efficient gradient coding framework to overcome these drawbacks. Our proposed framework enables using any linear code to design the encoding and decoding functions. When a particular code is used in this framework, its block-length determines the computation load, dimension determines the communication overhead, and minimum distance determines the straggler tolerance. The flexibility of choosing a code allows us to gracefully trade-off the straggler threshold and communication overhead for smaller decoding complexity and higher numerical stability. Further, we show that using a maximum distance separable (MDS) code generated by a random Gaussian matrix in our framework yields a gradient code that is optimal with respect to the trade-off and, in addition, satisfies stronger guarantees on numerical stability as compared to the previously proposed schemes. Finally, we evaluate our proposed framework on Amazon EC2 and demonstrate that it reduces the average iteration time by 16% as compared to prior gradient coding schemes.

Matrix-matrix multiplication and its derivatives are fundamental linear-algebraic primitives at the core of many modern optimization and machine learning algorithms. We design a new and novel framework for speeding up large-scale matrix-matrix multiplication when the output matrix is known to be sparse, as is true in many applications of interest. Our solution is based on a novel use of product codes which have been studied in the communications literature. In particular, when multiplying two matrices of sizes n × d and d n where the output matrix is (exactly) K-sparse with support× uniformly distributed, our algorithm requires max(O(dK), O(dn)) computations. We also extend our framework to handle the approximately-sparse setting where the output matrix has K-entries that are significantly larger than the rest. In this case, the computational complexity is max(O(dK log2(n)), O(dn log2(n))). We corroborate our findings with numerical simulations that validate our claims.

We address the problem of Federated Learning (FL) where users are distributed and partitioned into clusters. This setup captures settings where different groups of users have their own objectives (learning tasks) but by aggregating their data with others in the same cluster (same learning task), they can leverage the strength in numbers in order to perform more efficient Federated Learning. We propose a new framework dubbed the Iterative Federated Clustering Algorithm (IFCA), which alternately estimates the cluster identities of the users and optimizes model parameters for the user clusters via gradient descent. We analyze the convergence rate of this algorithm first in a linear model with squared loss and then for generic strongly convex and smooth loss functions. We show that in both settings, with good initialization, IFCA converges at an exponential rate, and discuss the optimality of the statistical error rate. When the clustering structure is ambiguous, we propose to train the models by combining IFCA with the weight sharing technique in multi-task learning. In the experiments, we show that our algorithm can succeed even if we relax the requirements on initialization with random initialization and multiple restarts. We also present experimental results showing that our algorithm is efficient in non-convex problems such as neural networks. We demonstrate the benefits of IFCA over the baselines on several clustered FL benchmarks.

Imitation learning (IL) aims to mimic the behavior of an expert policy in a sequential decision-making problem given only demonstrations. In this paper, we focus on understanding the minimax statistical limits of IL in episodic Markov Decision Processes (MDPs). We first consider the setting where the learner is provided a dataset of $N$ expert trajectories ahead of time, and cannot interact with the MDP. Here, we show that the policy which mimics the expert whenever possible is in expectation $\lesssim \frac{|\mathcal{S}| H^2 \log (N)}{N}$ suboptimal compared to the value of the expert, even when the expert plays a stochastic policy. Here $\mathcal{S}$ is the state space and $H$ is the length of the episode. Furthermore, we establish a suboptimality lower bound of $\gtrsim |\mathcal{S}| H^2 / N$ which applies even if the expert is constrained to be deterministic, or if the learner is allowed to actively query the expert at visited states while interacting with the MDP for $N$ episodes. To our knowledge, this is the first algorithm with suboptimality having no dependence on the number of actions, under no additional assumptions. We then propose a novel algorithm based on minimum-distance functionals in the setting where the transition model is given and the expert is deterministic. The algorithm is suboptimal by $\lesssim |\mathcal{S}| H^{3/2} / N$, matching our lower bound up to a $\sqrt{H}$ factor, and breaks the $\mathcal{O}(H^2)$ error compounding barrier of IL.

Robustness of machine learning models to various adversarial and non-adversarial corruptions continues to be of interest. In this paper, we introduce the notion of the boundary thickness of a classifier, and we describe its connection with and usefulness for model robustness. Thick decision boundaries lead to improved performance, while thin decision boundaries lead to overfitting (e.g., measured by the robust generalization gap between training and testing) and lower robustness. We show that a thicker boundary helps improve robustness against adversarial examples (e.g., improving the robust test accuracy of adversarial training), as well as so-called out-of-distribution (OOD) transforms, and we show that many commonly-used regularization and data augmentation procedures can increase boundary thickness. On the theoretical side, we establish that maximizing boundary thickness is akin to minimizing the so-called mixup loss. Using these observations, we can show that noise-augmentation on mixup training further increases boundary thickness, thereby combating vulnerability to various forms of adversarial attacks and OOD transforms. We can also show that the performance improvement in several recent lines of work happens in conjunction with a thicker boundary.

SUMMARY: We propose a new spectral framework for reliable training, scalable inference and interpretable explanation of the DNA repair outcome following a Cas9 cutting. Our framework, dubbed CRISPRL and, relies on an unexploited observation about the nature of the repair process: the landscape of the DNA repair is highly sparse in the (Walsh-Hadamard) spectral domain. This observation enables our framework to address key shortcomings that limit the interpretability and scaling of current deep-learning-based DNA repair models. In particular, CRISPRL and reduces the time to compute the full DNA repair landscape from a striking 5230 years to 1 week and the sampling complexity from 1012 to 3 million guide RNAs with only a small loss in accuracy (R2R2 ∼ 0.9). Our proposed framework is based on a divide-and-conquer strategy that uses a fast peeling algorithm to learn the DNA repair models. CRISPRL and captures lower-degree features around the cut site, which enrich for short insertions and deletions as well as higher-degree microhomology patterns that enrich for longer deletions. AVAILABILITY AND IMPLEMENTATION: The CRISPRL and software is publicly available at https://github.com/UCBASiCS/CRISPRLand.

We present a method for converting the voices between a set of speakers. Our method is based on training multiple autoencoder paths, where there is a single speaker-independent encoder and multiple speaker-dependent decoders. The autoencoders are trained with an addition of an adversarial loss which is provided by an auxiliary classifier in order to guide the output of the encoder to be speaker independent. The training of the model is unsupervised in the sense that it does not require collecting the same utterances from the speakers nor does it require time aligning over phonemes. Due to the use of a single encoder, our method can generalize to converting the voice of out-of-training speakers to speakers in the training dataset. We present subjective tests corroborating the performance of our method.

First-order gradient methods are commonly used for compressed sensing reconstruction. However, for Fourier sampling systems, they require computing a large number of fast Fourier transforms (FFTs), which can be expensive in real-time applications. In this paper, instead of random sub-sampling, we use a sampling scheme inspired by coding theory from a recent sparse-FFT work of Pawar and Ramchandran [1]. In particular, we show that Iterative Soft Thresholding Algorithm (ISTA) applied on the Least Absolute Shrinkage and Selection Operator (LASSO) with the coded sampling provides an O(log n) per-iteration speedup over the standard iteration cost, where n is the signal length. Since the coded sampling operation deviates from the common randomized compressed sensing sampling, it is a priori unclear whether LASSO can recover sparse signals. We provide recovery guarantees for LASSO using the coded sampling guaranteed for an arbitrary signal-to-noise ratio. For a k-sparse signal and under a uniformly random sparsity model, we show that LASSO recovers the underlying signal from O(k log4n) measurements through the coded sensing system, with a reconstruction error that is proportional to the sparsity level and noise energy. Moreover, we demonstrate numerically computational speedups for using this scheme as well as lower MRI acquisition times.

We study robust distributed learning that involves minimizing a non-convex loss function with saddle points. We consider the Byzantine setting where some worker machines have abnormal or even arbitrary and adversarial behavior, and in this setting, the Byzantine machines may create fake local minima near a saddle point that is far away from any true local minimum, even when robust gradient estimators are used. We develop ByzantinePGD, a robust first-order algorithm that can provably escape saddle points and fake local minima, and converge to an approximate true local minimizer with low iteration complexity. As a by-product, we give a simpler algorithm and analysis for escaping saddle points in the usual non-Byzantine setting. We further discuss three robust gradient estimators that can be used in ByzantinePGD, including median, trimmed mean, and iterative filtering. We characterize their performance in concrete statistical settings, and argue for their near-optimality in low and high dimensional regimes.

Many machine learning models are vulnerable to adversarial attacks; for example, adding adversarial perturbations that are imperceptible to humans can often make machine learning models produce wrong predictions with high confidence; moreover, although we may obtain robust models on the training dataset via adversarial training, in some problems the learned models cannot generalize well to the test data. In this paper, we focus on $\ell_\infty$ attacks, and study the adversarially robust generalization problem through the lens of Rademacher complexity. For binary linear classifiers, we prove tight bounds for the adversarial Rademacher complexity, and show that the adversarial Rademacher complexity is never smaller than its natural counterpart, and it has an unavoidable dimension dependence, unless the weight vector has bounded $\ell_1$ norm, and our results also extend to multi-class linear classifiers; in addition, for (nonlinear) neural networks, we show that the dimension dependence in the adversarial Rademacher complexity also exists. We further consider a surrogate adversarial loss for one-hidden layer ReLU network and prove margin bounds for this setting. Our results indicate that having $\ell_1$ norm constraints on the weight matrices might be a potential way to improve generalization in the adversarial setting. We demonstrate experimental results that validate our theoretical findings.

Distributed implementations of gradient-based methods, wherein a server distributes gradient computations across worker machines, suffer from slow running machines, called stragglers. Gradient coding is a coding-theoretic framework to mitigate stragglers by enabling the server to recover the gradient sum in the presence of stragglers. Approximate gradient codes are variants of gradient codes that reduce computation and storage overhead per worker by allowing the server to approximately reconstruct the gradient sum.In this work, our goal is to construct approximate gradient codes that are resilient to stragglers selected by a computationally unbounded adversary. Our motivation for constructing codes to mitigate adversarial stragglers stems from the challenge of tackling stragglers in massive-scale elastic and serverless systems, wherein it is difficult to statistically model stragglers. Towards this end, we propose a class of approximate gradient codes based on balanced incomplete block designs (BIBDs). We show that the approximation error for these codes depends only on the number of stragglers, and thus, adversarial straggler selection has no advantage over random selection. In addition, the proposed codes admit computationally efficient decoding at the server. Next, to characterize fundamental limits of adversarial straggling, we consider the notion of adversarial threshold - the smallest number of workers that an adversary must straggle to inflict certain approximation error. We compute a lower bound on the adversarial threshold, and show that codes based on symmetric BIBDs maximize this lower bound among a wide class of codes, making them excellent candidates for mitigating adversarial stragglers.

The goal of differentially private data publishing is to release a modified dataset so that its privacy can be ensured while allowing for efficient learning. We propose a new data publishing algorithm in which a released dataset is formed by mixing ℓ randomly chosen data points and then perturbing them with an additive noise. Our privacy analysis shows that as ℓ increases, noise with smaller variance is sufficient to achieve a target privacy level. In order to quantify the usefulness of our algorithm, we adopt the accuracy of a predictive model trained with our synthetic dataset, which we call the utility of the dataset. By characterizing the utility of our dataset as a function of ℓ, we show that one can learn both linear and nonlinear predictive models so that they yield reasonably good prediction accuracies. Particularly, we show that there exists a sweet spot on ℓ that maximizes the prediction accuracy given a required privacy level, or vice versa. We also demonstrate that given a target privacy level, our datasets can achieve higher utility than other datasets generated with the existing data publishing algorithms.

Pseudo-Boolean functions are functions whose input variables are binary and output is in the real numbers. These functions show up in many different applications in computer science, finance and economics to name a few. Pseudo-Boolean functions lend themselves to a spectral representation, which is closely related to the Walsh-Hadamard Transform from signal processing. In some problems, the coefficients of the spectral representation are active only on the low-degree terms. In this work, we present a method for computationally-efficient recovery of these low-degree coefficients. Our method is based on evaluating the input pseudo-Boolean function at points given by the codewords of a codebook, and then performing a Walsh-Hadamard Transform on the resulting signal. Codes having high rates and good minimum distance properties yield sets of evaluations points whose size is close to the number of low-degree coefficients. In particular perfect codes, such as Hamming Codes or the Golay Code, enable efficient recovery with optimal number of evaluations of the function.

We study the support recovery problem for compressed sensing, where the goal is to reconstruct the sparsity pattern of a high-dimensional K-sparse signal x ∈ ℝN, as well as the corresponding sparse coefficients, from low-dimensional linear measurements with and without noise. Our key contribution is a new compressed sensing framework through a new family of carefully designed sparse measurement matrices associated with minimal measurement costs and a low-complexity recovery algorithm. Specifically, the measurement matrix in our framework is designed based on the well-crafted sparsification through capacity-approaching sparse-graph codes, where the sparse coefficients can be recovered efficiently in a few iterations by performing simple error decoding over the observations. We formally connect this general recovery problem with sparsegraph decoding in packet communication systems and analyze our framework in terms of the measurement cost, computational complexity, and recovery performance. Specifically, we show that in the noiseless setting, our framework can recover any arbitrary K-sparse signal in O(K) time using 2K measurements asymptotically with a vanishing error probability. In the noisy setting, when the sparse coefficients take values in a finite and quantized alphabet, our framework can achieve the same goal in time O(K log(N/K)) using O(K log(N/K)) measurements obtained from measurement matrix with elements {-1, 0, 1}. When the sparsity K is sub-linear in the signal dimension K = O(Nδ) for some 0δ) and the magnitudes of all thesparse coefficients are bounded below by a positive constant, our algorithm can recover an arbitrarily large (1- p)-fraction of the support of the sparse signal using O(K log(N/K) log log(N/K)) measurements, and O(K log3(N/K)) run-time, where r is an arbitrarily small constant. For each recovered sparse coefficient, we can achieve O(∈) error for an arbitrarily small constant E. In addition, if the magnitudes of all the sparse coefficients are upper bounded by O(Kc) for some constant c1recovery guarantee for the estimated signal x̂: ∥x̂ - x∥1≤ κ∥x∥1, where the constant κ can be arbitrarily small. This offers the desired scalability of our framework that can potentially enable real-time or near-realtime processing for massive datasets featuring sparsity, which are relevant to a multitude of practical applications.

In this paper, we consider the mixture of sparse linear regressions model. Let β(1), . . ., β(L)∈ ℂnbe L unknown sparse parameter vectors with a total of K non-zero elements. Noisy linear measurements are obtained in the form yi= xiHβ(ℓi) + wi, each of which is generated randomly from one of the sparse vectors with the label ℓiunknown. The goal is to estimate the parameter vectors efficiently with low sample and computational costs. This problem presents significant challenges as one needs to simultaneously solve the demixing problem of recovering the labels ℓias well as the estimation problem of recovering the sparse vectors β(ℓ). Our solution to the problem leverages the connection between modern coding theory and statistical inference. We introduce a new algorithm, MixedColoring, which samples the mixture strategically using query vectors xiconstructed based on ideas from sparse graph codes. Our novel code design allows for both efficient demixing and parameter estimation. To find K non-zero elements, it is clear that we need at least Θ(K) measurements, and thus the time complexity is at least (K). In the noiseless setting, for a constant number of sparse parameter vectors, our algorithm achieves the order-optimal sample and time complexities of Θ(K). In the presence of Gaussian noise,1 for the problem with two parameter vectors (i.e., L = 2), we show that the Robust Mixed-Coloring algorithm achieves near-optimal Θ(K polylog(n)) sample and time complexities. When K = O(nα) for some constant α ∈ (0, 1) (i.e., K is sublinear in n), we can achieve sample and time complexities both sublinear in the ambient dimension. In one of our experiments, to recover a mixture of two regressions with dimension n = 500 and sparsity K = 50, our algorithm is more than 300 times faster than EM algorithm, with about one third of its sample cost.

A common problem in machine learning is to rank a set of n items based on pairwise comparison. Here, ranking refers to partitioning the items into sets of pre-specified sizes according to theirs scores, which includes identification of the top-k items as the most prominent special case. The score of a given item is defined as the probability that it beats a randomly chosen other item. In practice, in particular when n is large, finding an exact ranking typically requires a prohibitively large number of comparisons. What comes to our rescue here is that in practice, one is usually content with finding an approximate ranking. In this paper we consider the problem of finding approximate rankings from pairwise comparisons. We analyze an active ranking algorithm that counts the number of comparisons won, and decides whether to stop or which pair of items to compare next, based on confidence intervals computed from the data collected in previous steps. We show that this algorithm succeeds in recovering approximate rankings using a number of comparisons that is close to optimal up to logarithmic factors. We also present numerical results, showing that in practice, approximation can drastically reduce the number of comparisons required to estimate a ranking.

It has been experimentally observed that distributed implementations of mini-batch stochastic gradient descent (SGD) algorithms exhibit speedup saturation and decaying generalization ability beyond a particular batch-size. In this work, we present an analysis hinting that high similarity between concurrently processed gradients may be a cause of this performance degradation. We introduce the notion of gradient diversity that measures the dissimilarity between concurrent gradient updates, and show its key role in the convergence and generalization performance of mini-batch SGD. We also establish that heuristics similar to DropConnect, Langevin dynamics, and quantization, are provably diversity-inducing mechanisms, and provide experimental evidence indicating that these mechanisms can indeed enable the use of larger batches without sacrificing accuracy and lead to faster training in distributed learning. For example, in one of our experiments, for a convolutional neural network to reach 95% training accuracy on MNIST, using the diversity-inducing mechanism can reduce the training time by 30% in the distributed setting.

We propose OverSketch, an approximate algorithm for distributed matrix multiplication in serverless computing. OverSketch leverages ideas from matrix sketching and high-performance computing to enable cost-efficient multiplication that is resilient to faults and straggling nodes pervasive in low-cost serverless architectures. We establish statistical guarantees on the accuracy of OverSketch and empirically validate our results by solving a large-scale linear program using interior-point methods and demonstrate a 34% reduction in compute time on AWS Lambda.

In this paper, we develop distributed optimization algorithms that are provably robust against Byzantine failures—arbitrary and potentially adversarial behavior, in distributed computing systems, with a focus on achieving optimal statistical performance. A main result of this work is a sharp analysis of two robust distributed gradient descent algorithms based on median and trimmed mean operations, respectively. We prove statistical error rates for all of strongly convex, non-strongly convex, and smooth non-convex population loss functions. In particular, these algorithms are shown to achieve order-optimal statistical error rates for strongly convex losses. To achieve better communication efficiency, we further propose a median-based distributed algorithm that is provably robust, and uses only one communication round. For strongly convex quadratic loss, we show that this algorithm achieves the same optimal error rate as the robust distributed gradient descent algorithms.

Distributed computing allows for large-scale computation and machine learning tasks by enabling parallel computing at massive scale. A critical challenge to speeding up distributed computing comes from stragglers, a crippling bottleneck to system performance [1]. Recently, coding theory has offered an attractive paradigm dubbed as coded computation [2] for addressing this challenge through the judicious introduction of redundant computing to combat stragglers. However, most existing approaches have limited applicability if the system scales to hundreds or thousands of workers, as is the trend in computing platforms. At these scales, previously proposed algorithms based on Maximum Distance Separable (MDS) codes are too expensive due to their hidden cost, i.e., computing and communication costs associated with the encoding/decoding procedures. Motivated by this limitation, we present a novel coded matrix-matrix multiplication scheme based on d-dimensional product codes. We show that our scheme allows for order-optimal computation/communication costs for the encoding/decoding procedures while achieving near-optimal compute time.

Codes are widely used in many engineering applications to offerrobustnessagainstnoise. In large-scale systems, there are several types of noise that can affect the performance of distributed machine learning algorithms—straggler nodes, system failures, or communication bottlenecks—but there has been little interaction cutting across codes, machine learning, and distributed systems. In this paper, we provide theoretical insights on howcodedsolutions can achieve significant gains compared with uncoded ones. We focus on two of the most basic building blocks of distributed learning algorithms:matrix multiplicationanddata shuffling. For matrix multiplication, we use codes to alleviate the effect of stragglers and show that if the number of homogeneous workers is$n$, and the runtime of each subtask has an exponential tail, coded computation can speed up distributed matrix multiplication by a factor of$\log n$. For data shuffling, we use codes to reduce communication bottlenecks, exploiting the excess in storage. We show that when a constant fraction$\alpha $of the data matrix can be cached at each worker, and$n$is the number of workers,coded shufflingreduces the communication cost by a factor of$\left({\alpha + \frac {1}{n}}\right)\gamma (n)$compared with uncoded shuffling, where$\gamma (n)$is the ratio of the cost of unicasting$n$messages to$n$users to multicasting a common message (of the same size) to$n$users. For instance,$\gamma (n) \simeq n$if multicasting a message to$n$users is as cheap as unicasting a message to one user. We also provide experimental results, corroborating our theoretical gains of the coded algorithms.

It is a well-known fact that the Discrete Fourier Transform (DFT) X̅ of an arbitrary n-length input signal x̅, can be computed from all the n time-domain samples in O(n log n) operations via a Fast Fourier Transform (FFT) algorithm. If the spectrum X̅ is k-sparse (where k ≪ n), can we do better? We show that asymptotically in k and n, when k is sub-linear in n (precisely, k = O(nδ), where 0 ≤ δ <; 1), and the support of the non-zero DFT coefficients is uniformly random, the fast fourier aliasing-based sparse transform (FFAST) algorithm, proposed in this paper, computes, with asymptotically high probability, the k non-zero DFT coefficients of X̅ from O(k) samples of x̅ in O(k log k) arithmetic operations. Further, the constants in the big Oh notation for both sample and computational cost are small, e.g., when δ <; 0.99, which essentially covers a wide range of sublinear sparsity cases, the sample cost is less than 4k. Although, in this paper we assume that the samples of the signal x̅ observed by the FFAST are noise-free, a noise-robust extension of the FFAST is provided in a companion (Part II) paper [1]. Our approach is based on filter-less sub-sampling of the input signal using a set of carefully chosen uniform sub-sampling patterns guided by the Chinese Remainder Theorem (CRT). The idea is to cleverly exploit, rather than avoid, the resulting aliasing artifacts induced by sub-sampling. Specifically, the sub-sampling operation on the time-domain signal x̅ is designed to create aliasing patterns of the non-zero coefficients of the spectrum X̅ to “look like” paritycheck constraints of a good erasure-correcting sparse-graph code. Next, we show that computing the sparse DFT X̅ is equivalent to decoding of an appropriate sparse-graph code. The sparse-graph codes further permit a fast peeling-style decoding. Consequently, the resulting DFT computation is low in both the sample and the decoding complexity. We analytically connect our proposed CRTbased aliasing framework to random sparse-graph codes, and analyze the performance of our algorithm using density evolution techniques from coding theory. We provide extensive simulation results, that are in tight agreement with our theoretical findings.

The fast Fourier transform is the most efficiently known way to compute the discrete Fourier transform (DFT) of an arbitrary n-length signal, and has a computational complexity of O(n log n). If the DFT X⃗ of the signal x⃗ has only k non-zero coefficients (where k3n) noise-corrupted time-domain samples in O(k log4n) complexity, i.e., sub-linear sample and time complexity. In Section IX, we provide extensive simulation results validating the empirical performance of the R-FFAST algorithm, e.g., we show that the R-FFAST algorithm computes a 50-sparse DFT of an ≈10 million length signal using only 4800 noisy samples with an effective signal-to-noise ratio of 5 dB. We also provide comparison of the run-time performance of several existing sparse Fourier transform implementations with that of the R-FFAST and show that it is almost 20 times faster, for comparable settings, than the state-of-the-art algorithm, while simultaneously providing better support recovery guarantees. While our theoretical results are for signals with a uniformly random support of the non-zero DFT coefficients and additive white Gaussian noise, we provide simulation results, which demonstrate that the R-FFAST algorithm performs well even for signals like magnetic resonance images, that have an approximately sparse Fourier spectrum with a non-uniform support for the dominant DFT coefficients.

Repair operations in erasure-coded distributed storage systems involve a lot of data movement. This can potentially expose data to malicious acts of passive eavesdroppers or active adversaries, putting security of the system at risk. This paper presents coding schemes and repair algorithms that ensure security of the data in the presence of passive eavesdroppers and active adversaries while maintaining high availability, reliability, and resource efficiency in the system. The proposed codes are optimal in that they meet previously proposed lower bounds on storage and network-bandwidth requirements for a wide range of system parameters. The results thus establish the secure storage capacity of such systems. The proposed codes are based on an optimal class of codes called product-matrix codes. The constructions presented for security from active adversaries provide an additional appealing feature of “on-demand security,” where the desired level of security can be chosen separately for each instance of repair, and the proposed algorithms remain optimal simultaneously for all possible security levels. This paper also provides necessary and sufficient conditions governing the transformation of any (non-secure) code into one providing on-demand security.

In this paper, we design a fast and efficient energy-based and asynchronous neighbor discovery protocol for the Internet of Things (IoT). In our solution, we relax the assumption of frame-level synchronization. We formulate a novel asynchronous group testing scheme and apply it to the neighbor discovery problem. We then show that our proposed scheme is able to detect the set of K active neighbors1among a network of n nodes with codeword length and decoding complexity of Θ(K log (K) log (n)). Finally, we provide extensive simulation results to verify our theoretical guarantees.

We consider the online one-class collaborative filtering (CF) problem that consist of recommending items to users over time in an online fashion based on positive ratings only. This problem arises when users respond only occasionally to a recommendation with a positive rating, and never with a negative one. We study the impact of the probability of a user responding to a recommendation, $p_f$, on the sample complexity, and ask whether receiving positive and negative ratings, instead of positive ratings only, improves the sample complexity. Both questions arise in the design of recommender systems. We introduce a simple probabilistic user model, and analyze the performance of an online user-based CF algorithm. We prove that after an initial cold start phase, where recommendations are invested in exploring the user’s preferences, this algorithm makes—up to a fraction of the recommendations required for updating the user’s preferences—perfect recommendations. The number of ratings required for the cold start phase is nearly proportional to $1/p_f$, and that for updating the user’s preferences is essentially independent of $p_f$. As a consequence we find that, receiving positive and negative ratings instead of only positive ones improves the number of ratings required for initial exploration by a factor of $1/p_f$, which can be significant.

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.

Due to its longevity and enormous information density, DNA is an attractive medium for archival storage. In this work, we study the fundamental limits and tradeoffs of DNA-based storage systems under a simple model, motivated by current technological constraints on DNA synthesis and sequencing. Our model captures two key distinctive aspects of DNA storage systems: (1) the data is written onto many short DNA molecules that are stored in an unordered way and (2) the data is read by randomly sampling from this DNA pool. Under this model, we characterize the storage capacity, and show that a simple index-based coding scheme is optimal.

Consider a distributed computing setup consisting of a master node and n worker nodes, each equipped with p cores, and a function f (x) = g(f1(x), f2(x),..., fk(x)), where each fican be computed independently of the rest. Assuming that the worker computational times have exponential tails, what is the minimum possible time for computing f? Can we use coding theory principles to speed up this distributed computation? In [1], it is shown that distributed computing of linear functions can be expedited by applying linear erasure codes. However, it is not clear if linear codes can speed up distributed computation of `nonlinear' functions as well. To resolve this problem, we propose the use of sparse linear codes, exploiting the modern multicore processing architecture. We show that 1) our coding solution achieves the order optimal runtime, and 2) it is at least Θ(√log n) times faster than any uncoded schemes where the number of workers is n.

Coded computation is a framework for providing redundancy in distributed computing systems to make them robust to slower nodes, or stragglers. In [1], the authors propose a coded computation scheme based on maximum distance separable (MDS) codes for computing the product ATB, and this scheme is suitable for the case where one of the matrices is small enough to fit into a single compute node. In this work, we study coded computation involving large matrix multiplication where both matrices are large, and propose a new coded computation scheme, which we call product-coded matrix multiplication. Our analysis reveals interesting insights into which schemes perform best in which regimes. When the number of backup nodes scales sub-linearly in the size of the product, the product-coded scheme achieves the best run-time performance. On the other hand, when the number of backup nodes scales linearly in the size of the product, the MDS-coded scheme achieves the fundamental limit on the run-time performance. Further, we propose a novel application of low-density-parity-check (LDPC) codes to achieve linear-time decoding complexity, thus allowing our proposed solutions to scale gracefully.

Variant calling, in particular, calling SNPs (Single Nucleotide Polymorphisms) is a fundamental task in genomics. While existing packages offer excellent performance on calling SNPs which have uniquely mapped reads, they suffer in loci where the reads are multiply mapped, and are unable to make any reliable calls. Variants in multiply mapped loci can arise, for example in long segmental duplications, and can play important role in evolution and disease. In this paper, we develop a new SNP caller named abSNP, which offers three innovations. (a) abSNP calls SNPs from RNA-Seq data. Since RNA-Seq data is primarily sampled from gene regions, this method is inexpensive. (b) abSNP is able to successfully make calls on repetitive gene regions by exploiting the quality scores of multiply mapped reads carefully in order to make variant calls. (c) abSNP exploits a specific feature of RNA-Seq data, namely the varying abundance of different genes, in order to identify which repetitive copy a particular read is sampled from. We demonstrate that the proposed method offers significant performance gains on repetitive regions in simulated data. In particular, the algorithm is able to achieve near-perfect sensitivity on high-coverage SNPs, even when multiply mapped.

Anonymous social media platforms, like Secret, Yik Yak, and Whisper, have emerged as important tools for sharing ideas without the fear of judgment. Such anonymous platforms are also important in nations under authoritarian rule, where freedom of expression and the personal safety of message that authors may depend on anonymity. Whether for fear of judgment or retribution, it is sometimes crucial to hide the identities of users who post sensitive messages. In this paper, we consider a global adversary who wishes to identify the author of a message; it observes either a snapshot of the spread of a message at a certain time or sampled timestamp metadata, or both. Recent advances in rumor source detection show that existing messaging protocols are vulnerable against such an adversary. We introduce a novel messaging protocol, which we call adaptive diffusion, and show that under the snapshot adversarial model, adaptive diffusion spreads content fast and achieves perfect obfuscation of the source when the underlying contact network is an infinite regular tree. That is, all users with the message are nearly equally likely to have been the origin of the message. When the contact network is an irregular tree, we characterize the probability of maximum likelihood detection by proving a concentration result over Galton-Watson trees. Experiments on a sampled Facebook network demonstrate that adaptive diffusion effectively hides the location of the source even when the graph is finite, is irregular, and has cycles.

In order to scale economically, data centers are increasingly evolving their data storage methods from simple data replication to more powerful erasure codes, which provide the same level of reliability as replication, but at a significantly lower storage cost. In particular, it is well known that maximum-distance-separable (MDS) codes, such as Reed-Solomon codes, can achieve a target reliability with the maximum storage efficiency. While the use of codes for providing improved reliability in archival storage systems, where data is less frequently accessed (or so-called “cold data”), is well understood, the role of codes in storing more frequently accessed and active “hot data”, where latency is the key metric, is less clear. In this paper, we study data storage systems based on MDS codes through the lens of queueing theory, and term the queueing system arising under codes as an “MDS queue.” We provide lower and upper bounds on the average job latency for both centralized and decentralized versions of MDS queues. We also provide extensive simulations to corroborate our analysis as well as obtain additional insights.

Erasure codes are being extensively deployed in distributed storage systems instead of replication to achieve fault tolerance in a storage efficient manner. While traditional erasure codes are storage efficient, they can result in a significant increase in the amount of data access and downloaded during rebuilding of failed or otherwise unavailable nodes. In this paper, we present a new framework, which we call piggybacking, for constructing distributed storage codes that are efficient in the amount of data read and downloaded during rebuilding, while meeting requirements arising out of system considerations in data centers-maximum-distance-separability (MDS), high-rate, and a small number of so-called substripes. Under this setting, to the best of our knowledge, piggyback codes achieve the minimum average amount of data access and downloaded during rebuilding among all existing explicit solutions. The piggybacking framework also offers a rich design space for constructing codes for a variety of other settings. In particular, we construct codes that require minimum amount of data access and downloaded for rebuilding among all existing solutions for: 1) binary MDS array codes with more than two parities and 2) MDS codes with the smallest locality during rebuilding. In addition, we show how piggybacking can be employed to enable efficient repair of parity nodes in codes that address the rebuilding of only systematic nodes. The basic idea behind the piggybacking framework is to take multiple instances of existing codes and add carefully designed functions of the data from one instance to the others. This framework provides 25% to 50% savings in the average amount of data access and downloaded during rebuilding depending on the choice of the code parameters.

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. Several theoretical models have been proposed to explain the power of using redundant requests, and all of the existing 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. 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 under the new model. 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. Furthermore, 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 two-server case, the optimal dynamic scheduler can achieve 7%-16% lower average job latency, compared with the optimal static scheduler.

We study the design of measurement matrices for compressed sensing, where the goal is to stably acquire and reconstruct arbitrary K-sparse N-length signals in the presence of noise. We propose a new design framework that simultaneously leads to low measurement cost and low computational cost. In particular, the proposed framework guarantees successful recovery with high probability using O(K log N) measurements with a computational complexity of O(K log N). Both the measurement cost and algorithm runtime are order-optimal for support recovery when K = O (Nδ ) for some 0 <; δ <; 1. To the best of our knowledge, this is the first result that achieves this optimal scaling. The remarkable gains are brought by the proposed measurement structure based on sparse-graph codes, which allows for reconstructions of sparse signals using a simple peeling decoder. More generally, we formally connect general sparse recovery problems with sparse-graph decoding, and demonstrate our design in terms of the measurement cost, computational complexity and performance.

Sampling of bandlimited signals whose frequency support is unknown is called spectrum-blind sampling. It has attracted considerable attention due to its potential for sampling much lower than the Nyquist rate. The minimum rate for spectrum-blind sampling has been established as twice the measure of the frequency support. We study this sampling problem and propose a novel sampling framework by leveraging tools from modern coding theory. Our approach is based on subsampling the outputs of a carefully designed sparse-graph-codedfilter bank. The key idea is to exploit, rather than avoid, the aliasing artifacts induced by subsampling, which introduces linear mixing of spectral components in the form of parity constraints for sparse-graph codes. Under the proposed sampling scheme, signal reconstruction becomes equivalent to the peeling decoding of sparse-graph codes in erasure channels. As a result, we can simultaneously approach the minimum sampling rate, while also having a computational cost that is linear in the number of samples. We support our theoretical findings through numerical experiments.

We present a novel algorithm, named the 2D-FFAST (Two-dimensional Fast Fourier Aliasing-based Sparse Transform), to compute a sparse 2D-Discrete Fourier Transform (2D-DFT) featuring both low sample and computational complexity. The proposed algorithm is based on diverse concepts from signal processing (sub-sampling and aliasing), coding theory (sparse-graph codes) and number theory (Chinese-remainder-theorem) and generalizes the 1D-FFAST algorithm recently proposed by Pawar and Ramchandran to the 2D setting. Concretely, our proposed 2D-FFAST algorithm computes a k-sparse 2D-DFT, with a uniformly random support, of size N = Nx× Nyusing O(k) noiseless spatial-domain measurements in O(k log k) computational time. Our results are attractive when the sparsity is sub-linear with respect to the signal dimension, that is, when k → ∞ and k/N → 0. For the case when the spatial-domain measurements are corrupted by additive noise, our 2D-FFAST framework extends to a noise-robust version of computing a 2D-DFT using O(k log3N) measurements in sub-linear time of O(k log4N). Empirically, we show that the 2D-FFAST can compute a k = 3509 sparse 2D-DFT of a 508 × 508-size phantom image using only 4.75k measurements. We also empirically evaluate the 2D-FFAST algorithm on a real-world magnetic resonance brain image using a total of 60.18% of Fourier measurements to provide an almost instant reconstruction with SNR=4.5 dB. This provides empirical evidence that the 2D-FFAST architecture is applicable to a wider class of input signals than analyzed theoretically in the paper.

Anonymous messaging platforms like Whisper and Yik Yak allow users to spread messages over a network (e.g., a social network) without revealing message authorship to other users. The spread of messages on these platforms can be modeled by a diffusion process over a graph. Recent advances in network analysis have revealed that such diffusion processes are vulnerable to author deanonymization by adversaries with access to metadata, such as timing information. In this work, we ask the fundamental question of how to propagate anonymous messages over a graph to make it difficult for adversaries to infer the source. In particular, we study the performance of a message propagation protocol called adaptive diffusion introduced in (Fanti et al., 2015). We prove that when the adversary has access to metadata at a fraction of corrupted graph nodes, adaptive diffusion achieves asymptotically optimal source-hiding and significantly outperforms standard diffusion. We further demonstrate empirically that adaptive diffusion hides the source effectively on real social networks.

Recently developed high-throughput sequencing platforms can generate very long reads, making the perfect assembly of whole genomes information-theoretically possible [1]. One of the challenges in achieving this goal in practice, however, is that traditional assembly algorithms based on the de Bruijn graph framework cannot handle the high error rates of long-read technologies. On the other hand, overlap-based approaches such as string graphs [2] are very robust to errors, but cannot achieve the theoretical lower bounds. In particular, these methods handle the variable-length reads provided by long-read technologies in a suboptimal manner. In this work, we introduce a new assembly algorithm with two desirable features in the context of long-read sequencing: (1) it is an overlap-based method, thus being more resilient to read errors than de Bruijn graph approaches; and (2) it achieves the information-theoretic bounds even in the variable-length read setting.

Distributed machine learning algorithms that are widely run on modern large-scale computing platforms face several types of randomness, uncertainty and system “noise.” These include stragglers1, system failures, maintenance outages, and communication bottlenecks. In this work, we view distributed machine learning algorithms through a coding-theoretic lens, and show how codes can equip them with robustness against this system noise. Motivated by their importance and universality, we focus on two of the most basic building blocks of distributed learning algorithms: data shuffling and matrix multiplication. In data shuffling, we use codes to reduce communication bottlenecks: when a constant fraction of the data can be cached at each worker node, and n is the number of workers, coded shuffling reduces the communication cost by up to a factor Θ(n) over uncoded shuffling. For matrix multiplication, we use codes to alleviate the effects of stragglers, also known as the straggler problem. We show that if the number of workers is n, and the runtime of each subtask has an exponential tail, the optimal coded matrix multiplication is Θ(log n) times faster than the uncoded matrix multiplication or the optimal task replication scheme.

Group testing is the problem of identifying K defective items among n items by pooling groups of items. In this paper, we design group testing algorithms for approximate recovery with order-optimal sample complexity by leveraging design and analysis tools from modern sparse-graph coding theory. Our algorithm, SAFFRON, recovers at least (1 - ε)K defective items w.p.1 - K/nr with m = 2(1 + r)C(ε)K log2n tests, where ε is an arbitrarily small constant, C(ε) is a precisely characterizable constant, and r is any positive integer. The decoding complexity is Θ(K log n). We also propose variations of SAFFRON, which are robust to noise and unknown offsets. For example, for n ≃ 4.3 × 109and K = 128, our algorithm is observed to recover all defective items with m ≃ 8.3 × 105tests, even in the presence of noisy test results. Moreover, the decoding time takes less than 4 seconds on a laptop with a 2 GHz Intel Core i7 and 8 GB memory.

We consider the problem of constructing explicit erasure codes for distributed storage with the following desirable properties motivated by system constraints: (i) Maximum-Distance-Separable (MDS), (ii)Optimal repair-bandwidth, (iii)Flexibility in repair (as will be described), (iv) Systematic Form, and (v) Fast encoding (enabled by a sparse generator matrix). Existing constructions in the literature satisfy only strict subsets of these desired properties. This paper presents the first explicit code construction which theoretically guarantees all the five desired properties simultaneously. We first present a construction that builds on Product-Matrix (PM) codes by enabling sparsity in its generator matrix. We then present a transformation for general classes of storage and repair optimal codes to enable fast encoding through sparsity. In practice, such sparse codes are roughly 7 times sparser than their standard counterparts, and result in encoding speedup by a factor of about 4 for typical parameters.

Anonymous messaging applications have recently gained popularity as a means for sharing opinions without fear of judgment or repercussion. Messages in these applications propagate anonymously (without authorship metadata) over a network that is typically defined by social connections or physical proximity. However, recent advances in rumor source detection show that the source of such an anonymous message can be inferred by statistical inference attacks. Adaptive diffusion was recently proposed as a solution that achieves optimal source obfuscation over regular trees. However, in real social networks, node degrees differ from node to node, and adaptive diffusion can be significantly sub-optimal. This gap increases as the degrees become more irregular.

Data in the form of pairwise comparisons arises in many domains, including preference elicitation, sporting competitions, and peer grading among others. We consider parametric ordinal models for such pairwise comparison data involving a latent vector $w^* \in \mathbb{R}^d$ that represents the “qualities” of the $d$ items being compared; this class of models includes the two most widely used parametric models---the Bradley-Terry-Luce (BTL) and the Thurstone models. Working within a standard minimax framework, we provide tight upper and lower bounds on the optimal error in estimating the quality score vector $w^*$ under this class of models. The bounds depend on the topology of the comparison graph induced by the subset of pairs being compared, via the spectrum of the Laplacian of the comparison graph. Thus, in settings where the subset of pairs may be chosen, our results provide principled guidelines for making this choice. Finally, we compare these error rates to those under cardinal measurement models and show that the error rates in the ordinal and cardinal settings have identical scalings apart from constant pre- factors.

Many systems possess the flexibility to serve requests in more than one way, such as distributed storage systems that store multiple copies of the data. In such systems, the latency of serving the requests may potentially be reduced by sending redundant requests: a request may be sent to more servers than needed and deemed served when the requisite number of servers complete service. Such a mechanism trades off the possibility of faster execution of the request with the increase in the load on the system. Several recent works empirically evaluate the latency performance of redundant requests in diverse settings. In this paper, we perform an analytical study of the latency performance of redundant requests, with the primary goals of characterizing under what scenarios sending redundant requests will help (and under what scenarios it will not), and of designing optimal redundant-requesting policies. We show that when service times are i.i.d. memoryless or “heavier,” and when the additional copies of already-completed jobs can be removed instantly, maximally scheduling redundant requests achieves the optimal average latency. On the other hand, when service times are i.i.d. “lighter” or when service times are memoryless and removal of jobs is not instantaneous, then not having any redundancy in the requests is optimal under high loads. Our results are applicable to arbitrary arrival processes.

In this paper, we study the data exchange problem, where a set of users is interested in gaining access to a common file, but where each has only partial knowledge about it as side-information. Assuming that the file is broken into packets, the side-information considered is in the form of linear combinations of the file packets. Given that the collective information of all the users is sufficient to allow recovery of the entire file, the goal is for each user to gain access to the file, while minimizing some communication cost. We assume that the users can communicate over a noiseless broadcast channel, and that the communication cost is a sum of each user's cost function over the number of bits it transmits. For instance, the communication cost could simply be the total number of bits that needs to be transmitted. In the most general case studied in this paper, each user can have any arbitrary convex cost function. We provide deterministic, polynomial-time algorithms (in the number of users and packets), which find an optimal communication scheme that minimizes the communication cost. To further lower the complexity, we also propose a simple randomized algorithm inspired by our deterministic algorithm, which is based on a random linear network-coding scheme.

Consider the problem of identifying the underlying qualities of a set of items based on measuring noisy comparisons between pairs of items. The Bradley-Terry-Luce (BTL) and Thurstone models are the most widely used parametric models for such pairwise comparison data. Working within a standard minimax framework, this paper provides sharp upper and lower bounds on the optimal error in estimating the underlying qualities under the BTL and the Thurstone models. These bounds are are topology-aware, meaning that they change qualitatively depending on the comparison graph induced by the subset of pairs being compared. Thus, in settings where the subset of pairs may be chosen, our results provide some principled guidelines for making this choice. Finally, we compare these error rates to those under cardinal measurement models and show that the error rates in the ordinal and cardinal settings have identical scalings apart from constant pre-factors. We use this result to investigate the relative merits of cardinal and ordinal measurement schemes.

We consider the problem of recovering the support of an arbitrary K-sparse N-length vector in the presence of noise, where the sparsity K = O(Nδ) is sub-linear in N for some 01.3̇N) and sub-linear computational complexity O(K log1.3̇N). Our measurement system is designed to capture observations of the signal through the parity constraints of sparse-graph codes, and to recover the signal by using a simple peeling decoder. We formally connect general sparse recovery problems with sparse-graph decoding, and showcase our design in terms of the measurement cost, computational complexity and recovery performance.

In this paper, we tackle the general compressive phase retrieval problem. The problem is to recover (to within a global phase uncertainty) a K-sparse complex vector of length n, x ∈ ℂn, from the magnitudes of m linear measurements, y = |Ax|, where A ∈ ℂm×ncan be designed, and the magnitudes are taken component-wise for vector Ax ∈ ℂm. We propose a variant of the PhaseCode algorithm, first introduced in [1], and show that under some mild assumptions, using an irregular left-degree sparse-graph code construction, the algorithm can recover almost all the K non-zero signal components using only slightly more than 4K measurements, with orderoptimal time and memory complexity of O(K). It is known that the fundamental limit for the number of measurements in compressive phase retrieval problem is 4K - o(K) [2, 3]. To the best of our knowledge, this is the first constructive capacityapproaching compressive phase retrieval algorithm: in fact, our algorithm is also order-optimal in complexity and memory.

In this paper, we tackle the compressive phase retrieval problem in the presence of noise. The noisy compressive phase retrieval problem is to recover a K-sparse complex signal s ∈ ℂn, from a set of m noisy quadratic measurements: yi= |aiHs|2+ wi; where aiH∈ ℂnis the ith row of the measurement matrix A ∈ ℂm×n, and wiis the additive noise to the ith measurement. We consider the regime where K = βnδ, δ ∈ (0; 1). We use the architecture of PhaseCode algorithm [1], and robustify it using two schemes: the almost-linear scheme and the sublinear scheme. We prove that with high probability, the almost-linear scheme recovers s with sample complexity1Θ(K log(n)) and computational complexity Θ(n log(n)), and the sublinear scheme recovers s with sample complexity Θ(K log3(n)) and computational complexity Θ(K log3(n)). To the best of our knowledge, this is the first scheme that achieves sublinear computational complexity for compressive phase retrieval problem. Finally, we provide simulation results that support our theoretical contributions.

Let $f: \{-1,1\}^n \rightarrow \mathbb{R}$ be an $n$-variate polynomial consisting of $2^n$ monomials, in which only $s\ll 2^n$ coefficients are non-zero. The goal is to learn the polynomial by querying the values of $f$. We introduce an active learning framework that is associated with a low query cost and computational runtime. The significant savings are enabled by leveraging sampling strategies based on modern coding theory, specifically, the design and analysis of {\it sparse-graph codes}, such as Low-Density-Parity-Check (LDPC) codes, which represent the state-of-the-art of modern packet communications. More significantly, we show how this design perspective leads to exciting, and to the best of our knowledge, largely unexplored intellectual connections between learning and coding. The key is to relax the worst-case assumption with an ensemble-average setting, where the polynomial is assumed to be drawn uniformly at random from the ensemble of all polynomials (of a given size $n$ and sparsity $s$). Our framework succeeds with high probability with respect to the polynomial ensemble with sparsity up to $s={O}(2^{\delta n})$ for any $\delta\in(0,1)$, where $f$ is exactly learned using ${O}(ns)$ queries in time ${O}(n s \log s)$, even if the queries are perturbed by Gaussian noise. We further apply the proposed framework to graph sketching, which is the problem of inferring sparse graphs by querying graph cuts. By writing the cut function as a polynomial and exploiting the graph structure, we propose a sketching algorithm to learn the an arbitrary $n$-node unknown graph using only few cut queries, which scales {\it almost linearly} in the number of edges and {\it sub-linearly} in the graph size $n$. Experiments on real datasets show significant reductions in the runtime and query complexity compared with competitive schemes.

Given a similarity graph between items, correlation clustering (CC) groups similar items together and dissimilar ones apart. One of the most popular CC algorithms is KwikCluster: an algorithm that serially clusters neighborhoods of vertices, and obtains a 3-approximation ratio. Unfortunately, in practice KwikCluster requires a large number of clustering rounds, a potential bottleneck for large graphs.We present C4 and ClusterWild!, two algorithms for parallel correlation clustering that run in a polylogarithmic number of rounds, and provably achieve nearly linear speedups. C4 uses concurrency control to enforce serializability of a parallel clustering process, and guarantees a 3-approximation ratio. ClusterWild! is a coordination free algorithm that abandons consistency for the benefit of better scaling; this leads to a provably small loss in the 3 approximation ratio.We provide extensive experimental results for both algorithms, where we outperform the state of the art, both in terms of clustering accuracy and running time. We show that our algorithms can cluster billion-edge graphs in under 5 seconds on 32 cores, while achieving a 15x speedup.

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.

In this paper, we consider the problem of computing a K-sparse N-point Hadamard Transforms (HT) from noisy time domain samples, where K = O(Nα) scales sub-linearly in N for some α ∈ (0; 1). The SParse Robust Iterative Graph-based Hadamard Transform (SPRIGHT) algorithm is proposed to recover the sparse HT coefficients in a stable manner that is robust to additive Gaussian noise. In particular, it is shown that the K-sparse HT of the signal can be reconstructed from noisy time domain samples with a vanishing error probability using the same sample complexity O(K logN) as in the noiseless case of [1] and computational complexity1O(N logN). Last but not least, given the complexity orders of the SPRIGHT algorithm, our numerical experiments further validate that the big-Oh constants in the complexity are small.

The Fast Fourier Transform (FFT) is the most efficiently known way to compute the Discrete Fourier Transform (DFT) of an arbitrary n-length signal, and has a computational complexity of O(n log n). If the DFT X⃗ of the signal x⃗ has only k non-zero coefficients (where k1noise-corrupted time-domain samples, in O(n log n) computations2. While our theoretical results are for signals with a uniformly random support of the non-zero DFT coefficients and additive white Gaussian noise, we provide simulation results which demonstrates that the R-FFAST algorithm performs well even for signals like MR images, that have an approximately sparse Fourier spectrum with a non-uniform support for the dominant DFT coefficients.

In order to scale economically, data centers are increasingly evolving their data storage methods from the use of simple data replication to the use of more powerful erasure codes, which provide the same level of reliability as replication but at a significantly lower storage cost. In particular, it is well known that Maximum-Distance-Separable (MDS) codes, such as Reed-Solomon codes, provide the maximum storage efficiency. While the use of codes for providing improved reliability in archival storage systems, where data is less frequently accessed (or so-called “cold data”), is well understood, the role of codes in the storage of more frequently accessed and active “hot data”, where latency is the key metric, is less clear. In this paper, we study data storage systems based on MDS codes through the lens of queueing theory, and term the queueing system arising under codes as an “MDS queue.” We present insightful scheduling policies that form upper and lower bounds to its performance, and use these to obtain easily computable analytical bounds on the average latency of the MDS queue. These bounds were observed to be quite tight in the settings we simulated. We additionally derive closed-form expressions of the throughputs of these systems. Finally, we employ the framework of the MDS queue to analyse different methods of performing so-called degraded reads (reading of partial data) in distributed data storage.

Private information retrieval (PIR) systems allow a user to retrieve a record from a public database without revealing to the server which record is being retrieved. The literature on PIR considers only replication-based systems, wherein each storage node stores a copy of the entire data. However, systems based on erasure codes are gaining increasing popularity due to a variety of reasons. This paper initiates an investigation into PIR in erasure-coded systems by establishing its capacity and designing explicit codes and algorithms. The notion of privacy considered here is information-theoretic, and the metric optimized is the amount of data downloaded by the user during PIR. In this paper, we present four main results. First, we design an explicit erasure code and PIR algorithm that requires only one extra bit of download to provide perfect privacy. In contrast, all existing PIR algorithms require a download of at least twice the size of the requisite data. Second, we derive lower bounds proving the necessity of downloading at least one additional bit. This establishes the precise capacity of PIR with respect to the metric of download. These results are also applicable to PIR in replication-based systems, which are a special case of erasure codes. Our third contribution is a negative result showing that capacity-achieving codes necessitate super-linear storage overheads. This motivates the fourth contribution of this paper: an erasure code and PIR algorithm that requires a linear storage overhead, provides high reliability to the data, and is a small factor away from the capacity.

The ability to search databases by providing multimedia examples of voices, faces, or locations instead of textual descriptions can be tremendously useful. At the same time, uploading media for queries---especially media that contains sensitive content---means sharing private information with a potentially untrusted service provider. The growing field of privacy-preserving database searches attempts to resolve this tension. Within this scope of private searches, private media classification and retrieval is particularly challenging due to the inherent inexactness of recognition; to be useful, image or other media classification systems must identify approximate matches rather than just exact ones. This is difficult to reconcile with distortion-intolerant and resource-heavy privacy primitives, especially in web-scale databases. In this paper, we present an architecture for media classification on public databases that preserves client privacy while achieving asymptotic communication and computation costs that are sublinear in the size of the database. We demonstrate the usefulness of this architecture in the context of a privacy-preserving face recognition system. We observe order-of-magnitude speedups over state-of-the-art private face recognition systems.

Erasure codes such as Reed-Solomon (RS) codes are being extensively deployed in data centers since they offer significantly higher reliability than data replication methods at much lower storage overheads. These codes however mandate much higher resources with respect to network bandwidth and disk IO during reconstruction of data that is missing or otherwise unavailable. Existing solutions to this problem either demand additional storage space or severely limit the choice of the system parameters. In this paper, we present "Hitchhiker", a new erasure-coded storage system that reduces both network traffic and disk IO by around 25% to 45% during reconstruction of missing or otherwise unavailable data, with no additional storage, the same fault tolerance, and arbitrary flexibility in the choice of parameters, as compared to RS-based systems. Hitchhiker 'rides' on top of RS codes, and is based on novel encoding and decoding techniques that will be presented in this paper. We have implemented Hitchhiker in the Hadoop Distributed File System (HDFS). When evaluating various metrics on the data-warehouse cluster in production at Facebook with real-time traffic and workloads, during reconstruction, we observe a 36% reduction in the computation time and a 32% reduction in the data read time, in addition to the 35% reduction in network traffic and disk IO. Hitchhiker can thus reduce the latency of degraded reads and perform faster recovery from failed or decommissioned machines.

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.

Linear shift-invariant processing of graph signals rests on circulant graphs and filters. The spatial features of circulant structures also permit shift-varying operations such as sampling. Their spectral features-as described by their Graph Fourier Transform profiles-enable novel multiscale signal processing systems and methods. To extend the reach of circulant structures, we present a method to decompose an arbitrary graph or filter into a combination of circulant structures. Our decomposition is analogous to resolving a linear time-varying system into a bank of linear time-invariant systems. As an application, we perform multiscale decomposition on temperature data spanning the continental United States.

We establish the fundamental limits of DNA shotgun sequencing under noisy reads. We show a surprising result: for the i.i.d. DNA model, noisy reads are as good as noiseless reads, provided that the noise level is below a certain threshold which can be surprisingly high. As an example, for a uniformly distributed DNA sequence and a symmetric substitution noisy read channel, the threshold is as high as 19%.

Given an n-length input signal x, it is well known that its Discrete Fourier Transform (DFT), X, can be computed in O(nlogn) complexity using a Fast Fourier Transform. If the spectrum X is exactly k-sparse (where kδwhere 0 <; δ <; 1), and the support of the non-zero DFT coefficients is uniformly random, we can exploit this sparsity in two fundamental ways (i) sample complexity: we need only M = rk deterministically chosen samples of the input signal x (where r <; 4 when 0 <; δ <; 0.99); and (ii) computational complexity: we can reliably compute the DFT X using O(k log k) operations, where the constants in the big Oh are small. Our algorithm succeeds with high probability, with the probability of failure vanishing to zero asymptotically in the number of samples acquired, M. Our approach is based on filterless subsampling of the input signal x using a small set of carefully chosen uniform subsampling patterns guided by the Chinese Remainder Theorem (CRT). Specifically, our subsampling operation on x is designed to create aliasing patterns on the spectrum X that "look like" parity-check constraints of good erasure-correcting sparse-graph codes. We show how computing the sparse DFT X is equivalent to decoding of these sparse-graph codes and is low in both sample complexity and decoding complexity. We accordingly dub our algorithm the FFAST (Fast Fourier Aliasing-based Sparse Transform) algorithm. In our analysis, we rigorously connect our CRT based graph constructions to random sparse-graph codes based on a balls-and-bins model and analyze the convergence behavior of the latter using well-studied density evolution techniques from coding theory. We provide simulation results in Section IV that corroborate our theoretical findings, and validate the empirical performance of the FFAST algorithm.

We present a new piggybacking framework for designing distributed storage codes that are efficient in the amount of data read and downloaded during node-repair. We illustrate the power of this framework by constructing explicit codes that attain the smallest amount of data to be read and downloaded for repair among all existing solutions for three important settings: (a) codes meeting the constraints of being maximum distance separable (MDS), high-rate, and having a small number of substripes, (b) binary MDS codes for all parameters where binary MDS codes exist, and (c) MDS codes with the smallest repair-locality. In addition, we show how to use this framework to enable efficient repair of parity nodes in existing codes that are constructed to address the repair of only the systematic nodes. The basic idea behind this framework is to take multiple stripes of existing codes and add carefully designed functions of the data of one stripe to other stripes. Typical savings in the amount of data read and downloaded during repair are 25% to 50% depending on the choice of the system parameters.

Shamir's (n, k) threshold secret sharing is an important component of several cryptographic protocols, such as those for secure multiparty-computation. These protocols typically assume the presence of direct communication links from the dealer to all participants, in which case the dealer can directly pass the shares of the secret to every participant. In this paper, we consider the problem of secret sharing when the dealer does not have direct communication links to all participants, and instead, they form a general network. We present an algorithm for secret sharing over networks that satisfy what we call the k-propagating-dealer condition. The algorithm is communication-efficient, distributed and deterministic. Interestingly, the solution constitutes an instance of a network coding problem admitting a distributed and deterministic solution, and furthermore, handles the case of nodal-eavesdropping, about which very little appears to be known in the literature. In the second part of the paper, we derive information-theoretic lower bounds on the communication complexity of secret sharing over any network, which may also be of independent interest. We show that for networks satisfying the k-propagating-dealer condition, the communication complexity of our algorithm is Θ(n), and furthermore, is always within a constant factor of the lower bound. We also show that, in contrast, existing solutions in the literature entail a communication-complexity that is superlinear for a wide class of networks, and is Θ(n2) in the worst case. Our algorithm thus allows for efficient generalization of several cryptographic protocols to a large class of networks.

We propose, analyze and implement a general architecture for massively parallel VoD content distribution. We allow for devices that have a wide range of reliability, storage and bandwidth constraints. Each device can act as a cache for other devices and can also communicate with a central server. Some devices may be dedicated caches with no co-located users. Our goal is to allow each user device to be able to stream any movie from a large catalog, while minimizing the load of the central server. First, we architect and formulate a static optimization problem that accounts for various network bandwidth and storage capacity constraints, as well as the maximum number of network connections for each device. Not surprisingly this formulation is NP-hard. We then use a Markov approximation technique in a primal-dual framework to devise a highly distributed algorithm which is provably close to the optimal. Next we test the practical effectiveness of the distributed algorithm in several ways. We demonstrate remarkable robustness to system scale and changes in demand, user churn, network failure and node failures via a packet level simulation of the system. Finally, we describe our results from numerous experiments on a full implementation of the system with 60 caches and 120 users on 20 Amazon EC2 instances. In addition to corroborating our analytical and simulation-based findings, the implementation allows us to examine various system-level tradeoffs. Examples of this include: (i) the split between server to cache and cache to device traffic, (ii) the tradeoff between cache update intervals and the time taken for the system to adjust to changes in demand, and (iii) the tradeoff between the rate of virtual topology updates and convergence. These insights give us the confidence to claim that a much larger system on the scale of hundreds of thousands of highly heterogeneous nodes would perform as well as our current implementation.

Over the recent years, the problem of video location estimation (i.e., estimating the longitude/latitude coordinates of a video without GPS information) has been approached with diverse methods and ideas in the research community and significant improvements have been made. So far, however, systems have only been compared against each other and no systematic study on human performance has been conducted. Based on a human-subject study with 11,900 experiments, this article presents a human baseline for location estimation for different combinations of modalities (audio, audio/video, audio/video/text). Furthermore, this article compares state-of-the-art location estimation systems with the human baseline. Although the overall performance of humans' multimodal video location estimation is better than current machine learning approaches, the difference is quite small: For 41% of the test set, the machine's accuracy was superior to the humans. We present case studies and discuss why machines did better for some videos and not for others. Our analysis suggests new directions and priorities for future work on the improvement of location inference algorithms.

The high repair bandwidth cost of (n,k) maximum distance separable (MDS) erasure codes has motivated a new class of codes that can reduce repair bandwidth over that of conventional MDS codes. In this paper, we address (n,k,d) exact repair MDS codes, which allow for any single failed node to be repaired exactly with access to any arbitrary set ofdsurvivor nodes. We show the existence of exact repair MDS codes that achieve minimum repair bandwidth (matching the cut-set lower bound) for arbitrary admissible (n,k,d), i.e.,k≤d≤n-1. Moreover, we extend our results to show the optimality of our codes for multiple-node failure scenarios in which an arbitrary set ofr≤n-kfailed nodes needs to repaired. Our approach is based on asymptotic interference alignment proposed by Cadambe and Jafar. As a byproduct, we also characterize the capacity of a class of multisource nonmulticast networks.

We consider a secure lossless source coding problem with a rate-limited helper. In particular, Alice observes an independent and identically distributed (i.i.d.) sourceXnand wishes to transmit this source losslessly to Bob over a rate-limited link of capacity not exceedingRx. A helper, say Helen, observes an i.i.d. correlated sourceYnand can transmit information to Bob over another link of capacity not exceedingRy. A passive eavesdropper (say Eve) can observe the coded output of Alice, i.e., the link from Alice to Bob is public. The uncertainty about the sourceXnat Eve (denoted by Δ) is measured by the conditional entropy [(H(Xn|Jx))/(n)] , whereJxis the coded output of Alice andnis the block length. We completely characterize the rate-equivocation region for this secure source coding model, where we show that Slepian-Wolf binning ofXnwith respect to the coded side information received at Bob is optimal. We next consider a modification of this model in which Alice also has access to the coded output of Helen. We call this model as the two-sided helper model. For the two-sided helper model, we characterize the rate-equivocation region. While the availability of side information at Alice does not reduce the rate of transmission from Alice, it significantly enhances the resulting equivocation at Eve. In particular, the resulting equivocation for the two-sided helper case is shown to be min(H(X),Ry), i.e., one bit from the two-sided helper provides one bit of uncertainty at Eve. From this result, we infer that Slepian-Wolf binning ofXis suboptimal and one can further decrease the information leakage to the eavesdropper by utilizing the side information at Alice. We, finally, generalize both of these results to the case in which there is additional uncoded side informationWnavailable at Bob and characterize the rate-equivocation regions under the assumption thatYn→Xn→Wnforms a Markov chain.

This paper considers a binary channel with deletions and insertions, where each input bit is transformed in one of the following ways: it is deleted with probability d, or an extra bit is added after it with probability i, or it is transmitted unmodified with probability 1-d-i. A computable lower bound on the capacity of this channel is derived. The transformation of the input sequence by the channel may be viewed in terms of runs as follows: some runs of the input sequence get shorter/longer, some runs get deleted, and some new runs are added. It is difficult for the decoder to synchronize the channel output sequence to the transmitted codeword mainly due to deleted runs and new inserted runs. The main idea is a mutual information decomposition in terms of the rate achieved by a suboptimal decoder that determines the positions of the deleted and inserted runs in addition to decoding the transmitted codeword. The mutual information between the channel input and output sequences is expressed as the sum of the rate achieved by this decoder and the rate loss due to its suboptimality. Obtaining computable lower bounds on each of these quantities yields a lower bound on the capacity. The bounds proposed in this paper provide the first characterization of achievable rates for channels with general insertions, and for channels with both deletions and insertions. For the special case of the deletion channel, the proposed bound improves on the previous best lower bound for deletion probabilities up to 0.3.

This article describes a novel approach to the problem of associating geo-locations to consumer-produced multimedia data such as videos and photos that are publicly available on social networking websites such as Flickr. We specifically focus on the case where the available training data is sparse both in absolute numbers as well as geographic coverage when compared to the number of untagged query data. We develop a novel graphical model based framework for the problem of interest and pose the problem of geotagging as one of inference over this graph. The novelty of our algorithm lies in the fact that we jointly estimate the geo-locations of all the query videos, which helps obtain performance improvements over existing algorithms in the literature that process each query video independently. Our system enables the query videos to act as "virtual" training data that effectively bootstrap the geo-tagging process. The quality of the database improves with each additional query video in the system. Further, our modeling provides a generic theoretical framework that can be used to incorporate any other available textual, visual or audio features. We evaluate our algorithm on the MediaEval 2011 Placing Task data set and show that for fixed training data the system performance improves with an increasing number of unlabeled test data. The performance gains are shown to be over 10% as compared to existing algorithms in the literature.

In this paper we understand BitTorrent protocol from a Markov approximation perspective. We show that together with the underlying rate control algorithm, the rarest first algorithm and choking algorithm in BitTorrent protocol implicitly solve a cooperative combinatorial network utility maximization problem in a distributed manner. This understanding allows us to access properties of BitTorrent from a fresh perspective, including performance optimality, convergence and impacts of design parameters. Our numerical evaluations validate the analytical results.

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.

In this paper, we quantify how much codes can reduce the data retrieval latency in storage systems. By combining a simple linear code with a novel request scheduling algorithm, which we call Blocking-one Scheduling (BoS), we show analytically that it is possible to use codes to reduce data retrieval delay by up to 17% over currently popular replication-based strategies. Although in this work we focus on a simplified setting where the storage system stores a single content, the methodology developed can be applied to more general settings with multiple contents. The results also offer insightful guidance to the design of storage systems in data centers and content distribution networks.

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.

In this paper we construct a deterministic polynomial time algorithm for the problem where a set of users is interested in gaining access to a common file, but where each has only partial knowledge of the file. We further assume the existence of another set of terminals in the system, called helpers, who are not interested in the common file, but who are willing to help the users. Given that the collective information of all the terminals is sufficient to allow recovery of the entire file, the goal is to minimize the (weighted) sum of bits that these terminals need to exchange over a noiseless public channel in order achieve this goal. Based on established connections to the multi-terminal secrecy problem, our algorithm also implies a polynomial-time method for constructing the largest shared secret key in the presence of an eavesdropper. We consider the following side-information settings: (i) side-information in the form of uncoded packets of the file, where the terminals' side-information consists of subsets of the file packets; (ii) side-information in the form of linearly correlated packets, where the terminals have access to linear combinations of the file packets; and (iii) the general setting where the the terminals' side-information has an arbitrary (i.i.d.) correlation structure. We provide a polynomial-time algorithm (in the number of terminals) that finds the optimal rate allocations for these terminals, and then determines an explicit optimal transmission scheme for cases (i) and (ii).

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.

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.

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.

Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any subset of nodes within the -node network. However, regenerating codes possess in addition, the ability to repair a failed node by connecting to an arbitrary subset of nodes. It has been shown that for the case of functional repair, there is a tradeoff between the amount of data stored per node and the bandwidth required to repair a failed node. A special case of functional repair is exact repair where the replacement node is required to store data identical to that in the failed node. Exact repair is of interest as it greatly simplifies system implementation. The first result of this paper is an explicit, exact-repair code for the point on the storage-bandwidth tradeoff corresponding to the minimum possible repair bandwidth, for the case when . This code has a particularly simple graphical description, and most interestingly has the ability to carry out exact repair without any need to perform arithmetic operations. We term this ability of the code to perform repair through mere transfer of data as repair by transfer. The second result of this paper shows that the interior points on the storage-bandwidth tradeoff cannot be achieved under exact repair, thus pointing to the existence of a separate tradeoff under exact repair. Specifically, we identify a set of scenarios which we term as “helper node pooling,” and show that it is the necessity to satisfy such scenarios that overconstrains the system.

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.

Abstract—We study the problem of cooperative node lo-calization in non-line-of-sight (NLOS) wireless networks and address design questions such as, “How many anchors and what fraction of line-of-sight (LOS) measurements are needed achieve a specified target accuracy?”. We analytically characterize the performance improvement in localization accuracy as a function of the number of nodes in the network and the fraction of LOS measurements. In particular, we show that the Cramer-Rao Lower Bound (CRLB) can be expressed as a product of two factors- a scalar function that depends only on the parameters of the noise distribution and a matrix that depends only on the geometry of node locations. This holds for arbitrary distance and angle measurement modalities under an additive noise model. Further, a simplified expression is obtained for the CRLB, which provides an insightful understanding of the bound and helps deduce the scaling behavior of the estimation error as a function of the number of agents and anchors in the network. The mean squared error in localization is shown to have an inverse linear relationship with the number of anchors or agents. The error is also shown to have an approximately inverse linear relationship with the fraction of LOS readings except at the extremes. The behavior at the extremes suggests that even a small fraction of LOS measurements can provide significant improvements. Conversely, a small fraction of NLOS measurements can significantly degrade the performance. Keywords- NLOS localization, Cramer-Rao Bound. I.

The problem of reconstructing a source sequence with the presence of decoder side-information that is mis-synchronized to the source due to deletions is studied in a distributed source coding framework. Motivated by practical applications, the deletion process is assumed to be bursty and is modeled by a Markov chain. The minimum rate needed to reconstruct the source sequence with high probability is characterized in terms of an information theoretic expression, which is interpreted as the amount of information of the deleted content and the locations of deletions, subtracting “nature's secret”, that is, the uncertainty of the locations given the source and side-information. For small bursty deletion probability, the asymptotic expansion of the minimum rate is computed.

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.

We introduce an efficient family of exact regenerating codes for data storage in large-scale distributed systems. We refer to these new codes as Distributed Replication-based Exact Simple Storage (DRESS) codes. A key property of DRESS codes is their very efficient distributed and uncoded repair and growth processes that have minimum bandwidth, reads and computational overheads. This property is essential for large-scale systems with high reliability and availability requirements. DRESS codes will first encode the file using a Maximum Distance Separable (MDS) code, then place multiple replicas of the coded packets on different nodes in the system. We propose a simple and flexible randomized scheme for placing those replicas based on the balls-and-bins model. Our construction showcases the power of the probabilistic approach in constructing regenerating codes that can be efficiently repaired and grown.

We address the problem of securing distributed storage systems against adversarial node attacks. An important aspect of these systems is node failures over time, necessitating, thus, a repair mechanism in order to maintain a desired high system reliability. In such dynamic settings, an important security problem is to safeguard the system from a malicious adversary who may come at different time instances during the lifetime of the storage system to corrupt the data stored on some nodes. We provide upper bounds on the maximum amount of information that can be stored safely on the system in the presence of the adversary. For an important operating regime, which we call the bandwidth-limited regime, we show that our upper bounds are tight and provide explicit linear code constructions. Moreover, we provide a way to shortlist the malicious nodes and expurgate the system.

Consider a binary channel with deletions and insertions, where each input bit is transformed in one of the following ways: it is deleted with probability d, or an extra bit added after it with probability i, or it is transmitted unmodified with probability 1 - d - i. We obtain a lower bound on the capacity of this channel. The transformation of the input sequence by the channel may be viewed in terms of runs as follows: some runs of the input sequence get shorter/longer, some runs get deleted, and some new runs are added. The capacity is difficult to compute mainly due to the last two phenomena: deleted runs, and new inserted runs. We consider a decoder which first decodes the positions of the deleted and inserted runs, and then the transmitted codeword. Analyzing the performance of such a decoder leads to a computable lower bound on the capacity.

We study the problem of neighbor selection in BitTorrent-like peer-to-peer (P2P) systems, and propose a "soft-worst-neighbor-choking" algorithm that is provably optimal. In practical P2P systems, peers often keep a large set of potential neighbors, but only simultaneously upload/download to/from a small subset of them, which we call active neighbors, to avoid excessive connection overhead. A natural question to ask is: which active neighbor set should each peer choose to maximize the global system performance? The combinatorial nature of the problem makes it especially challenging. In this paper, we formulate an optimization problem and derive a distributed algorithm. We remark that our solution has a similar favor compared to the worst neighbor choking and optimistic unchoking neighbor selection algorithms that are implemented by BitTorrent. However, it encourages peers to stick to better performing neighbors for longer time and is provably globally optimal. Our proposed solution is easy to implement: each peer periodically waits for a constant period of time that depends on the size of the potential neighbor set and the aggregated utility of the active neighbors, chokes (drops) one of its current active neighbors with probability proportional to an exponential weight on the utility of the corresponding link, and randomly unchokes (adds) a new neighbor from its potential neighbor set. Our theoretical findings provide insightful guidelines to designing practical P2P systems. Simulation results corroborate our proposed solution.

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.

Distributed storage systems often introduce redundancy to increase reliability. When coding is used, the repair problem arises: if a node storing encoded information fails, in order to maintain the same level of reliability we need to create encoded information at a new node. This amounts to a partial recovery of the code, whereas conventional erasure coding focuses on the complete recovery of the information from a subset of encoded packets. The consideration of the repair network traffic gives rise to new design challenges. Recently, network coding techniques have been instrumental in addressing these challenges, establishing that maintenance bandwidth can be reduced by orders of magnitude compared to standard erasure codes. This paper provides an overview of the research results on this topic.

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.

We address the problem of securing distributed storage systems against eavesdropping and adversarial attacks. An important aspect of these systems is node failures over time, necessitating, thus, a repair mechanism in order to maintain a desired high system reliability. In such dynamic settings, an important security problem is to safeguard the system from an intruder who may come at different time instances during the lifetime of the storage system to observe and possibly alter the data stored on some nodes. In this scenario, we give upper bounds on the maximum amount of information that can be stored safely on the system. For an important operating regime of the distributed storage system, which we call the bandwidth-limited regime, we show that our upper bounds are tight and provide explicit code constructions. Moreover, we provide a way to short list the malicious nodes and expurgate the system.

The problem of broadcasting a parallel Gaussian source over an additive white Gaussian noise broadcast channel under the mean-squared error distortion criterion is studied. A hybrid digital-analog coding strategy which combines source coding with side information, channel coding with side information, layered source coding, and superposition broadcast channel coding is presented. When specialized to the open problem of broadcasting a white Gaussian source over an additive white Gaussian noise broadcast channel with bandwidth mismatch, which has been the subject of several previous investigations, this coding scheme strictly improves on the state of the art.

The high repair cost of$(n,k)$Maximum Distance Separable (MDS) erasure codes has recently motivated a new class of MDS codes, called Repair MDS codes, that can significantly reduce repair bandwidth over conventional MDS codes. In this paper, we describe$(n,k,d)$Exact-Repair MDS codes, which allow for any failed node to be repaired exactly with access to$d$survivor nodes, where$k\leq d\leq n-1$. We construct Exact-Repair MDS codes that are optimal in repair bandwidth for the cases of:$(a)~k/n\leq 1/2$and$d\geq 2k-1$In this paper, we assume that all of the survivor systematic nodes participate in the repair.;$(b)~k\leq 3$. Our codes are deterministic and require a finite-field size of at most$2(n-k)$. Our constructive codes are based on interference alignment techniques.

In this paper we consider the problem of high accuracy localization of mobile nodes in a multipath-rich environment where sub-meter accuracies are required. We employ a peer to peer framework where the vehicles/nodes can get pairwise multipath-degraded ranging estimates in local neighborhoods together with a fixed number of anchor nodes. The challenge is to overcome the multipath-barrier with redundancy in order to provide the desired accuracies especially under severe multipath conditions when the fraction of received signals corrupted by multipath is dominating. We invoke a message passing analytical framework based on particle filtering and reveal its high accuracy localization promise through simulations.

In live video communication, the quality of the video that is encoded on a mobile device is more often than not constrained by the available computational resources. We address this problem by allowing the encoder to “outsource” the encoding complexity to the decoder through the use of feedback, under a sum-rate constraint comprising the weighted sum of the forward and feedback rates. Analysis of such a complexity-outsourced framework using an analytically tractable video model reveals that the feedback rate should be optimally adapted to the video motion characteristics. Application of our framework to real-world video sequences reveals the efficacy of our proposed architecture, with experimental results validating that substantial gains in PSNR are achievable over state-of-the-art fast-search algorithms at a comparable level of complexity. These gains are significant even for mobile live video communication applications over the Internet.

We investigate the design of a frame-bufferless and low-latency video communication system, where the encoder has no access to any previous frames and only one use of feedback communication from the decoder to the encoder is allowed in encoding each frame. This strict requirement on encoder complexity and system latency is of critical importance in designing low complexity realtime video communication systems, where the encoder is limited in storage and computing resources and the use of the feedback channel must not incur accumulated receiver playback delay. We propose a simple online statistical model that captures the time-varying video process and develop a general framework that explores how to best utilize the feedback and distributed source coding mechanisms to minimize the overall communication rate. Our analysis and experimental results validate the efficiency of the proposed system and highlight its potential in practical system design.

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 Θ̂ satisfying ||Θ̂ - Θ||∞-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.

In this work we study the problem of key agreement over a public noiseless channel when Alice, Bob and Charlie observe discrete memoryless sources of an unknown distribution. Alice and Bob want to agree on a key KABthat is protected from Charlie. At the same time, Alice and Charlie want to agree on a key KACthat is protected from Bob. In order to construct codebooks for the key agreement, Alice has to know how the sources are distributed. Therefore, she requests Bob and Charlie to send her sufficient information about their observations. We also assume that Bob and Charlie, besides agreeing with Alice on the keys, want to learn as much as possible about the other user's key: we call this quantity the leakage. We model these reports by having Bob and Charlie select discrete memoryless channels and passing their true observations through them. We approach this problem from a game-theoretic point of view. For a class of Bob and Charlie's objective functions which are linear in the key rate and the leakage rate, we characterize a Nash equilibrium. Also, we propose a strategy that Alice can apply in order to ensure that Bob and Charlie's honest reporting is a Nash equilibrium.

We address the problem of securing distributed storage systems against passive eavesdroppers that can observe a limited number of storage nodes. An important aspect of these systems is node failures over time, which demand a repair mechanism aimed at maintaining a targeted high level of system reliability. If an eavesdropper observes a node that is added to the system to replace a failed node, it will have access to all the data downloaded during repair, which can potentially compromise the entire information in the system.We are interested in determining the secrecy capacity of distributed storage systems under repair dynamics, i.e., the maximum amount of data that can be securely stored and made available to a legitimate user without revealing any information to any eavesdropper. We derive a general upper bound on the secrecy capacity and show that this bound is tight for the bandwidth-limited regime which is of importance in scenarios such as peer-to-peer distributed storage systems. We also provide a simple explicit code construction that achieves the capacity for this regime.

In the distributed storage setting that we consider, data is stored across n nodes in the network such that the data can be recovered by connecting to any subset of k nodes. Additionally, one can repair a failed node by connecting to any d nodes while downloading β units of data from each. Dimakis et al. show that the repair bandwidth dβ can be considerably reduced if each node stores slightly more than the minimum required and characterize the tradeoff between the amount of storage per node and the repair bandwidth. In the exact regeneration variation, unlike the functional regeneration, the replacement for a failed node is required to store data identical to that in the failed node. This greatly reduces the complexity of system maintenance. The main result of this paper is an explicit construction of codes for all values of the system parameters at one of the two most important and extreme points of the tradeoff the Minimum Bandwidth Regenerating point, which performs optimal exact regeneration of any failed node. A second result is a non-existence proof showing that with one possible exception, no other point on the tradeoff can be achieved for exact regeneration.

We consider the problem of securing a distributed storage system with decentralized data, where some of the nodes are compromised by an eavesdropper. The system is formed of n storage nodes among which k nodes (k <; n) have information sources. The system is required to have the “MDS property”, i.e., to allow any user to recover all the sources by contacting any k nodes. To achieve this goal, the source nodes need to disseminate their data to the other nodes in the system while revealing no information to the eavesdropper. We investigate the role of interaction between the sources in reducing the total required bandwidth. When the sources are independent, we show that interaction does not help and that there always exists an optimal non-interactive scheme.

The high repair cost of (n, k) Maximum Distance Separable (MDS) erasure codes has recently motivated a new class of codes, called Regenerating Codes, that optimally trade off storage cost for repair bandwidth. In this paper, we address bandwidth-optimal (n, k, d) Exact-Repair MDS codes, which allow for any failed node to be repaired exactly with access to arbitrary d survivor nodes, where k ≤ d ≤ n - 1. Under scalarlinear codes which do not permit symbol-splitting, we construct Exact-Repair MDS codes that are optimal in repair bandwidth for the case of k/n ≤ 1/2 and d ≥ 2k - 1. Our codes are deterministic and require a finite-field size of at most 2(n - k). Under vector-linear codes which allow for the break-up of stored symbols into arbitrarily small subsymbols, we show the existence of optimal Exact-Repair codes for the entire admissible range of possible (n, k, d), i.e., k ≤ n and k ≤ d ≤ n - 1. That is, we establish the existence of vector-linear Exact-Repair MDS codes that match the fundamental cutset lower bound. Our approach for both the constructive scalar-linear code design and for the existence of vector-linear codes is based on interference alignment techniques.

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+ 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.

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 communicatefunctionsof 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.

In the above titled paper (ibid., vol. 52, no. 7, pp. 2986-3002, Jul. 06), there is an error on line 8 in the first paragraph on the left column on page 2992 regarding broadcast channels. The equation is not correct and thus the argument given in the rest of the paragraph is not valid. A correct argument is presented here.

We study the information-theoretic limits of exactly recovering the support set 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 observationsn, the ambient signal dimensionp, and the signal sparsitykare 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 (including non-Gaussian) dense measurement matrices. Combined with previously known sufficient conditions, this result yields sharp characterizations of when the optimal decoder can recover a signal for various scalings of the signal sparsitykand sample sizen, including the important special case of linear sparsity(k= ¿(p)) using a linear scaling of observations(n= ¿(p)). Our second contribution is to prove necessary conditions on the number of observationsnrequired for asymptotically reliable recovery using a class of¿-sparsified measurement matrices, where the measurement sparsity parameter¿(n,p,k) ¿ (0,1] corresponds to the fraction of nonzero entries per row. Our analysis allows general scaling of the quadruplet(n,p,k, ¿) , and reveals three different regimes, corresponding to whether measurement sparsity has no asymptotic effect, a minor effect, or a dramatic effect on the information-theoretic limits of the subset recovery problem.

We investigate a practical approach to solving one instantiation of a distributed hypothesis testing problem under severe rate constraints that shows up in a wide variety of applications such as camera calibration, biometric authentication and video hashing: given two distributed continuous-valued random sources, determine if they satisfy a certain Euclidean distance criterion. We show a way to convert the problem from continuous-valued to binary-valued using binarized random projections and obtain rate savings by applying a linear syndrome code. In finding visual correspondences, our approach uses just 49% of the rate of scalar quantization to achieve the same level of retrieval performance. To perform video hashing, our approach requires only a hash rate of 0.0142 bpp to identify corresponding groups of pictures correctly.

Video file synchronization between remote users is an important task in many applications. Re-transmission of a video that has been only slightly modified is expensive, wasteful and avoidable. We propose a scheme that automatically detects and sends only modified content according to some user defined distortion constraint to enable rate savings under a wide range of video edits. Through the use of a low-rate hierarchical hashing scheme, we can detect modifications with some spatial granularity. We also apply distributed source coding techniques to exploit correlation between remote copies for a further rate rebate. Experimental results show that the proposed approach achieves up to 7times rate reduction when compared to re-transmitting.

We consider the design of a low-complexity video encoder in a scenario where an unconstrained receiver can help the encoder reduce complexity by exploiting feedback. To aid us in making design choices, we propose a simple model for video data that captures key properties of the temporal correlation between video frames and the predictability of motion vectors. Our analysis identifies the strengths and weaknesses of previous approaches and motivates a hybrid approach in which the decoder sends motion information to reduce motion estimation workload, the encoder uses incremental distributed source coding on the blocks with poor motion estimates, and the decoder performs decoder motion search and requests additional bits when necessary. Under the model, our analysis shows that such a hybrid scheme outperforms prior approaches. Experimental results of comparable implementations indicate that the hybrid scheme, while not fully implemented, is very promising in practice.

The throughput of Peer-to-Peer (P2P) Video-on-Demand (VoD) systems is typically capped by the users' aggregate upload bandwidth [1]. The drastic increase in the popularity of VoD and the demand of higher quality content has thus placed substantial burden on the content servers. We investigate a novel P2P VoD architecture that leverages idle Internet resources, which we call helpers, to provide a scalable solution to P2P VoD systems. Helpers are volatile in nature, and can be individually unreliable. However, we investigate the statistical aggregation of a large number of helpers to guarantee quality of service. Since helpers do not come with ¿free¿ preloaded content, trade-offs between how much a helper should download and how much it can aid the system need to be explored. In this paper, the optimal steady-state design parameters are derived to maximize the helpers' upload bandwidth utilization. Packet level simulations have verified the efficiency of the system. In a typical scenario of 240 users and a required theoretical minimum of 120 helpers with an average upload bandwidth of 256 kbps, a streaming rate of 384 kbps can be sustained with < 2% relative server load. Results also show that the system is robust to helper churn.

Confidential communication aided by a relay without security clearance is studied. General strategies and outer bounds are derived for the problem of secret communication and secret key generation when correlated observations at all terminals are available. In a variation of the problem, it is assumed that the quality of the channel to the relay is known only to the relay. If the throughput-maximizing strategy is used according to the relay's claimed channel quality, the question is: what should the relay claim about the channel in order to maximize its eavesdropping capabilities? We propose a strategy that Alice and Bob may agree on in order to suppress any leakage of confidential communication between the source and the receiver.

We propose a decentralized Peer-to-Peer (P2P) Video-on-Demand (VoD) system. The traditional data center architecture is eliminated and is replaced by a large set of distributed, dynamic and individually unreliable helpers. The system leverages the strength of numbers to effect reliable cooperative content distribution, removing the drawbacks of conventional data center architectures including complexity of maintenance, high power consumption and lack of scalability. In the proposed VoD system, users and helper ldquoserveletsrdquo cooperate in a P2P manner to deliver the video stream. Helpers are preloaded with only a small fraction of parity coded video data packets, and form into swarms each serving partial video content. The total number of helpers is optimized to guarantee high quality of service. In cases of helper churn, the helper network is also able to regenerate itself by users and helpers working cooperatively to repair the lost data, which yields a highly reliable system. Analysis and simulation results corroborate the feasibility and effectiveness of the proposed architecture.

This paper presents a practical method for using multi-antenna radios to cancel interference in cognitive radio systems. Under this method, secondary radio transmitters use beamforming techniques to find antenna weights that place nulls at the primary receivers, and secondary radio receivers use adaptive techniques to decode in the presence of interference from primary users. As an example, we show how this scheme can be leveraged to effectively reuse the uplink band of a cellular network. However, estimating the channel responses, without causing interference and without requiring significant modifications to legacy systems, is a challenging problem. We provide an iterative method for accurate channel estimation in frequency division duplexed networks, where the uplink is independent of the downlink.

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 "drift" 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.

Peer-to-peer (P2P) video streaming over the Internet plays an important role in reshaping today's Internet traffic. The performance of a P2P system is typically bottlenecked by the limited upload bandwidth of the participating peers, which typically have asymmetric upload/download bandwidth connections to the Internet. Increasing the streaming bitrate in P2P systems beyond what is sustainable with participating peers' upload bandwidths therefore places extra burden on the content server, clearly not a desirable solution in terms of scalability. Motivated by this, we explore here an alternative architecture based on the notion of "helpers", who are online users with spare upload capacity. We show how efficient utilization of helpers' spare upload capacity can lead to significantly improved streaming bitrate in a P2P network without incurring additional server burden. For instance, a 2000 node P2P system with an average upload bandwidth of 512 kbps can sustain streaming rate of 512 kbps with very little server usage. But with an additional 533 helpers, the system can stream at 640 kbps without incurring any additional server load.

We consider the problem of establishing visual correspondences in a distributed and rate-efficient fashion by broadcasting compact descriptors. Establishing visual correspondences is a critical task before other vision tasks can be performed in a wireless camera network. We propose the use of coarsely quantized random projections of descriptors to build binary hashes, and use the Hamming distance between binary hashes as the matching criterion. In this work, we derive the analytic relationship of Hamming distance between the binary hashes to Euclidean distance between the original descriptors. We present experimental verification of our result, and show that for the task of finding visual correspondences, sending binary hashes is more rate-efficient than prior approaches.

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.

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.

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.

VSYNC is a novel incremental video file synchronization system that efficiently synchronizes two video files at remote ends through a bi-directional communications link. Retransmission of a video file that has been modified only slightly, for the purpose of synchronization with a remote-end copy, is extremely expensive but avoidable. VSYNC is a bi-directional algorithm designed to automatically detect and transmit changes in the modified video file without the knowledge of what was changed. Another feature of VSYNC is that it allows synchronization to within some user defined distortion constraint. A hierarchical hashing scheme is designed to compare video chunks, converting the high-level content information to a low-level hash stream that is more amenable to the tools of coding theory. Our approach shows impressive gains in transmission rate-savings. In a typical example of two 12 sec video files with about 10% of the frames being edited, transmission savings of 44% to 87% can be obtained compared to directly sending the updated video files using H.264 and rsync [1].

We present a compressed domain scheme that is able to recognize and localize actions at high speeds. The recognition problem is posed as performing an action video query on a test video sequence. Our method is based on computing motion similarity using compressed domain features which can be extracted with low complexity. We introduce a novel motion correlation measure that takes into account differences in motion directions and magnitudes. Our method is appearance-invariant, requires no prior segmentation, alignment or stabilization, and is able to localize actions in both space and time. We evaluated our method on a benchmark action video database consisting of six actions performed by 25 people under three different scenarios. Our proposed method achieved a classification accuracy of 90%, comparing favorably with existing methods in action classification accuracy, and is able to localize a template video of 80 x 64 pixels with 23 frames in a test video of 368 x 184 pixels with 835 frames in just 11 s, easily outperforming other methods in localization speed. We also perform a systematic investigation of the effects of various encoding options on our proposed approach. In particular, we present results on the compression-classification tradeoff, which would provide valuable insight into jointly designing a system that performs video encoding at the camera front-end and action classification at the processing back-end.

We present a framework for compressing encrypted media, such as images and videos. Encryption masks the source, rendering traditional compression algorithms ineffective. By conceiving of the problem as one of distributed source coding, it has been shown in prior work that encrypted data are as compressible as unencrypted data. However, there are two major challenges to realize these theoretical results. The first is the development of models that capture the underlying statistical structure and are compatible with our framework. The second is that since the source is masked by encryption, the compressor does not know what rate to target. We tackle these issues in this paper. We first develop statistical models for images before extending it to videos, where our techniques really gain traction. As an illustration, we compare our results to a state-of-the-art motion-compensated lossless video encoder that requires unencrypted video input. The latter compresses each unencrypted frame of the ldquoForemanrdquo test sequence by 59% on average. In comparison, our proof-of-concept implementation, working on encrypted data, compresses the same sequence by 33%. Next, we develop and present an adaptive protocol for universal compression and show that it converges to the entropy rate. Finally, we demonstrate a complete implementation for encrypted video.

The problem of transmitting a Gaussian source with memory to a digital and a linear-analog receiver, over an arbitrarily colored, nondegraded Gaussian broadcast channel is studied. The main result of this work is a complete characterization of the set of achievable distortion pairs at the two receivers given a power constraint at the transmitter. Further, a constructive hybrid uncoded-coded scheme consisting of the cascade of source coding with side information and channel coding with side information systems is shown to achieve the entire power-mean squared error (MSE) distortion region associated with the problem. An interesting operating point in this region is one where the digital receiver obtains the classical point-to-point optimal quality and the analog receiver attains the best possible simultaneously achievable distortion. This problem is motivated by the practical application of the seamless ldquoin-bandrdquo digital upgrade of legacy analog transmission systems.

We consider video sequences that have been encrypted uncompressed. Since encryption masks the source, traditional data compression algorithms are rendered ineffective. However, it has been shown that through the use of distributed source-coding techniques, the compression of encrypted data is in fact possible. This means that it is possible to reduce data size without requiring that the data be compressed prior to encryption. Indeed, under some reasonable conditions, neither security nor compression efficiency need be sacrificed when compression is performed on the encrypted data (Johnson et al., 2004). In this paper we develop an algorithm for the practical lossless compression of encrypted gray scale video. Our method is based on considering the temporal correlations in the video. This move to temporal dependence builds on our previous work on memoryless sources, and one- and two-dimensional Markov sources. For comparison, a motion-compensated lossless video encoder can compress each unencrypted frame of the standard "Foreman" test video sequence by about 57%. Our algorithm can compress the same frames, after encryption, by about 33%

We study the problem of reducing power during data-retention in a standby static random access memory (SRAM). For successful data-retention, the supply voltage of an SRAM cell should be greater than a critical data retention voltage (DRV). Due to circuit parameter variations, the DRV for different cells on the same chip exhibits variation with a distribution having diminishing tail. For reliable data retention, the existing low-power design uses a worst-case technique in which a standby supply voltage that is larger than the highest DRV among all cells in an SRAM is used. Instead, our approach uses aggressive voltage reduction and counters the ensuing unreliability through a fault-tolerant memory architecture. The main results of this work are as follows: (i) We establish fundamental bounds on the power reduction in terms of the DRV-distribution using techniques from information theory. For the DRV-distribution of test-chip in (Qin, H, et al., 2006), we show that 49% power reduction with respect to (w.r.t.) the worst-case is a fundamental lower bound while 40% power reduction w.r.t. the worst-case is achievable with a practical combinatorial scheme, (ii) We study the power reduction as a function of the block-length for low-latency codes since most applications using SRAM are latency constrained. We propose a reliable memory architecture based on the Hamming code for the next test-chip implementation with a predicted power reduction of 33% while accounting for coding overheads.

We propose a method for delivering error-resilient video from wireless camera networks in a distributed fashion over lossy channels. Our scheme is based on distributed source coding that exploits inter-view correlation among cameras with overlapping views. The main focus in this work is on robustness which is imminently needed in a wireless setting. The proposed approach has low encoding complexity, is robust while satisfying tight latency constraints, and requires no inter-camera communication. Our system is built on and is a multi-camera extension of PRISM[1], an earlier proposed single-camera distributed video compression system. Decoder motion search, a key attribute of single-camera PRISM, is extended to the multi-view setting by using estimated scene depth information when it is available. In particular, dense stereo correspondence and view synthesis are utilized to generate side-information. When combined with decoder motion search, our proposed method can be made insensitive to small errors in camera calibration, disparity estimation and view synthesis. In experiments over a simulated wireless channel, the proposed approach achieves up to 2.1 dB gain in PSNR over a system using H.263+ with forward error correction.

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.

Consider a large-scale wireless sensor network measuring compressible data, where n distributed data values can be well-approximated using only k « n coefficients of some known transform. We address the problem of recovering an approximation of the n data values by querying any L sensors, so that the reconstruction error is comparable to the optimal k-term approximation. To solve this problem, we present a novel distributed algorithm based on sparse random projections, which requires no global coordination or knowledge. The key idea is that the sparsity of the random projections greatly reduces the communication cost of pre-processing the data. Our algorithm allows the collector to choose the number of sensors to query according to the desired approximation error. The reconstruction quality depends only on the number of sensors queried, enabling robust refinable approximation.

The authors study leakage-power reduction in standby random access memories (SRAMs) during data-retention. An SRAM cell requires a minimum critical supply voltage (DRV) above which it preserves the stored-bit reliably. Due to process-variations, the intra-chip DRV exhibits variation with a distribution having a diminishing tail. In order to minimize leakage power while preserving data reliably, existing low-power design methods use a worst-case standby supply voltage. This worst-case voltage is larger than the highest DRV among all cells in an SRAM. In contrast, the approach uses aggressive voltage reduction and counters the ensuing unreliability by an error-control code based memory architecture. Using this approach, we explore fundamental trade-offs between power reduction and redundancy present in the SRAM. The authors establish fundamental bounds on the power reduction in terms of the DRV-distribution using techniques from information theory and algebraic coding theory. For an experimental test-chip DRV-distribution in the 90nm CMOS technology, the authors show that 49% power reduction with respect to (w.r.t.) the worst-case is a fundamental lower bound while 40% power reduction w.r.t. the worst-case is achievable by using a practical algebraic coding scheme. The authors also study the power reduction as a function of the block-length for low-latency codes since most applications using SRAM are latency constrained. The authors propose a reliable low-power memory architecture based on the Hamming code for the next test-chip implementation with a predicted power reduction of 33% while accounting for coding overheads

We study a problem motivated by cognitive radio in which the primary is a packet system that employs ARQ feedback. A secondary system is allowed to transmit in the same frequency band provided it ensures that the primary attains a specified target rate. That is, the secondary has a certain "interference budget". The crux of the problem is that the secondary does not know how much interference it creates on the primary and therefore is ignorant of its interference budget. Absent this knowledge, we propose a scheme in which the secondary eavesdrops on the primary's ARQ and uses this knowledge to stay within its interference budget. Under certain assumptions, we show there exists an optimal rate-interference budget (RIB) tradeoff. We compare how far fixed strategies are from this RIB function as we vary the interference budget. Further, we exhibit a strategy that is optimal beyond a threshold interference budget and within 1 bit per primary packet elsewhere.

In this paper we study channels where a side-information sequence is available strictly causally at the transmitter, i.e., the channel input at time k may depend on the side-information sequence up to and including time k - 1. This is in contrast to Shannon's channel coding with causal side-information at the transmitter where the channel input at time k may depend on the side-information sequence up to and including time k. We consider side-information sequences with memory and study the Gaussian and modulo-additive channels.

We address the problem of robust low-delay video multicast over wireless networks and propose an MPEG/H.26x compatible receiver-driven multicast system. Distributed source coded (DSC) data and forward error correction (FEC) coded parity data are sent to different multicast groups. Heterogeneous receivers with different bandwidth and channel conditions can dynamically switch between subscribing to FEC multicast group(s) and DSC multicast group(s) to enhance the quality of decoded video based on their individual decoding status. Simulations show that this approach has advantages over pure-FEC based schemes and random intra-refresh, especially when the delay constraint is stringent and the transmission channel loss has a bursty nature, as is true in wireless channels.

The automated extraction of semantically meaningful information from multi-modal data is becoming increasingly necessary due to the escalation of captured data for archival. A novel area of multi-modal data labelling, which has received relatively little attention, is the automatic estimation of the most dominant person in a group meeting. In this paper, we provide a framework for detecting dominance in group meetings using different audio and video cues. We show that by using a simple model for dominance estimation we can obtain promising results.

Given a large collection of videos containing activities, we investigate the problem of organizing it in an unsupervised fashion into a hierarchy based on the similarity of actions embedded in the videos. We use spatio-temporal volumes of filtered motion vectors to compute appearance-invariant action similarity measures efficiently - and use these similarity measures in hierarchical agglomerative clustering to organize videos into a hierarchy such that neighboring nodes contain similar actions. This naturally leads to a simple automatic scheme for selecting videos of representative actions (exemplars) from the database and for efficiently indexing the whole database. We compute a performance metric on the hierarchical structure to evaluate goodness of the estimated hierarchy, and show that this metric has potential for predicting the clustering performance of various joining criteria used in building hierarchies. Our results show that perceptually meaningful hierarchies can be constructed based on action similarities with minimal user supervision, while providing favorable clustering performance and retrieval performance.

We investigate the design of fountain codes with good intermediate performance and built-in unequal error protection for low-delay video multicast. In particular, we design novel short-blocklength fountain codes for media streaming applications to multiple heterogeneous receivers and analyze their performance. Our theoretical contribution is the generalization of the growth code analysis for unequal error protection to suit the characteristics of video data. Simulation results show that the proposed method can effectively increase the number of decodable packets over a very wide range of packet drop rates and provide smooth and graceful video quality degradation for users with various channel conditions. The proposed scheme also enjoys the important benefits of much lower decoder complexity and simpler system architecture compared to traditional MDS erasure coding based solutions.

Recently, a new class of distributed source coding (DSC) based video coders has been proposed to enable low-complexity encoding. However, to date, these low-complexity DSC-based video encoders have been unable to compress as efficiently as motion-compensated predictive coding based video codecs, such as H.264/AVC, due to insufficiently accurate modeling of video data. In this work, we examine achieving H.264-like high compression efficiency with a DSC-based approach without the encoding complexity constraint. The success of H.264/AVC highlights the importance of accurately modeling the highly non-stationary video data through fine-granularity motion estimation. This motivates us to deviate from the popular approach of approaching the Wyner-Ziv bound with sophisticated capacity-achieving channel codes that require long block lengths and high decoding complexity, and instead focus on accurately modeling video data. Such a DSC-based, compression-centric encoder is an important first step towards building a robust DSC-based video coding framework.

We propose a novel method of exploiting inter-view correlation among cameras that have overlapping views in order to deliver error-resilient video in a distributed multi-camera system. The main focus in this work is on robustness which is imminently needed in a wireless setting. Our system has low encoding complexity, is robust while satisfying tight latency constraints, and requires no inter-sensor communication. In this work, we build on and generalize PRISM [Puri2002], an earlier proposed single-camera distributed video compression system. Specifically, decoder motion search, a key attribute of single-camera PRISM, is extended to the multi-view setting to include decoder disparity search based on two-view camera geometry. Our proposed system, dubbed PRISM-MC (PRISM multi-camera), achieved PSNR gains of up to 1.7 dB over a PRISM based simulcast solution in experiments over a wireless channel simulator.

We describe PRISM, a video coding paradigm based on the principles of lossy distributed compression (also called source coding with side information or Wyner-Ziv coding) from multiuser information theory. PRISM represents a major departure from conventional video coding architectures (e.g., the MPEGx, H.26x families) that are based on motion-compensated predictive coding, with the goal of addressing some of their architectural limitations. PRISM allows for two key architectural enhancements: (1) inbuilt robustness to "drift" between encoder and decoder and (2) the feasibility of a flexible distribution of computational complexity between encoder and decoder. Specifically, PRISM enables transfer of the computationally expensive video encoder motion-search module to the video decoder. Based on this capability, we consider an instance of PRISM corresponding to a near reversal in codec complexities with respect to today's codecs (leading to a novel light encoder and heavy decoder paradigm), in this paper. We present encouraging preliminary results on real-world video sequences, particularly in the realm of transmission losses, where PRISM exhibits the characteristic of rapid recovery, in contrast to contemporary codecs. This renders PRISM as an attractive candidate for wireless video applications.

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.

We propose a distributed multiresolution representation of sensor network data so that large-scale summaries are readily available by querying a small fraction of sensor nodes, anywhere in the network, and small-scale details are available by querying a larger number of sensors, locally in the region of interest. A global querier (such as a mobile collector or unmanned aerial vehicle) can obtain a lossy to lossless representation of the network data, according to the desired resolution. A local querier (such as a sensor node) can also obtain either large-scale trends or local details, by querying its immediate neighborhood. We want the encoding to be robust to arbitrary, even time-varying, wireless communication connectivity graphs. Thus we want to avoid cluster heads or deterministic hierarchies that are not robust to single points of failure. We propose a randomized encoding which enables both robustness, and distributed computation that does not require long distance coordination or awareness of network connectivity at individual sensors. Our distributed encoding algorithm operates on local neighborhoods of the communication graph

We investigate the problem of constructing fountain codes for distributed storage in sensor networks. Specifically, we assume that there are n storage nodes with limited memory and k < n data nodes generating the data by sensing the environment. We want a data collector who can appear anywhere in the network, to query any k + epsi storage nodes and be able to retrieve almost all the data packets. We demonstrate how it is possible to solve this problem by using a specific kind of fountain code that requires only linear communication and decoding complexity. Further, for a grid topology, we propose a randomized algorithm that constructs the fountain code over a network using only geographical knowledge and local decisions. A key step in the analysis of our algorithm is a novel result concerning random walks on finite grids with traps

Coding schemes for secure and efficient communication over noiseless public channels traditionally compress and then encrypt the source data. In some cases reversing the ordering of compression and encryption would be useful, e.g., in enabling the efficient distribution of protected media content. Indeed, not only is it possible to reverse the order, but under some conditions neither security nor compression efficiency need be sacrificed. In earlier work on this problem we have assumed that the source data is either memoryless or has a 1-D Markov structure. Such models are poor matches for the 2-D structure of images. In this work, we use a 2-D source model, and develop a scheme to compress encrypted images based on LDPC codes. We present practical simulation results for compressing bi-level images. In tests, we are able to compress an encrypted 10, 000 bit bi-level image to 4, 299 bits and successfully recover the image exactly. In previous works, the best analogous 1-D model (operating on a raster scanned data sequence of the same source) could only compress the image to 7, 710 bits.

This paper addresses the problem of low-latency robust video delivery over packet networks characterized by a bursty loss process. We propose a joint source-channel coding based video codec which uses distributed source coding (DSC) principles. This codec can efficiently tune to both the source content as well as to the network loss characteristics while respecting stringent latency constraints. Simulation results show that the proposed system is both objectively (in PSNR) and subjectively (visual quality) superior to predictive video coding systems where the encoded bitstream is protected with forward error correction (FEC) codes.

We consider the problem of spatio-temporal resolution enhancement of a dynamic video scene by synergistically combining information from multiple video sequences corresponding to the different views of the scene. While prior work has focused on spatio-temporal superresolution by primarily exploiting the blurring correlation induced by the scene imaging process, in this work we exploit another and perhaps a stronger form of correlation the intrinsic correlation present in the dynamic scene. We use the knowledge base from the areas of multi-view computer vision, video coding and signal/image processing to efficiently model the dynamic video scene by exploiting inter-camera (space) as well as intra-camera correlations (time). We present simulation results corresponding to a lowframe rate two-camera stereo video configuration where the sequences are combined to generate higher frame-rate sequences. Our proposed framework has direct application to problems such as multi-view video surveillance and relates closely to problems such as multi-view video compression.

We propose random distributed multiresolution representations of sensor network data, so that the most significant encoding coefficients are easily accessible by querying a few sensors, anywhere in the network. Less significant encoding coefficients are available by querying a larger number of sensors, local to the region of interest. Significance can be defined in a multiresolution way, without any prior knowledge of the source data, as global summaries versus local details. Alternatively, significance can be defined in a data-adaptive way, as large differences between neighboring data values. We propose a distributed encoding algorithm that is robust to arbitrary wireless communication connectivity graphs, where links can fail or change with time. This randomized algorithm allows distributed computation that does not require strict global coordination or awareness of network connectivity at individual sensors. Because computations involve sensors in local neighborhoods of the communication graph, they are communication-efficient. Our framework uses local interaction among sensors to enable flexible information retrieval at the global level.

In this paper, we address the case of a single remote sensing unit (encoder), a central processing unit (decoder), and a finite bitrate constraint as an abstraction of a bandwidth-limited channel between the encoder and decoder. The goal is to spend this bit budget in an optimal sense, in terms of classification or estimation performance (minimize the probability of classification error or minimize the probability that the parameter estimation error exceeds a desired tolerance) while ensuring the reconstruction of the raw data with maximum fidelity (in a rate-distortion sense)

We present a compressed domain scheme that is able to recognize and localize actions in real-time. The recognition problem is posed as performing a video query on a test video sequence. Our method is based on computing motion similarity using compressed domain features which can be extracted with low complexity. We introduce a novel motion correlation measure that takes into account differences in motion magnitudes. Our method is appearance invariant, requires no prior segmentation, alignment or stabilization, and is able to localize actions in both space and time. We evaluated our method on a large action video database consisting of 6 actions performed by 25 people under 3 different scenarios. Our classification results compare favorably with existing methods at only a fraction of their computational cost

In this correspondence, we consider the problem of constructing an erasure code for storage over a network when the data sources are distributed. Specifically, we assume that there are n storage nodes with limited memory and k

The drive toward the implementation and massive deployment of wireless sensor networks calls for ultralow-cost and low-power nodes. While the digital subsystems of the nodes are still following Moore's Law, there is no such trend regarding the performance of analog components. This work proposes a fully integrated architecture of both digital and analog components (including local oscillator) that offers significant reduction in cost, size, and overall power consumption of the node. Even though such a radical architecture cannot offer the reliable tuning of standard designs, it is shown that by using random network coding, a dense network of such nodes can achieve throughput linear in the number of channels available for communication. Moreover, the ratio of the achievable throughput of the untuned network to the throughput of a tuned network with perfect coordination is shown to be close to 1/e. This work uses network coding to leverage the fact that throughput equal to the max-flow in a graph is achievable even if the topology is not know a priori. However, the challenge here is finding the max-flow of the random graph corresponding to the network.

In this paper, we address duality in a variety of multiuser source and channel coding problems under different scenarios of "one-sided" inter-terminal collaboration at either the transmitter or at the receiver. First we consider duality between broadcast channel coding and distributed source coding problems. We also consider a new source coding problem in this paper, which we refer to as distributed reconstruction source coding. This problem is closely related to the multiple description source coding problem. We then consider duality between this problem and the multiple access channel coding problem. Our notion of duality in this paper is in a functional sense, where the optimal encoder mapping for a multiuser source coding problem becomes identical to the optimal decoder mapping for the dual multiuser channel coding problem, and vice versa. For ease of illustration we give the formulation only for systems which involve either two encoders or two decoders. Our formulation can be easily extended to the multiuser (more than two noncollaborating terminals) case. We present the precise mathematical conditions under which these encoder-decoder mappings are swappable in the two dual multiuser communication problems, identifying the key roles played by the source distortion and channel cost measures respectively in the multiuser source and channel coding problems in capturing this duality.

We study the problem of enhancing a baseline standards-compliant video-over-wireless broadcast system through the use of an auxiliary wireless broadcast channel. Our proposed solution is based on the information-theoretic concept of broadcast source coding which subsumes the concept of source coding with side-information. We integrate into this framework an analytically tractable mechanism for dynamically incorporating channel loss. Empirical validation of our proposed algorithm on a typical 3G wireless network broadcast channel simulator reveals its superior performance over pure FEC-based solutions by an average of 2-4 dB in PSNR.

In this work, we analytically study the complexity-performance trade-offs associated with video codecs based on the principle of source coding with side information at the decoder. We address three important aspects. First, we quantify the theoretical performance gains attained with side-information based codecs over prediction-based coders like MPEG under a lossy transmission scenario when there is drift. Secondly, we show that it is possible to closely approach MPEG's compression performance using side-information video coding principles with accurate DFD (displaced frame difference) modeling even without sophisticated channel codes. Thirdly, we analytically show that the value of accurately estimating DFD statistics diminishes as the channel gets noisier.

Consider a large-scale wireless sensor network of n nodes, where a fraction k out of n generate data packets of global interest. Assuming that the individual nodes have limited storage and computational capabilities, we address the problem of how to enable ubiquitous access to the distributed data packets. Specifically, we assume that each node can store at most one data packet, and study the problem of diffusing the data so that by querying any k nodes, it is possible to retrieve all the k data packets of interest (with high probability). We introduce a class of erasure codes and show how to solve this problem efficiently in a completely distributed and robust way. Specifically we show that we can efficiently diffuse the data by "pre-routing" only O(ln n) packets per data node to randomly selected storage nodes. By using the proposed scheme, the distributed data becomes available "at the fingertips" of a potential data collector located anywhere in the network.

If a signal x is known to have a sparse representation with respect to a frame, the signal can be estimated from a noise-corrupted observation y by finding the best sparse approximation to y. This paper analyzes the mean squared error (MSE) of this denoising scheme and the probability that the estimate has the same sparsity pattern as the original signal. The first main result is an MSE bound that depends on a new bound on approximating a Gaussian signal as a linear combination of elements of an overcomplete dictionary. This bound may be of independent interest for source coding. Further analyses are for dictionaries generated randomly according to a spherically-symmetric distribution and signals expressible with single dictionary elements. Easily-computed approximations for the probability of selecting the correct dictionary element and the MSE are given. In the limit of large dimension, these approximations have simple forms. The asymptotic expressions reveal a critical input signal-to-noise ratio (SNR) for signal recovery

We study the problem of estimating a physical process at a central processing unit (CPU) based on noisy measurements collected from a distributed, bandwidth-constrained, unreliable, network of sensors, modeled as an erasure network of unreliable "bit-pipes" between each sensor and the CPU. The CPU is guaranteed to receive data from a minimum fraction of the sensors and is tasked with optimally estimating the physical process under a specified distortion criterion. We study the noncollaborative (i.e., fully distributed) sensor network regime, and derive an information-theoretic achievable rate-distortion region for this network based on distributed source-coding insights. Specializing these results to the Gaussian setting and the mean-squared-error (MSE) distortion criterion reveals interesting robust-optimality properties of the solution. We also study the regime of clusters of collaborative sensors, where we address the important question: given a communication rate constraint between the sensor clusters and the CPU, should these clusters transmit their "raw data" or some low-dimensional "local estimates"? For a broad set of distortion criteria and sensor correlation statistics, we derive conditions under which rate-distortion-optimal compression of correlated cluster-observations separates into the tasks of dimension-reducing local estimation followed by optimal distributed compression of the local estimates.

In many multiterminal communication problems, constructions of good source codes involve finding distributed partitions (into bins) of a collection of quantizers associated with a group of source encoders. Further, computationally efficient procedures to index these bins are also required. In this work, we consider a constructive approach for distributed binning in an algebraic framework. Several application scenarios fall under the scope of this paper including the CEO problem, distributed source coding, and n-channel symmetric multiple description source coding with n>2. Specifically, in this exposition we consider the case of two codebooks while focusing on the Gaussian CEO problem with mean squared error reconstruction and with two symmetric observations. This problem deals with distributed encoding of correlated noisy observations of a source into descriptions such that the joint decoder having access to them can reconstruct the source with a fidelity criterion. We employ generalized coset codes constructed in a group-theoretic setting for this approach, and analyze the performance in terms of distance properties and decoding algorithms.

In this Part II of a two-part paper, we present a new achievable rate-distortion region for the symmetric n-channel multiple-descriptions coding problem (n>2) where the rate of every description is the same, and the reconstruction distortion depends only on the number of descriptions received. Using a new approach for the random coding constructions, along with a generalization of the technique used in the two-channel El Gamal and Cover region to any n, the rate region presented here achieves points that have not been known in the literature previously. This rate region is derived from a concatenation of source-channel erasure codes developed in Part I of this work by deploying the framework of source coding with side information ("random binning"). The key idea is that by using the framework of source coding with side information, multiple statistically identical realizations representing the coarse version of a source can be simultaneously refined by a single encoding. We point out that there is an important conceptual difference in random coding construction for the multiple-descriptions coding problem between the case of n=2 and n>2. To illustrate the framework, we also present the important case of the Gaussian source in detail.

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.

Slepian-Wolf coding tackles the problem of distributed encoding of correlated discrete-alphabet sources for decoding at a common receiver. In this work, we propose a distributed linear block code construction for attaining any point on the Slepian-Wolf achievable rate region for arbitrarily correlated sources using only a single code. 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 in the proposed framework to solve the general Slepian-Wolf problem constructively.

Distributed sampling and reconstruction of a physical field using an array of sensors is a problem of increasing interest in environmental monitoring applications of sensor networks. We show, using a dither-based scheme, that it is possible to reconstruct non-bandlimited fields with a reconstruction accuracy that depends on the available bitrate R and the spectral decay characteristics of the sensor field - we study exponentially decaying spectra as an illustration. For bandlimited fields f(t), the maximum pointwise error D/sub f/ decays as D/sub f/ /spl sim/ 2/sup -a1R/, i.e. exponentially with rate R. For the non-bandlimited case, we show that for fields u(t) with exponentially decaying spectral tails, i.e., |U(/spl omega/)|/spl sim/e/sup -a|/spl omega/|/, the maximum pointwise error D/sub u/ decays as D/sub u//spl sim/e/sup -a2/spl radic/R/(1+o(R)) with spatial bit rate R bits/metre. We also show that it is possible to trade off the number of sensors with their precision, while maintaining a similar reconstruction accuracy - a phenomenon that may be dubbed as a "bit-conservation" principle underlying the sampling framework.

This paper presents an adaptive approach for conserving energy in high-density sensor networks. The proposed method allows sensor nodes to sleep while ensuring that application performance constraints are met. Unlike deterministic algorithms that assume static connectivity, the approach uses a randomized algorithm to provide robustness to the variations in network connectivity. These variations are due to fading channels, depletion or addition of nodes, node mobility, and the sleeping of nodes. The algorithm developed in the paper is extremely lightweight and does not require nodes to keep any state information about their individual neighbors. Based on local observations, each node independently decides when to sleep and wakeup. The algorithm also ensures an evenly distributed workload among nodes, and achieves energy savings proportional to the density of nodes.

Consider a communication system in which a filtered and quantized signal is sent over a channel with erasures and (potentially) additive noise. Linear MMSE estimation is achieved in such a system by Kalman filtering. Allowing any Markov erasure process and any Markov-state jump linear signal generation model, it is shown that the estimation performance at the receiver can be computed as a deterministic optimization with linear matrix inequality (LMl) constraints rather than a pseudorandom simulation. Furthermore, in contrast to the case without erasures, the filtering in the transmitter should not necessarily be MMSE prediction (whitening); a procedure is given to find a locally optimal prefilter. The main tools are recent LMI characterizations of asymptotic state estimation error covariance and output estimation error variance for discrete-time jump linear systems in which the discrete portion of the system state is a Markov chain. As another application of this framework, a novel analysis and optimization of a "streaming" version of multiple description coding based on subsampling is outlined.

Theoretical analysis of differential predictive coding (DPC) has almost exclusively focused on scalar quantizers and the high-rate regime for tractability reasons. As a result, the role of noncausal decoding in improving the quality has been largely ignored in the literature. In this work we conduct a rigorous performance analysis of DPC-based schemes under a simple independent, vector-Gaussian, AR-1 source model and large-block (as opposed to high-rate) asymptotics. This analysis reveals that noncausal decoding can offer a significant relative improvement in the mean squared error (by as much as 3 dB) at medium to low rates (0.1-0.5 bit per sample) for sources having strong temporal correlation. Furthermore, most of this relative improvement can be attained with a modest decoder-latency. At very high and very low rates, the gains are negligible.

We present an algorithm for robust scalable video multicast based on distributed source coding techniques. Unlike prediction based coders, like MPEG, the proposed framework directly addresses the problem of drift due to packet losses. Building on the recently proposed PRISM video coding framework (R. Puri and K. Ramehandran, 2002), we show that substantial gains are possible for video multicast over lossy channels as compared to standard codecs, without a dramatic increase in encoder complexity as the number of streams increases.

Distributed sampling and reconstruction of a physical field using an array of sensors is a problem of considerable interest in environmental monitoring applications of sensor networks. Our recent work has focused on the sampling of bandlimited sensor fields. However, sensor fields are not perfectly bandlimited but typically have rapidly decaying spectra. In a classical sampling set-up it is possible to precede the A/D sampling operation with an appropriate analog anti-aliasing filter. However, in the case of sensor networks, this is infeasible since sampling must precede filtering. We show that even though the effects of aliasing on the reconstruction cannot be prevented due to the "filter-less" sampling constraint, they can be suitably controlled by oversampling and carefully reconstructing the field from the samples. We show using a dither-based scheme that it is possible to estimate non-bandlimited fields with a precision that depends on how fast the spectral content of the field decays. We develop a framework for analyzing non-bandlimited fields that lead to upper bounds on the maximum pointwise error for a spatial bit rate of R bits/meter. We present results for fields with exponentially decaying spectra as an illustration. In particular, we show that for fields f(t) with exponential tails; i.e., F(ω) ‹ παε–αω, the maximum pointwise error decays as c2e–α1√R+c3 1 over √R e >–2α1√R with spatial bit rate R bits/meter. Finally, we show that for fields with spectra that have a finite second moment, the distortion decreases as O((1 overN)2 over 3) as the density of sensors, N, scales up to infinity . We show that if D is the targeted non-zero distortion, then the required (finite) rate R scales as O (1 over √ overD log 1 over D).

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.

When transmitting a source over an insecure and bandwidth-limited channel, compression (lossy/lossless) precedes encryption. We show that, through the use of side-information coding principles, the order of these operations can be reversed without loss of Wyner-sense perfect secrecy and often with a significant compression ratio. Further, when the source has to be recovered perfectly (with high probability) or is Gaussian (with the mean-squared error fidelity criterion), there is no loss of compression efficiency and the proposed system requires no more randomness in the encryption key compared to systems where compression precedes encryption.

In the so-called CEO problem, a hidden source random process is of interest to a central unit or the "CEO". But this process cannot be observed directly. L sensors or agents observe independently corrupted versions of the source. They encode their observations without cooperating with one another and send through rate constrained noiseless channels to the CEO. The problem was first studied by T. Berger et al. (1996) in the context of discrete memoryless sources. The quadratic Gaussian version of the problem was studied. The best result known to date is the characterization of the sum-rate when all the agents have the same quality of observations. Here we characterize the rate region for any number of agents without assuming that their quality of observations is the same. This is one of the few examples of multiterminal lossy source coding problems in which the rate region can be characterized completely.

In this paper, the multiterminal sources is mapped independently into a message set characterized by a graph which preserves a predetermined amount of correlation between the sources, and the message set becomes the input to channel encoder. In this work joint source-channel coding scheme is considered as a part with associated message graph for transmitting distributed correlated sources over MAC. Thus the parameters are allowed to increase exponentially with number of channels and the performance of this characterized set is measured using minimum average probability of error.

This paper introduces a particular network source coding problem for sensor networks. The problem consists of transmitting information between a set of source-destination pairs over a network where the nodes are correlated. When the underlying graph structure is a tree we give a complete characterization of the achievable rate region and discusses the role of graphical models and in particular the junction tree in determining routing paths for cases where the underlying graph structure has cycles. The communication complexity of learning the statistics of the source from observation data and computing the routing spanning tree in a distributed manner is determined.

Predictive video codecs such as MPEG and H.26x are very susceptible to prediction mismatch between encoder and decoder or "drift" when there are packet losses, leading to a significant reduction in the decoded quality. In this paper, we propose a method to reduce the drift in these codecs by sending extra information over a side-channel. Using principles from distributed source coding, we send another description of the video sequence (at a lower rate) over the side-channel which can correct for errors in the decoded frame and thereby mitigate the drift. Simulation results using our techniques show significant gains in performance over conventional error protection schemes such as Forward Error Correction codes under reasonable latency constraints.

In this two-part paper, we present a new achievable rate region for the general n-channel symmetric multiple descriptions problem. In part I, inspired by the concept of maximum-distance separable (MDS) erasure channel codes, we consider a special case of this rate region, where the source is encoded into n descriptions each with rate R. These descriptions are transmitted over n bandwidth constrained and errorless channels. During transmission, a subset of these channels can break down, thus erasing the corresponding descriptions. The decoder is interested in recovering the source with the reception of at least k descriptions. Thus, the encoder is allowed to sample only one realization of this breakdown process during the entire transmission. For Gaussian sources, we have the following interesting result: when any k descriptions arrive, the achievable distortion exactly matches the optimal distortion-rate performance corresponding to a source rate of kR bits; with the reception of any m > k descriptions, the source reconstruction quality is strictly better, the improvement being nearly linear in the number of descriptions received.

The problem of rate-distortion efficient constructions is studied for the problem of source coding with side information (SCSI), which has assumed heightened interest. While the Wyner-Ziv theorem from information theory has prescribed rate-distortion performance bounds for the SCSI problem, the gap between theory and practice has remained large. To reduce this gap, two different frameworks are proposed based on a trellis construction and a turbo-based construction respectively. Simulation results on the Gaussian SCSI problem reveal the promise of the proposed approaches: at 1 bit per sample, 0.5 bits/sample, 0.25 bits/sample and 0.125 bits/sample, these constructions attain performance within 1.3 dB, 1.1 dB, 0.85 dB and 0.5 dB respectively of the theoretical Wyner-Ziv rate-distortion bound.

There has been a lot of interest recently in applying channel coding with side information (CCSI) concepts to data hiding. Part of the interest stems from the fact that information theoretic bounds can be derived for such systems. In this paper, we model the audio data embedding problem as a parallel CCSI problem. This is done by dividing the audio spectrum into frequency bins and then treating each bin as a separate CCSI channel. A perceptual mask is derived from the audio signal to determine the amount of power to use in each channel. It acts as a "water-filling" formula by determining the amount of distortion that can be introduced into each frequency bin without introducing audible distortion. As a result, our data embedding scheme will be imperceptible to the human ear. An exciting application for our audio data embedding solution is to embed data within the audio signal that will enable surround sound at the receiver. The resulting surround sound system will be better than existing surround sound systems that are based on manipulating two stereo channels to derive the other surround channels.

We consider the problem of low-complexity timing synchronization in digital receivers for DS-CDMA and UWB systems operating over channels with single or multiple propagation paths. We extend some of our recent sampling results for certain classes of non-bandlimited signals and develop a method that takes advantage of transform techniques to perform propagation delay estimation from a low-dimensional subspace of a received signal, that is, by sampling below the traditional Nyquist rate. By lowering the sampling rate we reduce computational requirements compared to existing solutions, allow for slower A/D converters and significantly reduce the power consumption of digital receivers.

In this work, we present PRISM (Power-efficient Robust high-compression Syndrome-based Multimedia coding), a new video coding paradigm based on the principles of distributed source coding. Incurring the low encoding complexity of intra-frame (still-image) video coding, PRISM approaches the high compression efficiency of full-motion inter-frame video coding, while simultaneously offering natural robustness to the drift problem and channel loss in direct contrast to conventional video coding architectures (MPEG and H.26L). These traits make it well-matched to uplink-rich applications such as multimedia over wireless networks, wireless video and sensor cameras, etc.

Despite their simplicity, scalar threshold operators effectively remove additive white Gaussian noise from wavelet detail coefficients of many practical signals. This paper explores the use of multivariate estimators that are almost as simple as scalar threshold operators. Sendur and Selesnick (2002) have recently shown the effectiveness of joint threshold estimation of parent and child wavelet coefficients. This paper discusses analogous results in two situations. With a frame representation, a simple joint threshold estimator is derived and it is shown that its generalization is equivalent to a type of l/sub 1/-regularized denoising. Then, for the case where multiple independent noisy observations are available, the counter-intuitive results by Chang, Yu, and Vetterli (2000) on combining averaging and thresholding are explained as a fortuitous consequence of randomization.

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.

This paper presents an information-theoretic study of video codecs that are based on the principle of source coding with side information at the decoder. In contrast to the classical Wyner-Ziv side-information source coding problem (1976), in this work we address the situation where the source and side-information are connected through a state of nature that is unknown to both the encoder and the decoder. We dub this framework as source encoding with side-information under ambiguous state of nature (SEASON). Our objective is to compare the achievable rate-distortion (R/D) performance of conventional video codecs designed under the motion-compensated predictive coding (MCPC) framework and video codecs designed under the SEASON framework. Our analysis shows that under appropriate motion models and for Gaussian displaced frame difference (DFD) statistics, the R/D performance of a classical MCPC-based video codec is matched by that of our proposed SEASON-based video codec, with the hitter being characterized by the novel concept of moving the motion compensation task from the encoder to the decoder.

We propose an image hashing algorithm that is based on distributed compression principles. The algorithm assumes the availability of a robust feature vector extracted from the image. Then a suitable dither sequence is added to this feature vector, and the resulting dithered feature vector is compressed using distributed compression principles. We prove that the dither sequence can be used to guarantee information-theoretic security. Applications of our proposed secure image hashing scheme include video watermarking, image authentication, and image database management.

In this work, we present PRISM (power-efficient, robust, high-compression, syndrome-based multimedia coding), a video coding paradigm based on the principles of coding with side information (which, unlike the classical Wyner-Ziv coding scenario Wyner, A et al. (1976), is characterized by an ambiguous state of nature characterizing the side-information Ishwar, P et al. (2003)). PRISM's architectural goals are to inherit the low encoding complexity and robustness of motion-JPEG style intra-frame video codecs while approaching the high compression efficiency of full-motion interframe video codecs. The PRISM paradigm roughly swaps the encoder-decoder complexity with respect to conventional video coding architectures through the novel concept of moving the motion compensation task from the encoder to the decoder. These traits make PRISM well-matched to uplink-rich media applications involving wireless video and security cameras, multimedia-equipped phones and PDA's etc.

We propose a novel approach to reducing energy consumption in sensor networks using a distributed adaptive signal processing framework and efficient algorithm. While the topic of energy-aware routing to alleviate energy consumption in sensor networks has received attention recently (C. Toh, 2001; R. Shah et al., 2002), in this paper, we propose an orthogonal approach to previous methods. Specifically, we propose a distributed way of continuously exploiting existing correlations in sensor data based on adaptive signal processing and distributed source coding principles. Our approach enables sensor nodes to blindly compress their readings with respect to one another without the need for explicit and energy-expensive intersensor communication to effect this compression. Furthermore, the distributed algorithm used by each sensor node is extremely low in complexity and easy to implement (i.e., one modulo operation), while an adaptive filtering framework is used at the data gathering unit to continuously learn the relevant correlation structures in the sensor data. Our simulations show the power of our proposed algorithms, revealing their potential to effect significant energy savings (from 10%-65%) for typical sensor data corresponding to a multitude of sensor modalities.

We explore the information-theoretic duality between source coding with side information at the decoder and channel coding with side information at the encoder. We begin with a mathematical characterization of the functional duality between classical source and channel coding, formulating the precise conditions under which the optimal encoder for one problem is functionally identical to the optimal decoder for the other problem. We then extend this functional duality to the case of coding with side information. By invoking this duality, we are able to generalize the result of Wyner and Ziv (1976) relating to no rate loss for source coding with side information from Gaussian to more arbitrary distributions. We consider several examples corresponding to both discrete- and continuous-valued cases to illustrate our formulation. For the Gaussian cases of coding with side information, we invoke geometric arguments to provide further insights into their duality. Our geometric treatment inspires the construction and dual use of practical coset codes for a large class of emerging applications for coding with side information, such as distributed sensor networks, watermarking, and information-hiding communication systems.

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.

We present new achievable rate regions and code constructions for the symmetric n-channel multiple descriptions (MD) coding problem (Puri et al. (2002)) for n>2. Our approach is inspired by unexplored connections between MD and the problem of distributed source coding (Slepian et al. (1973); Wyner et al. (1976)). For illustrative clarity, we restrict our focus to the important special case relating to (n, k) source-channel erasure codes (Pradhan et al. (2001)). This involves n encodings of a source with the goal of maximizing its reconstruction fidelity with the availability of any k of them, while strictly improving this reconstruction fidelity with the availability of more than k descriptions. We describe the underlying information-theoretic framework, and then formulate practical constructions based on scalar quantizers and linear channel codes for the n=3 case to illustrate our concepts.

Connexions is a new approach to authoring, teaching, and learning that aims to fully exploit modern information technology. Available free of charge to anyone under open-content and open-source licenses, Connexions offers custom-tailored, current course material, is adaptable to a wide range of learning styles, and encourages students to explore the links among courses and disciplines. In contrast to the traditional process of textbook writing and publishing, Connexions fosters world-wide, cross-institution communities of authors, instructors, and students, who collaboratively and dynamically fashion “modules” from which courses are constructed. We believe the ideas and philosophy embodied by Connexions have the potential to change the very nature of textbook writing and publishing, producing a dynamic, interconnected educational environment that is pedagogically sound, both time and cost efficient, and fun. This paper overviews the philosophy and technology behind Connexions and describes a nascent community developing material for DSP education.

Channel coding with side information (CCSI) provides a powerful framework for constructing data embedding codes. As a result, there has been a considerable amount of work done in trying to apply these CCSI codes to the field of image and video watermarking. The CCSI codes that exist in the literature however, are relatively far from theoretical bounds. Furthermore, these codes, by themselves, are not well-suited for dealing with geometrical distortions which often appear in watermarking attacks. In this paper we propose a CCSI code that is closer to the theoretical bounds (within 2.0 dB) than the codes that exist in the literature. In addition, we show how this code construction can be combined with a synchronization code to deal with geometrical distortions.

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, R.R. Coifman and D.L. Donoho (see Wavelets and Statistics, Lecture Notes in Statistics, vol.103, p.125-50, 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.

Microarray image technology is a powerful tool for monitoring the expression of thousands of genes simultaneously. Each microarray experiment produces immense amounts of image data, and efficient storage and transmission requires compression that utilizes the microarray image's structure and unique analysis goals. We have developed a progressive compression scheme for microarray images which can be either lossy or lossless. Our scheme has a coded data structure that allows fast decoding and reprocessing of image subsets, and includes summary statistics and image segmentation information. Since visual fidelity is not the end goal for microarray images, we introduce a new measure of distortion for lossy compression: the sensitivity of microarray information extraction to compression loss. We find that a lossy compression ratio of 8:1 for cDNA microarrays minimally affects downstream processing. The average lossless compression ratio is 1.83:1 for cDNA images and 2.43:1 for inkjet images, comparable to state-of-the-art lossless schemas, yet with added flexibility and information.

We address the problem of streaming video efficiently from multiple servers in a distributed manner. Invoking a scalable video encoding format, we describe a network-friendly, rate-distortion efficient distributed streaming algorithm based on a robust distributed encoding paradigm. The algorithm is efficiently matched dynamically to both the video content and the network channel conditions. Due to the diversity effect of multiple servers, our distributed algorithm is immune to single points of failure, provides natural load-balancing of the multiple servers and a graceful degradation in quality with an increase in multi-server load or a decrease in network throughput.

Channel coding with side information (CCSI) provides a powerful framework for constructing data embedding codes. As a result, there has been a considerable amount of work done in trying to apply these CCSI codes to the field of image and video watermarking. The CCSI codes that exist in the literature (see Chou, J. et al., 1999; Kesal, M. et al., 2000; Eggers, J. et al., 2001), however, are relatively far from theoretical bounds. Furthermore, these codes, by themselves, are not well-suited for dealing with geometrical distortions which often appear in watermarking attacks. We propose a CCSI code that is closer to the theoretical bounds (within 2.0 dB) than the codes that exist in the literature. In addition, we show how this code construction can be combined with a synchronization code to deal with geometrical distortions.

We address the problem of streaming video efficiently from mUl­ tiple servers in a distributed manner. Invoking a scalable video encoding format, we describe a network-friendly , rate-distortion efficient distributed streaming algorithm based on a robust dis­ tributed encoding paradigm. The algorithm is efficiently matched dynamically to both the video content and the network channel conditions. Due to t he d iversity effect of multiple servers, our dis­ tributed algorithm is immune to single points of failure, provides natural load-balancing of the multiple servers and a graceful degra­ dation in quality with an Increase in multi-server load or a decrease in network throughput. We present the results of our Internet ex­ periments that validate our hypotheses.

We address duality in a variety of multiple-input-multiple-output (MIMO) source and channel coding problems of interest under different scenarios of "one-sided" inter-terminal collaboration at either the transmitter or at the receiver, including certain cases of. duality between (i) broadcast channel coding and distributed source coding, and (ii) multi-access channel coding and multiple-descriptions source coding. Our notion of duality in this paper is in a functional sense, where the optimal encoder mapping for a MIMO source coding problem becomes identical to the optimal decoder mapping for the dual MIMO channel coding problem, and vice versa. For ease of illustration we give the formulation only for two-input-two-output systems, which can be easily extended to the MIMO case. We present the precise mathematical conditions under which these encoder-decoder mappings are swappable in the two dual MIMO problems, identifying the key roles played by the source distortion and channel cost measures respectively in the MIMO source and channel coding problems in capturing this duality.

This paper derives bounds on the performance of statistical object recognition systems, wherein an image of a target is observed by a remote sensor. Detection and recognition problems are modeled as composite hypothesis testing problems involving nuisance parameters. We develop information-theoretic performance bounds on target recognition based on statistical models for sensors and data, and examine conditions under which these bounds are tight. In particular, we examine the validity of asymptotic approximations to probability of error in such imaging problems. Problems involving Gaussian, Poisson, and multiplicative noise, and random pixel deletions are considered, as well as least-favorable Gaussian clutter. A sixth application involving compressed sensor image data is considered in some detail. This study provides a systematic and computationally attractive framework for analytically characterizing target recognition performance under complicated, non-Gaussian models and optimizing system parameters.

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.

We address the problem of real-time video streaming over wireless LANs for both unicast and multicast transmission. The wireless channel is modeled as a packet-erasure channel at the IP level. For the unicast scenario, we describe a novel hybrid Automatic Repeat reQuest (ARQ) algorithm that efficiently combines forward error control (FEC) coding with the ARQ protocol. For the multiple-users scenario, we formulate the problem of real-time video multicast as an optimization of a maximum regret cost function across the multicast user space. The proposed solution efficiently combines progressive source coding with FEC coding. We present a theoretical analysis of the unicast and multicast cases, as well as experimental results that demonstrate the performance advantages of the proposed algorithms over existing methods.

We address digital transmission for enhancing, in a backward compatible way, the quality of analog image transmission systems. We propose a practical algorithm that treats the problem as one of wavelet image compression with side information (available in the form of a noisy analog version of the image) present at the decoder. We propose a rate allocation technique to efficiently allocate the rate among the wavelet coefficients of the image. In typical instances of the problem, we get gain up to 2.5 dB over conventional methods that ignore the side information. Surprisingly, this is typically achieved by modifying a very small fraction of the wavelet coefficients (typically around 10-20%) of the conventional source coder. Extensions of our proposed image transmission framework to that of video transmission finds application in the upgrade of current analog television broadcast systems to digital TV.

The list Viterbi algorithm (LVA) with an arithmetic coding based continuous error detection (CED) scheme is applied to high-order partial-response magnetic recording channels. Commonly used magnetic recording systems employ distance-enhancing codes along with parity-check post-processors to correct most dominant error events. The system presented here inserts a CED encoder between the outer Reed-Solomon (RS) code and the channel, and utilizes LVA along with CED's error detection capabilities to improve the performance of the Viterbi decoder. Simulations show that this system results in a 2 dB improvement over MTR encoded EEPRML decoding at a BER of 2/spl times/10/sup -6/ in additive white Gaussian noise and localizes error occurrences to the end of the sector.

We combine recent 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 recently 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 a rate an order of magnitude higher than existing audio data hiding systems, while being robust to channel noise.

We consider the problem of efficiently transmitting sets of spatially correlated observations in a distributed sensor network without requiring inter-node communication to exploit the correlation. Specifically, we provide a construction for quantizer design given a training set, and a distributed compression scheme to efficiently relay the quantized observations to a central decoder.

Block cyclic redundancy check (CRC) codes represent a popular and powerful class of error detection techniques used almost exclusively in modern data communication systems. Though efficient, CRCs can detect errors only after an entire block of data has been received and processed. In this work, we exploit the "continuous" nature of error detection that results from using arithmetic codes for error detection, which provides a novel tradeoff between the amount of added redundancy and the amount of time needed to detect an error once it occurs. We demonstrate how this continuous error detection framework improves the overall performance of communication systems, and show how considerable performance gains can be attained. We focus on several important scenarios: 1) automatic repeat request (ARQ) based transmission; 2) forward error correction (FEC frameworks based on (serially) concatenated coding systems involving an inner error-correction code and an outer error-detection code; and 3) reduced state sequence estimation (RSSE) for channels with memory. We demonstrate that the proposed CED framework improves the throughput of ARQ systems by up to 15% and reduces the computational/storage complexity of FEC and RSSE by a factor of two in the comparisons that we make against state-of-the-art systems.

In this work we present an end-to-end optimized video streaming system comprising of synergistic interaction between a source packetization strategy and an efficient and responsive, TCP-friendly congestion control protocol [Linear Increase Multiplicative Decrease with History (LIMD/H)]. The proposed source packetization scheme transforms a scalable/layered video bitstream so as to provide graceful resilience to network packet drops. The congestion control mechanism provides low variation in transmission rate in steady state and at the same time is reactive and provably TCP-friendly. While the two constituent algorithms identified above are novel in their own right, a key aspect of this work is the integration of these algorithms in a simple yet effective framework. This "application-transport" layer interaction approach is used to maximize the expected delivered video quality at the receiver. The integrated framework allows our system to gracefully tolerate and quickly react to sudden changes in the available connection capacity due to the onset of congestion, as verified in our simulations.

We address the problem of distributed source coding using a practical and constructive approach, referred to as distributed source coding using syndromes (DISCUS), with applications to sensor networks. We propose low complexity encoding and decoding methods based on linear codes, to achieve all points in the achievable rate region of the Slepian-Wolf (1973) problem. The extension of these concepts to the construction of Euclidean-space codes is also studied and analyzed for the case of trellis and lattice codes. The performance of these symmetric methods for encoding with a fidelity criterion is shown to be the same as that of asymmetric encoding. Simulations are presented to corroborate these results.

Summary form only given. 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.

In this work, we introduce an efficient hidden Markov field model for wavelet image coefficients and apply it to the image denoising problem. Specifically, we propose to model wavelet image coefficients within subbands as Gaussian random variables with parameters determined by underlying hidden Markov-type process. Our model is inspired by the recent estimation-quantization image coder. To reduce the computational complexity we apply the novel factor graph framework to combine two 1-D chain models to approximate a hidden Markov field (HMF) model. We then apply the proposed models for wavelet image coefficients to perform an approximate minimum mean square error (MMSE) estimation procedure to restore an image corrupted by additive white Gaussian noise. Our results are among the state-of-the-art in the field and they indicate the promise of the proposed modeling techniques.

Intersymbol interference (ISI) distorts digital signals transmitted over band-limited channels. While solutions like decision feedback equalization (DFE) suffer from error propagation, sequence estimation methods have exponential complexity. We present a scheme that effectively reduces the complexity of sequence estimation by removing paths that are in error on the fly, using continuous error detection (CED). The number of symbols taken for detecting an error can be tuned based on the amount of redundancy available for the particular application. Simulations show that our scheme can bring about a factor of two reduction in complexity in the trellis of Yellin, Vardy and Amrani (see IEEE Trans. on Info. Theory, vol.43, p.409-25, 1997) and give about 0.5 dB performance improvement at the same complexity. CED can be implemented efficiently at low complexity in hardware and can enhance the performance of ARQ/FEC based digital transmission systems. This work presents the performance gains in a reduced state sequence estimation framework.

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.

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.

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.

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.

We propose a powerful new solution to the multimedia watermarking problem by exploiting its duality with another problem for which we have recently made pioneering constructive contributions. This latter problem is that of distributed source coding, or compression of correlated sources that are distributed. We show how these two seemingly unrelated problems are actually duals of each other. We exploit this duality by transforming our recently introduced powerful constructive framework for the distributed compression problem in [13] to a corresponding dual framework for the watermarking problem. Simulations expose the significant performance gains attained by our proposed watermarking approach and reveal its exciting potential for next-generation watermarking techniques. This can be accredited to the exploitation of the dual roles played by source codes and channel codes in the two problems.

Block cyclic redundancy check (CRC) codes are typically used to perform error detection in automatic repeat request (ARQ) protocols for data communications. Although efficient, CRCs can detect errors only after an entire block of data has been received and processed. We propose a new "continuous" error detection scheme using arithmetic coding that provides a novel tradeoff between the amount of added redundancy and the amount of time needed to detect an error once it occurs. This method of error detection, first introduced by Bell, Witten, and Cleary (1990), is achieved through the use of an arithmetic codec, and has the attractive feature that it can be combined physically with arithmetic source coding, which is widely used in state of-the-art image coders. We analytically optimize the tradeoff between added redundancy and error-detection time, achieving significant gains in bit rate throughput over conventional ARQ schemes for binary symmetric channel models for all probabilities of error.

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.

We present an optimal, computationally efficient, integer-bit power allocation algorithm for discrete multitone modulation. Using efficient lookup table searches and a Lagrange-multiplier bisection search, our algorithm converges faster to the optimal solution than existing techniques and can replace the use of suboptimal methods because of its low computational complexity. Fast algorithms are developed for the data rate and performance margin maximization problems.

We consider the problem of coding images for transmission over error-prone channels. The impairments we target are transient channel shutdowns, as would occur in a packet network when a packet is lost, or in a wireless system during a deep fade: when data is delivered it is assumed to be error-free, but some of the data may never reach the receiver. The proposed algorithms are based on a combination of multiple description scalar quantizers with techniques successfully applied to the construction of some of the most efficient subband coders. A given image is encoded into multiple independent packets of roughly equal length. When packets are lost, the quality of the approximation computed at the receiver depends only on the number of packets received, but does not depend on exactly which packets are actually received. When compared with previously reported results on the performance of robust image coders based on multiple descriptions, on standard test images, our coders attain similar PSNR values using typically about 50-60% of the bit rate required by these other state-of-the-art coders, while at the same time providing significantly more freedom in the mechanism for allocation of redundancy among descriptions.

We describe a spatially scalable video coding framework in which motion correspondences between successive video frames are exploited in the wavelet transform domain. 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 to 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 low pass filtering and interpolation in the estimation loop. Further, to achieve robust motion estimation against quantization noise, we propose a novel backward/forward hybrid motion compensation scheme, and a tree structured dynamic programming algorithm to optimize the backward/forward mode choices. A novel adaptive quantization scheme is applied to code the motion predicted residue wavelet coefficients, Experimental results reveal 0.3-2-dB increase in coded PSNR at low bit rates over the state-of-the-art H.263 standard with all enhancement modes enabled, and similar improvements over MPEG-2 at high bit rates, with a considerable improvement in subjective reconstruction quality, while simultaneously supporting a scalable representation.

Multiple description coding refers to the encoding of an information source into multiple bit streams, in a manner that each bit stream independently represents a "coarse" description of the source, while multiple descriptions jointly convey a higher fidelity source representation. Thus multiple description coding allows enhanced resilience to loss of individual descriptions, and can be viewed as a form of source-based diversity coding. This paper addresses the design of subband filter banks to optimize the rate-distortion performance of multiple description subband coding. The problem is formulated in a Lagrangian optimization framework, and is solved directly in the frequency domain to produce the optimal filter spectral responses. By varying the Lagrangian parameter, our design obtains all points on the redundancy-distortion curve for Gaussian wide-sense stationary input processes. We consider the cases of both orthonormal and more general biorthogonal filter banks. We also analyze the connections between these two solutions, and quantify the gap in their optimal performance. Application of the proposed methods to the popular first-order autoregressive (AR(1)) model yields very interesting and insightful results. In the two extreme cases of maximum and minimum redundancy, our solutions degenerate to previously known results. Finally, comparisons with popularly deployed filter banks reveal large gaps from the theoretical performance bound.

We address the problem of distributed source coding, i.e. compression of correlated sources that are not co-located and/or cannot communicate with each other to minimize their joint description cost. In this work we tackle the related problem of compressing a source that is correlated with another source which is available only at the decoder. In contrast to prior information-theoretic approaches, we introduce a new construction and practical framework for tackling the problem based on the judicious incorporation of channel coding principles into this source coding problem. We dub our approach as distributed source coding using syndromes (DISCUS). We focus in this paper on trellis-structured constructions of the framework to illustrate its utility. Simulation results confirm the power of DISCUS, opening up a new and exciting constructive playing-ground for the distributed source coding problem. For the distributed coding of correlated i.i.d. Gaussian sources that are noisy versions of each other with "correlation-SNR" in the range of 12 to 20 dB, the DISCUS method attains gains of 7-15 dB in SNR over the Shannon-bound using "naive" independent coding of the sources.

With the rapid growth of multimedia content in wireless communication, there is an increasing demand for efficient image and video transmission systems. We present a joint source-channel matching scheme for wireless video transmission which jointly optimizes the source and channel coder to yield the optimal transmission quality while satisfying real-time delay and buffer constraints. We utilize a parametric model approach which avoids the necessity of having detailed a priori knowledge of the coders, thus making the scheme applicable to a wide variety of source and channel coder pairs. Simulations show that the scheme yields excellent results and works for several different types of source and channel coders.

This paper deals with the application to denoising of a very simple but effective "local" spatially adaptive statistical model for the wavelet image representation that was previously introduced successfully in a compression context. Motivated by the intimate connection between compression and denoising, this paper explores the significant role of the underlying statistical wavelet image model. The model used here, a simplified version of the one proposed by LoPresto, Ramchandran and Orchard (see Proc. IEEE Data Compression Conf., 1997), is that of a mixture process of independent component fields having a zero-mean Gaussian distribution with unknown variances /spl sigma//sub s//sup 2/ that are slowly spatially-varying with the wavelet coefficient location s. We propose to use this model for image denoising by initially estimating the underlying variance field using a maximum likelihood (ML) rule and then applying the minimum mean squared error (MMSE) estimation procedure. In the process of variance estimation, we assume that the variance field is "locally" smooth to allow its reliable estimation, and use an adaptive window-based estimation procedure to capture the effect of edges. Despite the simplicity of our method, our denoising results compare favorably with the best reported results in the denoising literature.

We introduce a simple spatially adaptive statistical model for wavelet image coefficients and apply it to image denoising. Our model is inspired by a recent wavelet image compression algorithm, the estimation-quantization (EQ) coder. We model wavelet image coefficients as zero-mean Gaussian random variables with high local correlation. We assume a marginal prior distribution on wavelet coefficients variances and estimate them using an approximate maximum a posteriori probability rule. Then we apply an approximate minimum mean squared error estimation procedure to restore the noisy wavelet image coefficients. Despite the simplicity of our method, both in its concept and implementation, our denoising results are among the best reported in the literature.

We undertake a study of the performance difference of the discrete cosine transform (DCT) and the wavelet transform for both image and video coding, while comparing other aspects of the coding system on an equal footing based on the state-of-the-art coding techniques. The studies reveal that, for still images, the wavelet transform outperforms the DCT typically by the order of about 1 dB in peak signal-to-noise ratio. For video coding, the advantage of wavelet schemes is less obvious. We believe that the image and video compression algorithm should be addressed from the overall system viewpoint: quantization, entropy coding, and the complex interplay among elements of the coding system are more important than spending all the efforts on optimizing the transform.

In this paper, an experimental study of the statistical properties of wavelet coefficients of image data is presented, as well as the design of two different morphology-based image coding algorithms that make use of these statistics. A salient feature of the proposed methods is that, by a simple change of quantizers, the same basic algorithm yields high performance embedded or fixed rate coders. Another important feature is that the shape information of morphological sets used in this coder is encoded implicitly by the values of wavelet coefficients, thus avoiding the use of explicit and rate expensive shape descriptors. These proposed algorithms, while achieving nearly the same objective performance of state-of-the-art zerotree based methods, are able to produce reconstructions of a somewhat superior perceptual quality, due to a property of joint compression and noise reduction they exhibit.

This work introduces a new approach to inverse halftoning using nonorthogonal wavelets. The distinct features of this wavelet-based approach are: 1) edge information in the highpass wavelet images of a halftone image is extracted and used to assist inverse halftoning, 2) cross-scale correlations in the multiscale wavelet decomposition are used for removing background halftoning noise while preserving important edges in the wavelet lowpass image, and 3) experiments show that our simple wavelet-based approach outperforms the best results obtained from inverse halftoning methods published in the literature, which are iterative in nature.

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.

Summary form only given. 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.

Block cyclic redundancy check (CRC) codes represent a popular and powerful class of error detection techniques in modern data communication systems. Though efficient, CRCs can detect errors only after an entire block of data has been received and processed. We propose a new "continuous" error detection scheme using arithmetic coding that provides a novel tradeoff between the amount of added redundancy and the amount of time needed to detect an error once it occurs. We demonstrate how the new error detection framework improves the overall performance of transmission systems, and show how sizeable performance gains can be attained. We focus on two popular scenarios: (i) automatic repeat request (ARQ) based transmission; and (ii) forward error correction frameworks based on (serially) concatenated coding systems involving an inner error-correction code and an outer error-detection code.

Application of joint source-channel matching in heterogeneous multimedia environments will demand general source-channel optimization schemes suitable for a wide variety of source coding standards, channel coders, and variable channel conditions. We develop a general approach for joint source-channel matching based on a parametric distortion model that can be accurately applied to most classes of source and channel coders. Our simulations indicate that it may be possible to obtain nearly all of the benefits of joint source-channel optimization by matching existing source and channel coding standards using the simple and general approach we propose.

We present an optimal, efficient power allocation algorithm for discrete multitone modulation (DMT). Using efficient lookup table searches and a Lagrange multiplier bisection search, our algorithm converges much faster to the optimal solution than existing techniques and can replace the use of suboptimal methods because of its low computational complexity. A fast algorithm is developed and a pseudocode is provided.

We tackle the problem of efficient image transmission over multicarrier modulation (MCM) systems, proposing the use of a layered or multiresolution (MR) framework. We treat the source as being characterized by multiple layers of importance, and therefore deserving of multiple levels of noise immunity, i.e, having different BER requirements. We present the idea of embedded multicarrier modulation (EMCM) as a very 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 rates for the different resolution layers, subject to a total power constraint. Simulation results of our EMCM system reveal substantial gains (up to about 25%) in deliverable bit rates over optimized TDM-based MCM designs. Further, in typical image transmission simulations using an embedded wavelet image coder, the EMCM approach yields almost 3 dB gains in delivered quality over conventional single-resolution MCM systems.

Application of joint source-channel matching in heterogeneous multi-media environments will demand general source-channel optimization schemes suitable for a wide variety of source coding standards, channel coders, and variable channel conditions. We develop a general approach for joint source-channel matching based on a parametric distortion model that can be accurately applied to most classes of source and channel coders. Our simulations indicate that it may be possible to obtain nearly all of the benefits of joint source-channel optimization by matching existing source and channel coding standards using the simple and general approach we propose.

Despite their widespread popularity, the JPEG and MPEG compression standards can lead to noticeable "blocking" artifacts-artifical rectangular discontinuities in the decoded image. Powerful postprocessing algorithms have been developed to remove blocking artifacts without destroying key image information. However, all but the simplest algorithms can be too complex for real-time applications such as video and still image decoding. We introduce a fast, easy-to-implement algorithm that removes blockiness by performing a simple nonlinear smoothing of pixels. This approach significantly improves visual quality and achieves subjective and objective (PSNR) gains that are competitive with the best deblocking algorithms reported in the literature at much reduced computational complexity.

We extend the statistical model-based estimation-quantization (EQ) wavelet image coding algorithm introduced by LoPresto, Ramchandran and Orchard (see Proceedings of the Data Compression Conference, Snowbird, UT, 1997) to include an adaptive transform component. For this, we resort to the rich, space-frequency diverse, and easy-to-search library of transforms provided by the family of wavelet packet (WP) bases and their adaptive extensions. We use rate-distortion criteria to find the best basis jointly with the statistical model-based best adaptive quantization and entropy coding strategy of LoPresto et al. based on an efficient and fast tree pruning algorithm. A key underlying attribute of our paradigm is that the spatially-varying generalized Gaussian mixture model for wavelet coefficients introduced by LoPresto et al. is also applicable to the more arbitrary framework of (adaptive) wavelet packet transform coefficients as well. Our WP-EQ framework produces excellent results on standard test images. The most attractive property of our paradigm is its "universality" and robustness: based on an overall performance criterion that considers diverse classes of input test images that have varying space-frequency characteristics, it is more powerful than most of the existing image coding algorithms, using reasonable complexity, and a generic, integrated, non-training based framework.

We study certain aspects of the problem of watermarking images, not for the classical example of ownership identification, but instead for embedding a unique identifier that can act as a "serial number" for the image in which it is embedded. In this context, two fundamental questions are: (a) what is the maximum number of different watermarks that can be distinguished reliably? and (b) what are good design techniques for watermarking methods to approximate that maximum? Under the assumption that attacks can be modeled as additive noise, we provide answers to both questions. To answer (a), we first show how the process of inserting a watermark is analogous to that of storing bits in certain devices, and then we compute the storage capacity of these devices. To answer (b), we present a specific design of a modulator to store information in those devices. Numerical simulations reveal that although strongly suboptimal in the number of bits they can effectively store in an image, simple and very low complexity modulator designs are able to pack enough bits in an image to be useful in practice.

We consider the problem of image coding for communication systems that use diversity to overcome channel impairments. We focus on the special case in which there are two channels of equal capacity between a transmitter and a receiver. Our designs are based on a combination of techniques successfully applied to the construction of some of the most efficient wavelet based image coding algorithms, with multiple description scalar quantizers (MDSQs). For a given image, we produce two bitstreams, to be transmitted over each channel. Should one of the channels fail, each individual description guarantees a minimum image quality specified by the user. However, if both descriptions arrive at destination, they are combined to produce a higher quality image than that achievable based on individual descriptions. We formulate a discrete optimization problem, whose solution gives parameters of the proposed encoder yielding optimal performance in an operational sense. Simulation results are presented.

Multiple description coding refers to encoding an information source into multiple bitstreams, in a way that various levels of tradeoff between decoding quality and channel protection can be supported. This paper addresses the design of two-channel orthonormal filter banks to optimize the redundancy rate-distortion performance of multiple description subband coding. The problem is formulated in a Lagrangian optimization framework, and is solved directly in the frequency domain to produce the optimal filter responses. By varying the Lagrangian parameter, our design obtains all points on the information redundancy rate-distortion curve for Gaussian wide sense stationary input processes. Application of the proposed algorithm to the popular AR(1) model yields very interesting and insightful results. Comparisons with popularly deployed filter banks reveal large gaps from the theoretical performance bound.

Due to high data rates and limited bandwidth as well as limited battery power, wireless multimedia communications systems must be optimized in every possible way. We develop a generic matching scheme for wireless image and video communication in which the three most significant components: the source coder, the channel coder, and hardware power consumption, are jointly optimized. That is, we maximize the end-to-end image quality subject to a total power constraint on both the RF transmission power and the power consumption of the digital implementation of the channel coder, which represents a major portion of the total hardware power in short-range applications.

We address practical issues which arise in the implementation of optimized cache replenishment algorithms within a "soft" caching framework. We study the algorithms that have been proposed for optimized soft caching and simulate them using actual proxy traces. Our objective is to determine what compromises have to be made in order to approximate the desired optimal performance while maintaining a complexity level sufficiently low to enable a real-time implementation.

We propose an automatic repeat request (ARQ)/forward error correction (FEC) scheme for synchronous transmission of video over a binary symmetric constant rate channel. The approach consists of jointly allocating source and channel rates to video blocks from a given admissible set subject to the buffer or equivalently end-end delay constraints. The channel codes used are the popular class of powerful FEC codes known as rate-compatible punctured convolutional (RCPC) codes. The method used involves independent coding of the video units and optimization of the end-to-end expected delivered video quality. The existence of a return channel is assumed through which the decoder informs the encoder about the success/failure of the transmission. In the event of a failure, incremental parity information is sent to the decoder for correcting errors and a reallocation performed at the encoder. The simulations done point out the efficacy of the proposed scheme.

Despite their widespread popularity, the Joint Photographers Expert Group (JPEG) and Motion Pictures Expert Group (MPEG) compression standards can lead to noticeable "blocking" artifacts-artificial rectangular discontinuities in the decoded image. Powerful postprocessing algorithms have been developed to remove blocking artifacts without destroying key image information. However, all but the simplest algorithms can be too complex for real-time applications such as video and still image decoding. We introduce a fast, easy-to-implement algorithm that removes blockiness by performing a simple nonlinear smoothing of pixels. This approach significantly improves visual quality and achieves subjective and objective (PSNR) gains that are competitive with the best deblocking algorithms reported in the literature at much reduced computational complexity.

We extend our previous work on space-frequency quantization (SFQ) for image coding from wavelet transforms to the more general wavelet packet transforms. The resulting wavelet packet coder offers a universal transform coding framework within the constraints of filterbank structures by allowing joint transform and quantizer design without assuming a priori statistics of the input image. In other words, the new coder adaptively chooses the representation to suit the image and the quantization to suit the representation. Experimental results show that, for some image classes, our new coder gives excellent coding performance.

We introduce a new image compression paradigm that combines compression efficiency with speed, and is based on an independent "infinite" mixture model which accurately captures the space-frequency characterization of the wavelet image representation. Specifically, we model image wavelet coefficients as being drawn from an independent generalized Gaussian distribution field, of fixed unknown shape for each subband, having zero mean and unknown slowly spatially-varying variances. Based on this model, we develop a powerful "on the fly" estimation-quantization (EQ) framework that consists of: (i) first finding the maximum-likelihood estimate of the individual spatially-varying coefficient field variances based on causal and quantized spatial neighborhood contexts; and (ii) then applying an off-line rate-distortion (R-D) optimized quantization/entropy coding strategy, implemented as a fast lookup table, that is optimally matched to the derived variance estimates. A distinctive feature of our paradigm is the dynamic switching between forward and backward adaptation modes based on the reliability of causal prediction contexts. The performance of our coder is extremely competitive with the best published results in the literature across diverse classes of images and target bitrates of interest, in both compression efficiency and processing speed. For example, our coder exceeds the objective performance of the best zerotree-based wavelet coder based on space-frequency-quantization at all bit rates for all tested images at a fraction of its complexity.

Interference suppression in spread spectrum communication systems is often essential for achieving maximum system performance. Existing interference suppression methods do not perform well for most types of nonstationary interference. We first consider interference suppression schemes based on adaptive orthogonal time-frequency decompositions, such as wavelet packet and arbitrary dyadic time-frequency tilings. These methods often reduce interference substantially, but their performance can vary dramatically with minor changes in interference characteristics such as the center frequency. To circumvent these drawbacks, we propose a multiple overdetermined tiling (MODT) with an accompanying blind interference excision scheme which appears very promising for mitigating time-frequency-concentrated interference. Simulations with narrowband, impulsive, and simultaneous impulsive and narrowband interference compare the performance of the various methods and illustrate the promise of approaches based on multiple overdetermined tilings.

We consider the problem of efficient image transmission over noisy time-varying channels subject to a low transmission energy constraint (and fixed bandwidth/delay constraints). We examine the limits of desirability of a highly compressed representation using a joint source-channel coding (JSCC) framework. Specifically, invoking as a platform a state-of-the-art wavelet image coder, we demonstrate how the resulting highly compressed digital stream, appropriately protected against channel noise, is not always the best solution. We show how a hybrid scheme based on simple partitioning of the wavelet image representation into "compressed" and "uncompressed" components can lead to significantly improved performance (of the order of 3 dB in PSNR for Rayleigh channels) over popular JSCC schemes which are based on compressed, entropy-coded, and appropriately unequal error-protected (UEP) source representations.

It is commonly known that wavelet expansions are very sensitive to translation of an input signal due to their dyadic structure. Without proper time alignment of the signal to the decomposition basis vectors, a compact expansion may be unattainable. Recently, work has been done to combat translation sensitivity by determining the best translation-invariant expansion of a signal with respect to a set of bases. However, the dyadic structure of wavelet expansions also results in frequency alignment sensitivity. In this work, we introduce a frequency-shifted wavelet packet library as well as an efficient best basis algorithm for determining the best signal representation among all frequency shifts of a signal.

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.

We tackle the problem of efficient image transmission over multi-carrier modulation (MCM) systems, proposing the use of a layered or multiresolution (MR) framework. In this work, we treat the source as being characterized by multiple layers of importance, and therefore deserving of multiple levels of noise immunity, i.e. having different BER requirements. We present the idea of embedded multi-carrier modulation (EMCM) as a very 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 bitrates for the different resolution layers, subject to a total power constraint. Simulation results of our EMCM system reveal substantial gains (up to about 25%) in deliverable bit rates over optimized TDM-based MCM designs. Further, in typical image transmission simulations using an embedded wavelet image coder, the EMCM approach yields almost 3 dB gains in delivered quality over conventional single-resolution MCM systems.

Variable bit rate (VBR) transmission is widely regarded as the best solution for the transport of compressed image and video data, both in terms of network utilization and quality of data decoded at the receiver. However, significant problems remain unsolved to make this a viable approach. One of these problems is that of efficiently matching characteristics of the VBR source to those of the channel, in order to maximize end-to-end system performance. In this work, we propose a model for the channel based on which the source can make optimal decisions regarding bit allocation and rate control. This model consists of N queues, for each of which the source negotiates with the network statistical performance guarantees, consisting of allowable average transmission and packet loss rates. Based on such a channel description, the source determines how to allocate packets to each queue, to minimize the expected distortion of the images reconstructed at the receiver. A provably optimal algorithm for computing such bit allocations is the core of this work. Simulation results are presented.

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.

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.

Content based retrieval of image and video data from databases is a very challenging problem, whose interest is derived from the need of future databases to support efficient access to vast amounts of visual information. Typical queries to be performed in this context check attributes of objects present in image data, such as shape, color, relative locations, etc. Therefore, the way in which image data is represented plays a fundamental role in the efficient implementation of those queries. One possibility is to take the naive approach of storing images using standard compression techniques, storing image features (such as object shape descriptors, color histograms, etc.) as explicit side information, and whenever an image is involved in the evaluation of a query decoding it to full resolution; however, many more efficient techniques (in terms of storage and computational requirements) are possible. We propose a new image coding technique which combines a wavelet image representation, embedded coding of the wavelet coefficients, and segmentation of semantically meaningful objects in the wavelet domain, to generate a bitstream in which each object is encoded independently of every other object in the image, and without explicitly storing shape boundary information. Furthermore, since the representation of each object is fully embedded, applications may, independently for each object, specify the desired target bitrate and retrieve bits from the compressed bitstream.

Striving to maximize baseline (Joint Photographers Expert Group-JPEG) image quality without compromising compatibility of current JPEG decoders, we develop an image-adaptive JPEG encoding algorithm that jointly optimizes quantizer selection, coefficient "thresholding", and Huffman coding within a rate-distortion (R-D) framework. Practically speaking, our algorithm unifies two previous approaches to image-adaptive JPEG encoding: R-D optimized quantizer selection and R-D optimal thresholding. Conceptually speaking, our algorithm is a logical consequence of entropy-constrained vector quantization (ECVQ) design principles in the severely constrained instance of JPEG-compatible encoding. We explore both viewpoints: the practical, to concretely derive our algorithm, and the conceptual, to justify the claim that our algorithm approaches the best performance that a JPEG encoder can achieve. This performance includes significant objective peak signal-to-noise ratio (PSNR) improvement over previous work and at high rates gives results comparable to state-of-the-art image coders. For example, coding the Lena image at 1.0 b/pixel, our JPEG encoder achieves a PSNR performance of 39.6 dB that slightly exceeds the quoted PSNR results of Shapiro's wavelet-based zero-tree coder. Using a visually based distortion metric, we can achieve noticeable subjective improvement as well. Furthermore, our algorithm may be applied to other systems that use run-length encoding, including intraframe MPEG and subband or wavelet coding.

We examine the question of how to choose a space varying filterbank tree representation that minimizes some additive cost function for an image. The idea is that for a particular cost function, e.g., energy compaction or quantization distortion, some tree structures perform better than others. While the wavelet tree represents a good choice for many signals, it is generally outperformed by the best tree from the library of wavelet packet frequency-selective trees. The double-tree library of bases performs better still, by allowing different wavelet packet trees over all binary spatial segments of the image. We build on this foundation and present efficient new pruning algorithms for both one- and two-dimensional (1-D and 2-D) trees that will find the best basis from a library that is many times larger than the library of the single-tree or double-tree algorithms. The augmentation of the library of bases overcomes the constrained nature of the spatial variation in the double-tree bases, and is a significant enhancement in practice. Use of these algorithms to select the least-cost expansion for images with a rate-distortion cost function gives a very effective signal adaptive compression scheme. This scheme is universal in the sense that, without assuming a model for the signal or making use of training data, it performs very well over a large class of signal types. In experiments it achieves compression rates that are competitive with the best training-based schemes.

A new class of image coding algorithms coupling standard scalar quantization of frequency coefficients with tree-structured quantization (related to spatial structures) has attracted wide attention because its good performance appears to confirm the promised efficiencies of hierarchical representation. This paper addresses the problem of how spatial quantization modes and standard scalar quantization can be applied in a jointly optimal fashion in an image coder. We consider zerotree quantization (zeroing out tree-structured sets of wavelet coefficients) and the simplest form of scalar quantization (a single common uniform scalar quantizer applied to all nonzeroed coefficients), and we formalize the problem of optimizing their joint application. We develop an image coding algorithm for solving the resulting optimization problem. Despite the basic form of the two quantizers considered, the resulting algorithm demonstrates coding performance that is competitive, often outperforming the very best coding algorithms in the literature.

We introduce a novel region-based video compression framework that uses a morphological operation 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 needing to explicitly send object boundaries. Cluster matching is used in lieu of the conventional block matching methods of standard video codecs to define a cluster motion representation paradigm. Experimental coding results show about 10-20% reduction in prediction error energy and 0.3-1 db (average of about 0.44 dB) reduction in the final residue-coded peak signal to noise ratio (PSNR) using our proposed motion compensation framework on the football sequence over standard block motion compensation methods like MPEG, while also requiring less computational complexity.

We explore joint source-channel coding (JSCC) for time-varying (slow-fading Rayleigh) channels, using a multiresolution (MR) framework for both source coding and transmission (via a novel MR modulation constellation). We tackle the important case of the informed receiver but uninformed transmitter, i.e. where the receiver has access to the channel state information (CSI), but the transmitter does not. We describe an algorithm which jointly optimizes the design of the MR source codebook, the MR constellation, and the decoding strategy of optimally matching the source and signal constellation resolution trees according to the time-varying channel, and show how this leads to improved performance over separately designed source and channel coders.

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.

Recent work on filter banks and related expansions has revealed an interesting insight: different filter bank trees can be regarded as different ways of constructing orthonormal bases for linear signal expansion. In particular, fast algorithms for finding best bases in an operational rate-distortion sense have been successfully used in image coding. Independently of this work, recent research has also explored the design of filter banks that optimize energy compaction for a single signal or a class of signals. In this paper we integrate these two different but complementary approaches to best-basis design and propose an image coder in which subband filter banks, tree structure and quantizers are chosen so as to optimize rate-distortion performance. These optimal filter banks, tree structure and quantizers represent side information. They are selected from a codebook designed from training data, using a rate-distortion criterion.

This paper introduces a new approach to inverse halftoning using nonorthogonal wavelets. The distinct features of this wavelet-based approach are: a) edge information in the highpass wavelet images of a halftone is extracted and used to assist inverse halftoning, b) cross-scale correlations in the multiscale wavelet decomposition are used for removing background halftoning noise while preserving important edges in the wavelet lowpass image, c) experiments show that our simple wavelet-based approach outperforms the best results obtained from inverse halftoning methods published in the literature, which are iterative in nature.

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. The cluster motion field is obtained using a novel "cluster matching" approach which is computationally efficient due to the use of only a small cluster "core" that serves as a reliable representative of the entire cluster. A novel morphological dilation operation is used to expand the cluster based on the motion information, and quantization of the cluster motion prediction error is directly incorporated in the region-growing process. Experimental results reveal a 10-30% reduction in coding bit rate over the standard MPEG-1 coder at typical bit rates of 500 kbits/sec to 1 Mb/sec on standard test sequences, while also requiring much lower computational complexity.

The emergence of wavelets has led to a convergence of linear expansion methods used in signal processing and applied mathematics. In particular, subband coding methods and their associated filters are closely related to wavelet constructions. We first review such constructions with a signal processing perspective. We then discuss the idea behind signal adapted bases and associated algorithms before showing how wavelets and subband coding methods are used in signal compression applications.

We introduce a novel, adaptive image representation using spatially varying wavelet packets (WPs), Our adaptive representation uses the fast double-tree algorithm introduced previously (Herley et al., 1993) to optimize an operational rate-distortion (R-D) cost function, as is appropriate for the lossy image compression framework. This involves jointly determining which filter bank tree (WP frequency decomposition) to use, and when to change the filter bank tree (spatial segmentation). For optimality, the spatial and frequency segmentations must be done jointly, not sequentially. Due to computational complexity constraints, we consider quadtree spatial segmentations and binary WP frequency decompositions (corresponding to two-channel filter banks) for application to image coding. We present results verifying the usefulness and versatility of this adaptive representation for image coding using both a first-order entropy rate-measure-based coder as well as a powerful space-frequency quantization-based (SPQ-based) wavelet coder introduced by Xiong et al. (1993).

Previous works, including adaptive quantizer selection and adaptive coefficient thresholding, have addressed the optimization of a baseline-decodable JPEG coder in a rate-distortion (R-D) sense. In this work, by developing an entropy-constrained quantization framework, we show that these previous works do not fully realize the attainable coding gain, and then formulate a computationally efficient way that attempts to fully realize this gain for baseline-JPEG-decodable systems. Interestingly, we find that the gains obtained using the previous algorithms are almost additive. The framework involves viewing a scalar-quantized system with fixed quantizers as a special type of vector quantizer (VQ), and then to use techniques akin to entropy-constrained vector quantization (ECVQ) to optimize the system. In the JPEG case, a computationally efficient algorithm can be derived, without training, by jointly performing coefficient thresholding, quantizer selection, and Huffman table customization, all compatible with the baseline JPEG syntax. Our algorithm achieves significant R-D improvement over standard JPEG (about 2 dB for typical images) with performance comparable to that of more complex "state-of-the-art" coders. For example, for the Lenna image coded at 1.0 bits per pixel, our JPEG-compatible coder achieves a PSNR of 39.6 dB, which even slightly exceeds the published performance of Shapiro's wavelet coder. Although PSNR does not guarantee subjective performance, our algorithm can be applied with a flexible range of visually-based distortion metrics.

This paper introduces a novel, image-adaptive, encoding scheme for the baseline JPEG standard. In particular, coefficient thresholding, JPEG quantization matrix (Q-matrix) optimization, and adaptive Huffman entropy-coding are jointly performed to maximize coded still-image quality within the constraints of the baseline JPEG syntax. Adaptive JPEG coding has been addressed in earlier works: by Ramchandran and Vetterli (see IEEE Trans. on Image Processing, Special Issue on Image Compression, vol.3, p.700-704, September 1994), where fast rate-distortion (R-D) optimal coefficient thresholding was described, and by Wu and Gersho (see Proc. Inter. Conf. Acoustics, Speech and Signal Processing, vol.5, p.389-392, April 1993) and Hung and Meng (1991), where R-D optimized Q-matrix selection was performed. By formulating an algorithm which optimizes these two operations jointly, we have obtained performance comparable to more complex, "state-of-the-art" coding schemes: for the "Lenna" image at 1 bpp, our algorithm has achieved a PSNR of 39.6 dB. This result represents a gain of 1.7 dB over JPEG with a customized Huffman entropy coder, and even slightly exceeds the published performance of Shapiro's (see IEEE Trans. on Signal Processing, vol.41, p.3445-3462, December 1993) wavelet-based scheme. Furthermore, with the choice of appropriate visually-based error metrics, noticeable subjective improvement has been achieved as well.

We examine the question of how to choose a time-varying filter bank representation for a signal which is optimal with respect to an additive cost function. We present in detail an efficient algorithm for the Haar filter set which finds the optimal basis, given the constraint that the time and frequency segmentations are binary. Extension to multiple dimensions is simple, and the use of arbitrary filter sets is also possible. We verify that the algorithm indeed produces a lower cost representation than any of the wavelet packet representations for compression of images using a simple rate-distortion cost.

Proposes an improved statistical characterization of the field of wavelet coefficients of natural images. Based on this characterization, the authors introduce morphological representation of wavelet data (MRWD), a novel coding framework for both image and video coding applications. MRWD departs from existing wavelet-based coders in its use of a radically different set of primitive operations-non-linear, morphological operations-for efficiently encoding the wavelet data field. Simulation results are very encouraging: a preliminary algorithm based on the morphological data structure is able to achieve about 0.5 dB of gain in SNR over Shapiro's (1993) state-of-the-art zerotree-based wavelet coder at a coding rate of 1 bpp for the "Lena" image.

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.

In previous work, we introduced a new image representation for the field of wavelet coefficients (dubbed MRWD), based on morphological operators. This work extends the MRWD framework, by addressing the effective design of image coding algorithms. First, we design an encoder with the goal of being optimal in the operational rate-distortion sense. Second, based on the same (morphological) techniques, we design a successively refinable version of the single rate coder. Simulation results are reported.

We introduce a new image coding algorithm which exploits the idea of space-varying wavelet packets, where the best filter bank representation is chosen from a large library. The filter bank tree representations in the library are free to vary in structure over different segments of the image, and a fast search algorithm is given. In addition we employ the idea of space-frequency quantization, which is a rate-distortion optimized extension of the zero-tree wavelet coder of Shapiro to wavelet packets. The coder thus adaptively chooses the representation to suit the image and adaptively chooses the quantization to suit the representation. We present coding results that confirm the excellent performance of the scheme.

Wavelet image decompositions generate a tree-structured set of coefficients, providing an hierarchical data-structure for representing images. Several recently proposed image compression algorithms have focused on new ways for exploiting dependencies between this hierarchy of wavelet coefficients. This paper presents a new framework for understanding the efficiency of one such algorithm as a simplified attempt to a global entropy-constrained image quantizer. The principle insight offered by the new framework is that improved performance is achieved by more accurately characterizing the joint probabilities of arbitrary sets of wavelet coefficients. The specific algorithm described is designed around one conveniently structured collection of such sets. The efficiency of hierarchical wavelet coding algorithms derives from their success at identifying and exploiting dependencies between coefficients in the hierarchical structure. The second part of the paper presents an empirical study of the distribution of high-band wavelet coefficients, the band responsible for most of the performance improvements of the new algorithms.>

The authors show a rate-distortion optimal quantization technique to threshold the DCT coefficients in the industry image and video coding standards JPEG and MPEG respectively. Their scheme achieves a decent thresholding gain in terms of both objective SNR (about 1 dB) as well as perceived quality and uses a fast dynamic programming recursive structure which exploits certain monotonicity characteristics of the JPEG and MPEG codebooks to drastically reduce the complexity. The primary advantage of their encoding algorithm is that it is completely compatible with the baseline JPEG and MPEG decoders.>

Linear predictive models seek to optimally extract information about a sample of a signal based on some subset of its causal past. Very little work has been done in investigating the importance and choice of this subset (support) in the prediction process. The paper addresses the problem of finding the optimal support for use by a linear predictive model. The authors derive a general result relating the distortion incurred in predicting a sample of a stationary signal based on a causal support in terms of the Wiener coefficients of a larger support and the autocorrelation matrix. Based on the above result, they derive an algorithm which optimally reduces the size of the support by one at each stage. The algorithm is tested on the Barbara image for image estimation and on the football image sequence for pel-recursive motion compensation and is shown to outperform (by large margins in some cases) conventionally chosen supports.>

A novel quantization scheme targeted at jointly optimizing the spatial and frequency characterization of the wavelet representation of images was introduced in Xiong et al. (1993) for image compression applications. The present authors extend the concept of joint space-frequency quantization (SFQ) to the more flexible class of wavelet packet representations (Coifman and Wickerhauser, 1992), which are a generalization of the multiresolution decomposition using the wavelet transform. They propose a fast algorithm to jointly search for the best wavelet packet basis and space-frequency quantizer, presenting empirical evidence of its high performance (e.g., for the "Barbara" image coded at 0.5 b/p, they get a 0.7 dB gain in PSNR over the fixed-wavelet based SFQ of Xiong et al. and 1.5 dB over Shapiro's embedded wavelet coder (Shapiro, 1993)).>

The authors formalize the description of the buffer-constrained adaptive quantization problem. For a given set of admissible quantizers used to code a discrete nonstationary signal sequence in a buffer-constrained environment, they formulate the optimal solution. They also develop slightly suboptimal but much faster approximations. These solutions are valid for any globally minimum distortion criterion, which is additive over the individual elements of the sequence. As a first step, they define the problem as one of constrained, discrete optimization and establish its equivalence to some of the problems studied in the field of integer programming. Forward dynamic programming using the Viterbi algorithm is shown to provide a way of computing the optimal solution. Then, they provide a heuristic algorithm based on Lagrangian optimization using an operational rate-distortion framework that, with computing complexity reduced by an order of magnitude, approaches the optimally achievable performance. The algorithms can serve as a benchmark for assessing the performance of buffer control strategies and are useful for applications such as multimedia workstation displays, video encoding for CD-ROMs, and buffered JPEG coding environments, where processing delay is not a concern but decoding buffer size has to be minimized.

We address the problem of efficient bit allocation in a dependent coding environment. While optimal bit allocation for independently coded signal blocks has been studied in the literature, we extend these techniques to the more general temporally and spatially dependent coding scenarios. Of particular interest are the topical MPEG video coder and multiresolution coders. Our approach uses an operational rate-distortion (R-D) framework for arbitrary quantizer sets. We show how a certain monotonicity property of the dependent R-D curves can be exploited in formulating fast ways to obtain optimal and near-optimal solutions. We illustrate the application of this property in specifying intelligent pruning conditions to eliminate suboptimal operating points for the MPEG allocation problem, for which we also point out fast nearly-optimal heuristics. Additionally, we formulate an efficient allocation strategy for multiresolution coders, using the spatial pyramid coder as an example. We then extend this analysis to a spatio-temporal 3-D pyramidal coding scheme. We tackle the compatibility problem of optimizing full-resolution quality while simultaneously catering to subresolution bit rate or quality constraints. We show how to obtain fast solutions that provide nearly optimal (typically within 0.3 dB) full resolution quality while providing much better performance for the subresolution layer (typically 2-3 dB better than the full-resolution optimal solution).

We show a rate-distortion optimal way to threshold or drop the DCT coefficients of the JPEG and MPEG compression standards. Our optimal algorithm uses a fast dynamic programming recursive structure. The primary advantage of our approach lies in its complete compatibility with standard JPEG and MPEG decoders.

The use of multiresolution (MR) joint source-channel coding in the context of digital terrestrial broadcasting of high-definition television (HDTV) is shown to be an efficient alternative to single-resolution techniques, which suffer from a sharp threshold effect in the fringes of the broadcast area. It is shown how matched multiresolution source and channel coding can provide a stepwise graceful degradation and improve the behavior, in terms of coverage and robustness of the transmission scheme, over systems not specifically designed for broadcast situations. The alternative available for multiresolution transmission through embedded modulation and error correction codes are examined. It is also shown how multiresolution trellis-coded modulation (TCM) can be used to increase coverage range. Coding results and simulations of noisy transmission are presented, and tradeoffs are discussed.>

A fast rate-distortion (R-D) optimal scheme for coding adaptive trees whose individual nodes spawn descendents forming a disjoint and complete basis cover for the space spanned by their parent nodes is presented. The scheme guarantees operation on the convex hull of the operational R-D curve and uses a fast dynamic programing pruning algorithm to markedly reduce computational complexity. Applications for this coding technique include R. Coefman et al.'s (Yale Univ., 1990) generalized multiresolution wavelet packet decomposition, iterative subband coders, and quadtree structures. Applications to image processing involving wavelet packets as well as discrete cosine transform (DCT) quadtrees are presented.

A practical end-to-end all-digital multiresolution system is demonstrated that employs joint source-channel coding and modulation in order to achieve efficient broadcast of digital HDTV. The threshold effect plaguing single resolution systems is softened by a stepwise graceful degradation. This can be used to increase the coverage and robustness of the digital broadcast system. This approach is seen as an alternative to traditional single resolution digital transmission systems which are not designed for broadcast situations, and which suffer from the threshold effect. This paper highlights the benefits of using an embedded multiresolution modulation constellation over a modulation scheme that resorts to time or frequency multiplexing of the broadcast resolutions. Besides showing coding results and simulations of transmission effects, the paper discusses the trade-offs between low and high resolution coverage.