Learning-based denoising algorithms achieve state-of-the-art performance across various denoising tasks. However, training such models relies on access to large training datasets consisting of clean and noisy image pairs. On the other hand, in many imaging applications, such as microscopy, collecting ground truth images is often infeasible. To address this challenge, researchers have recently developed algorithms that can be trained without requiring access to ground truth data. However, training such models remains computationally challenging and still requires access to large noisy training samples. In this work, inspired by compression-based denoising and recent advances in neural compression, we propose a new compression-based denoising algorithm, which we name DeCompress, that i) does not require access to ground truth images, ii) does not require access to large training dataset - only a single noisy image is sufficient, iii) is robust to overfitting, and iv) achieves superior performance compared with zero-shot or unsupervised learning-based denoisers.

Zero-shot denoising aims to denoise observations without access to training samples or clean reference images. This setting is particularly relevant in practical imaging scenarios involving specialized domains such as medical imaging or biology. In this work, we propose the *Zero-Shot Neural Compression Denoiser* (ZS-NCD), a novel denoising framework based on neural compression. ZS-NCD treats a neural compression network as an untrained model, optimized directly on patches extracted from a single noisy image. The final reconstruction is then obtained by aggregating the outputs of the trained model over overlapping patches. Thanks to the built-in entropy constraints of compression architectures, our method naturally avoids overfitting and does not require manual regularization or early stopping. Through extensive experiments, we show that ZS-NCD achieves state-of-the-art performance among zero-shot denoisers for both Gaussian and Poisson noise, and generalizes well to both natural and non-natural images. Additionally, we provide new finite-sample theoretical results that characterize upper bounds on the achievable reconstruction error of general maximum-likelihood compression-based denoisers. These results further establish the theoretical foundations of compression-based denoising. Our code is available at: https://github.com/Computational-Imaging-RU/ZS-NCDenoiser.

Abstract. Snapshot compressive imaging (SCI) refers to the recovery of three-dimensional data cubes, such as videos or hyperspectral images, from their two-dimensional projections, which are generated by a special encoding of the data with a mask. SCI systems commonly use binary-valued masks that follow certain physical constraints. Optimizing these masks subject to these constraints is expected to improve system performance. While prior theoretical analysis of SCI systems has primarily focused on independent and identically distributed Gaussian masks, recent empirical, data-driven mask optimizations yield structured and sometimes interpretable patterns. However, such empirical optimizations typically involve computationally intensive joint procedures that are expected to be suboptimal due to the nonconvexity and complexity of the optimization. In this paper, we analytically characterize the performance of SCI systems employing binary masks and leverage our analysis to optimize hardware parameters. Our findings provide a comprehensive and fundamental understanding of the role of binary masks, with both independent and dependent elements, and their optimization. We also present simulation results that confirm our theoretical findings and further illuminate different aspects of mask design.

We investigate both the theoretical and algorithmic aspects of likelihood-based methods for recovering a complex-valued signal from multiple sets of measurements, referred to as looks, affected by speckle (multiplicative) noise. Our theoretical contributions include establishing the first existing theoretical upper bound on the Mean Squared Error (MSE) of the maximum likelihood estimator under the deep image prior hypothesis. Our theoretical results capture the dependence of MSE upon the number of parameters in the deep image prior, the number of looks, the signal dimension, and the number of measurements per look. On the algorithmic side, we introduce the concept of bagged Deep Image Priors (Bagged-DIP) and integrate them with projected gradient descent. Furthermore, we show how employing Newton-Schulz algorithm for calculating matrix inverses within the iterations of PGD reduces the computational complexity of the algorithm. We will show that this method achieves the state-of-the-art performance.

Snapshot compressive imaging (SCI) recovers high-dimensional (3D) data cubes from a single 2D measurement, enabling diverse applications like video and hyperspectral imaging to go beyond standard techniques in terms of acquisition speed and efficiency. In this paper, we focus on SCI recovery algorithms that employ untrained neural networks (UNNs), such as deep image prior (DIP), to model source structure. Such UNN-based methods are appealing as they have the potential of avoiding the computationally intensive retraining required for different source models and different measurement scenarios. We first develop a theoretical framework for characterizing the performance of such UNN-based methods. The theoretical framework, on the one hand, enables us to optimize the parameters of data-modulating masks, and on the other hand, provides a fundamental connection between the number of data frames that can be recovered from a single measurement to the parameters of the untrained NN. We also employ the recently proposed bagged-deep-image-prior (bagged-DIP) idea to develop SCI Bagged Deep Video Prior (SCI-BDVP) algorithms that address the common challenges faced by standard UNN solutions. Our experimental results show that in video SCI our proposed solution achieves state-of-the-art among UNN methods, and in the case of noisy measurements, it even outperforms supervised solutions. Code is publicly available at [https://github.com/Computational-Imaging-RU/SCI-BDVP](https://github.com/Computational-Imaging-RU/SCI-BDVP).

This paper presents a correction to Theorem 2 in[1]which follows from fixing an error inLemma 5 and aminor correction in the constant ofLemma 3. Despite modifications to upper bounds and constants, the core conclusions of the original paper remain unaffected. The revised proofs now feature precise constants for clarity, maintaining the original findings’ integrity.

Speckle or multiplicative noise is a critical issue in coherence-based imaging systems, such as synthetic aperture radar and optical coherence tomography. Existence of speckle noise considerably limits the applicability of such systems by degrading their performance. On the other hand, the sophistications that arise in the study of multiplicative noise have so far impeded theoretical analysis of such imaging systems. As a result, the current acquisition technology relies on heuristic solutions, such as oversampling the signal and converting the problem into a denoising problem with multiplicative noise. This paper attempts to bridge the gap between theory and practice by providing the first theoretical analysis of such systems. To achieve this goal the log-likelihood function corresponding to measurement systems with speckle noise is characterized. Then employing compression codes to model the source structure, for the case of under-sampled measurements, a compression-based maximum likelihood recovery method is proposed. The mean squared error (MSE) performance of the proposed method is characterized and is shown to scale as$O\left({\sqrt {\frac{k \log n }{ m}}}\right)$, where$k$,$m$and$n$denote the intrinsic dimension of the signal class according to the compression code, the number of observations, and the ambient dimension of the signal, respectively. This result, while in contrast to imaging systems with additive noise in which MSE scales as$O\left({{\frac{k \log n }{ m}}}\right)$, suggests that if the signal class is structured (i.e.,$k \ll n$), accurate recovery of a signal from under-determined measurements is still feasible, even in the presence of speckle noise. Simulation results are presented that suggest image recovery under multiplicative noise is inherently more challenging than additive noise, and that the derived theoretical results are sharp.

Compressive phase retrieval refers to the problem of recovering a structured n-dimensional complex-valued vector from its phase-less under-determined linear measurements. The non-linearity of the measurement process makes designing theoretically-analyzable efficient phase retrieval algorithms challenging. As a result, to a great extent, existing recovery algorithms only take advantage of simple structures such as sparsity and its convex generalizations. The goal of this article is to move beyond simple models through employing compression codes. Such codes are typically developed to take advantage of complex signal models to represent the signals as efficiently as possible. In this work, it is shown how an existing compression code can be treated as a black box and integrated into an efficient solution for phase retrieval. First, COmpressive PhasE Retrieval (COPER) optimization, a computationally-intensive compression-based phase retrieval method, is proposed. COPER provides a theoretical framework for studying compression-based phase retrieval. The number of measurements required by COPER is connected to κ, the α-dimension (closely related to the ratedistortion dimension) of a given family of compression codes. To finds the solution of COPER, an efficient iterative algorithm called gradient descent for COPER (GD-COPER) is proposed. It is proven that under some mild conditions on the initialization and the compression code, if the number of measurements is larger than Cκ2log2n, where C is a constant, GD-COPER obtains an accurate estimate of the input vector in polynomial time. In the simulation results, JPEG2000 is integrated in GD-COPER to confirm the state-of-the-art performance of the resulting algorithm on real-world images.

Noiseless compressed sensing refers to the problem of recovering a (high-dimensional) signal from its under-determined linear measurements. For compressed sensing to be feasible, the signal needs to be structured. While the main focus of the field has been on simple structures such as sparsity, there has been a growing interest in moving beyond sparsity and having a comprehensive compressed sensing framework that covers general structures. Two recent approaches that aim at developing such a framework from different perspectives are i) Quantized maximum a posteriori (Q-MAP), a Bayesian method that assumes full knowledge of the source distribution, and ii) Lagrangian minimum entropy pursuit (L-MEP), a universal recovery method that requires no prior knowledge about the distribution of the source. In this paper, by establishing theoretical connections between L-MEP and Q-MAP, it is shown how the two methods are complementary to each other and lead to a theoretically-founded learning-based recovery method that applies to sources with general structures. Unlike a Bayesian or a universal method, a learning-based method is able to extract the source structure from training data. The effect of error in estimating the source structure on the performance of the learning-based compressed sensing recovery method is characterized.

Clustering mixtures of Gaussian distributions is a fundamental and challenging problem. State-of-the-art theoretical work on learning Gaussian mixture models has mostly focused on estimating the mixture parameters, where clustering is given as a byproduct. These methods have focused mostly on improving separation bounds for different mixture classes, and doing so in polynomial time and sample complexity. Less emphasis has been given to aligning these algorithms to the challenges of big data. In this paper, we focus on clustering $n$ samples from an arbitrary mixture of $c$-separated Gaussians in $\mathbb{R}^p$ in time that is linear in $p$ and $n$, and sample complexity that is independent of $p$. Our analysis suggests that for sufficiently separated Gaussians after $o(\log{p})$ random projections a good direction is found that yields a small clustering error. Specifically, for a user-specified error $e$, the expected number of such projections is small and bounded by $o(\ln p)$ when $\gamma\leq c\sqrt{\ln{\ln{p}}}$ and $\gamma=Q^{-1}(e)$ is the separation of the Gaussians with $Q$ as the tail distribution function of the normal distribution. Consequently, the expected overall running time of the algorithm is linear in $n$ and quasi-linear in $p$ at $o(\ln{p})O(np)$, and the sample complexity is independent of $p$. Unlike the methods that are based on $k$-means, our analysis is applicable to any mixture class (spherical or non-spherical). Finally, an extension to $k>2$ components is also provided.

Compressed sensing (CS) algorithms recover a signal from its under-determined linear measurements via exploiting its structure. Starting from sparsity, recovery methods have steadily moved towards more complex structures. Emerging machine learning tools, e.g., generative models that are based on neural nets, potentially learn general complex structures from training data. Inspired by the success of such models in various computer vision tasks, researchers in CS have recently started to employ them to design efficient recovery methods. Consider a generative model defined by function g : Uk→ Rn, where U denotes a bounded subset of R. Assume that the function g is trained such that it can describe the class of desired signals Q c Rn. The standard problem in noiseless CS is to recover x ∈ Q from under-determined linear measurements y = Ax, where y ∈ Rmand mu∈Uk||g(u) - x||. Finally, using projected gradient descent to solve the aforementioned optimization, some preliminary numerical results are reported.

Denoising a stationary process (Xi)i∈Zcorrupted by additive white Gaussian noise (Zi)i∈Z, i.e., recovering Xn from Yn= Xn+ Zn, is a classic and fundamental problem in information theory and statistical signal processing. Theoretically-founded and computationally-efficient denoising algorithms which are applicable to general sources are yet to be found. In a Bayesian setup, given the distribution of Xn, a minimum mean square error (MMSE) denoiser computes E[Xn|Yn]. However, for general sources, computing E[Xn|Yn] is computationally very challenging, if not infeasible. In this paper, starting from a Bayesian setup, a novel denoiser, namely, quantized maximum a posteriori (Q-MAP) denoiser, is proposed and its asymptotic performance is analyzed. Both for memoryless sources, and for structured first-order Markov sources, it is shown that, asymptotically, as σ2(noise variance) converges to zero, 1/σ2E[(Xi-XQ-MAP)2] converges to the information dimension of the source. For the studied memoryless sources, this limit is known to be optimal. A key advantage of the QMAP denoiser is that, unlike a MMSE denoiser, it highlights the key properties of the source distribution that are to be used in its denoising. This naturally leads to a learning-based denoising algorithm. Using ImageNet database for training, initial simulation results exploring the performance of such a learning-based denoiser in image denoising are presented.

The universal approximation theorem states that any regular function can be approximated closely using a single hidden layer neural network. Some recent work has shown that, for some special functions, the number of nodes in such an approximation could be exponentially reduced with multi-layer neural networks. In this work, we extend this idea to a rich class of functions, namely the discriminant functions that arise in optimal Bayesian classification of Gaussian mixture models (GMMs) in $\mathds{R}^n$. We show that such functions can be approximated with arbitrary precision using $O(n)$ nodes in a neural network with two hidden layers (deep neural network), while in contrast, a neural network with a single hidden layer (shallow neural network) would require at least $O(\exp(n))$ nodes or exponentially large coefficients. Given the universality of the Gaussian distribution in the feature spaces of data, e.g., in speech, image and text, our results shed light on the observed efficiency of deep neural networks in practical classification problems.

Snapshot compressed sensing (CS) refers to compressive imaging systems in which multiple frames are mapped into a single measurement frame. Each pixel in the acquired frame is a noisy linear mapping of the corresponding pixels in the frames that are combined together. While the problem can be cast as a CS problem, due to the very special structure of the sensing matrix, standard CS theory cannot be employed to study such systems. In this paper, a compression-based framework is employed for theoretical analysis of snapshot CS systems. It is shown that this framework leads to two novel, computationally-efficient and theoretically-analyzable compression-based recovery algorithms. The proposed methods are iterative and employ compression codes to define and impose the structure of the desired signal. Theoretical convergence guarantees are derived for both algorithms. In the simulations, it is shown that, in the cases of both noise-free and noisy measurements, combining the proposed algorithms with a customized video compression code, designed to exploit nonlocal structures of video frames, significantly improves the state-of-the-art performance.

Compressive phase retrieval is the problem of recovering a structured vector x ∈ ℂnfrom its phaseless linear measurements. A compression algorithm aims to represent structured signals with as few bits as possible. As a result of extensive research devoted to compression algorithms, in many signal classes, compression algorithms are capable of employing sophisticated structures in signals and compress them efficiently. This raises the following important question: Can a compression algorithm be used to solve a compressive phase retrieval problem? To address this question, COmpressive PhasE Retrieval (COPER) optimization is proposed, which is a compression-based phase retrieval method. For a family of compression codes with rate-distortion function denoted by r(δ), in the noiseless setting, COPER is shown to require slightly more than limδ→0(r(δ))/(log (1/δ)) observations for an almost accurate recovery of x.

One-shot measurement systems combine multiple frames of a signal such as a video into a single frame of the same dimensions. Each element (pixel) in the measured frame is a linear combination of the corresponding elements (pixels) in the combined frames. Such systems are a crucial part of various modern compressive imaging systems with applications ranging from high-speed videos to high-dimensional medical images. In this paper, employing ideas from compression-based compressed sensing, a new theoretical framework for such one-shot compressive imaging systems is proposed. This new framework enables us to show that it is possible to recover frames that are combined under the one-shot measurement paradigm. The number of frames that can be combined and later deconvolved is connected with the level of structured-ness of the original multi-frame signal. This theoretical analysis aims at filling the gap between existing practical compressive imaging systems and traditional compressed sensing theory developed for random and dense sensing matrices.

Universal compressed sensing algorithms recover a “structured” signal from its under-sampled linear measurements, without knowing its distribution. The recently developed minimum entropy pursuit (MEP) optimization suggests a framework for developing universal compressed sensing algorithms. In the noiseless setting, among all signals that satisfy the measurement constraints, MEP seeks the “simplest”. In this work, the effect of noise on the performance of the relaxed version of MEP optimization, namely Lagrangian-MEP, is studied. It is proved that the performance the Lagrangian-MEP algorithm is robust to small additive noise.

A novel low-complexity robust-to-noise iterative algorithm named compression-based gradient descent (C-GD) algorithm is proposed. C-GD is a generic compressed sensing recovery algorithm, that at its core, employs compression codes, such as JPEG2000 and MPEG4. Through using compression codes, C-GD strongly generalizes the scope of structures used by compressed sensing recovery algorithms beyond sparsity or low-rankness. The squared error of the proposed method and its associated convergence is characterized and predicts the strong performance of C-GD. Numerical results suggest that C-GD, when combined with state-of-the-art compression codes, either outperforms or performs comparably to modern compressed sensing recovery methods.

In this paper, the problem of developing universal algorithms for noiseless compressed sensing of stochastic processes is studied. First, Rényi's notion of information dimension (ID) is generalized to continuous-valued discrete-time stationary processes. This provides a measure of complexity for such processes and is connected to the rate of measurement (sampling rate) required for their accurate recovery. Then, based on Occam's razor, a minimum entropy pursuit (MEP) optimization approach for universal compressed sensing is proposed. It is proven that, for any stationary process satisfying certain mixing conditions, if the sampling rate is larger than the ID of the source process, MEP optimization can reliably recover the source vector almost losslessly, without having any prior information about its distribution. Then, a Lagrangian-type relaxation of MEP optimization problem, referred to as Lagrangian-MEP, is studied. It is shown that Lagrangian-MEP is identical to an implementable algorithm proposed by Baron and coauthors, and for the right choice of parameters, has the same asymptotic performance as MEP optimization. Finally, it is proven that Lagrangian-MEP is robust to small measurement noise.

Modern compression codes exploit signals' complex structures to encode them very efficiently. On the other hand, compressed sensing algorithms recover “structured” signals from their under-determined set of linear measurements. Currently, there is a noticeable gap between the types of structures used in the area of compressed sensing and those employed by state-of-the-art compression codes. Recent results in the literature on deterministic signals aim at bridging this gap through devising compressed sensing decoders that employ compression codes. This paper focuses on structured stochastic processes and studies application of lossy compression codes to compressed sensing of such signals. The performance of the formerly proposed compressible signal pursuit (CSP) optimization is studied in this stochastic setting. It is proved that in the low-distortion regime, as the blocklength grows to infinity, the CSP optimization reliably and robustly recovers n instances of a stationary process from its random linear measurements as long as n is slightly more than n times the rate-distortion dimension (RDD) of the source. It is also shown that under some regularity conditions, the RDD of a stationary process is equal to its information dimension. This connection establishes the optimality of CSP at least for memoryless stationary sources, which have known fundamental limits. Finally, it is shown that CSP combined by a family of universal variable-length fixed-distortion compression codes yields a family of universal compressed sensing recovery algorithms.

In this paper, the problem of developing universal algorithms for noiseless compressed sensing of stochastic processes is studied. First, Rényi's notion of information dimension (ID) is generalized to analog stationary processes. This provides a measure of complexity for such processes and is connected to the number of measurements required for their accurate recovery. Then the so-called Lagrangian minimum entropy pursuit (Lagrangian-MEP) algorithm, originally proposed by Baron et al. as a heuristic universal recovery algorithm, is studied. It is shown that, if the normalized number of randomized measurements is larger than the ID of the source process, for the right set of parameters, asymptotically, the Lagrangian-MEP algorithm recovers any stationary process satisfying some mixing constraints almost losslessly, without having any prior information about the source distribution.

The rate-distortion dimension (RDD) of an analog stationary process is studied as a measure of complexity that captures the amount of information contained in the process. It is shown that the RDD of a process, defined as two times the asymptotic ratio of its rate-distortion function R(D) to log 1/D as the distortion D approaches zero, is equal to its information dimension (ID). This generalizes an earlier result by Kawabata and Dembo and provides an operational approach to evaluate the ID of a process, which previously was shown to be closely related to the effective dimension of the underlying process and also to the fundamental limits of compressed sensing. The relation between RDD and ID is illustrated for a piecewise constant process.

Data compression and compressed sensing algorithms exploit the structure present in a signal for its efficient representation and measurement, respectively. While most state-of-the-art data compression codes take advantage of complex patterns present in signals of interest, this is not the case in compressed sensing. This paper explores usage of efficient data compression codes in building compressed sensing recovery methods for stochastic processes. It is proved that for an i.i.d. process, compression-based compressed sensing achieves the fundamental limits in terms of the number of measurements. It is also proved that compressed sensing recovery methods built based on a family of universal compression codes yield a family of universal compressed sensing schemes.

Multi-tier cellular communication networks constitute a promising approach to expand the coverage of cellular networks and enable them to offer higher data rates. In this paper, an uplink two-tier communication network is studied, where macro users, femto users and femto access points are geometrically located inside the coverage area of a macro base station according to Poisson point processes. Each femtocell is assumed to have a fixed backhaul constraint that puts a limit on the maximum number of femto and macro users it can service. Under this backhaul constraint, the network adopts a special open access policy, in which each macro user is either assigned to its closest femto access point or to the macro base station, depending on the ratio between its distances from those two. Under this model, upper and lower bounds on the outage probabilities experienced by users (macro and femto) serviced by femto access points are derived as functions of the distance between the macro base station and the femto access point serving them. The bounds are confirmed via simulation results.

In this paper, we prove the separation of source-network coding and channel coding in wireline networks. For the purposes of this paper, a wireline network is any network of independent, memoryless, point-to-point, and finite-alphabet channels used to transmit dependent sources either losslessly or subject to a distortion constraint. In deriving this result, we also prove that in a general memoryless network with dependent sources, lossless, and zero-distortion reconstruction are equivalent provided that the conditional entropy of each source given the other sources is nonzero. Furthermore, we extend the separation result to the case of continuous-alphabet and point-to-point channels, such as additive white Gaussian noise channels.

Employing multi-tier networks is among the most promising approaches to address the rapid growth of the data demand in cellular networks. In this paper, we study a two-tier uplink cellular network consisting of femtocells and a macrocell. Femto base stations, and femto and macro users are spatially deployed based on independent Poisson point processes. We consider an open access assignment policy, where each macro user based on the ratio between its distances from its nearest femto access point (FAP) and from the macro base station (MBS) is assigned to either of them. By tuning the threshold, this policy allows controlling the coverage areas of FAPs. For a fixed threshold, femtocells coverage areas depend on their distances from the MBS; those closest to the fringes will have the largest coverage areas. Under this open-access policy, ignoring the additive noise, we derive analytical upper and lower bounds on the outage probabilities of femto users and macro users that are subject to fading and path loss. We also study the effect of the distance from the MBS on the outage probability experienced by the users of a femtocell. In all cases, our simulation results comply with our analytical bounds.

The nascent field of compressed sensing is founded on the fact that high-dimensional signals with simple structure can be recovered accurately from just a small number of randomized samples. Several specific kinds of structures have been explored in the literature, from sparsity and group sparsity to low-rankness. However, two fundamental questions have been left unanswered. What are the general abstract meanings of structure and simplicity? Do there exist universal algorithms for recovering such simple structured objects from fewer samples than their ambient dimension? In this paper, we address these two questions. Using algorithmic information theory tools such as the Kolmogorov complexity, we provide a unified definition of structure and simplicity. Leveraging this new definition, we develop and analyze an abstract algorithm for signal recovery motivated by Occam's Razor. Minimum complexity pursuit (MCP) requires approximately 2κ randomized samples to recover a signal of complexity κ and ambient dimension n. We also discuss the performance of the MCP in the presence of measurement noise and with approximately simple signals.

Can compression algorithms be employed for recovering signals from their underdetermined set of linear measurements? Addressing this question is the first step towards applying compression algorithms for compressed sensing (CS). In this paper, we consider a family of compression algorithms CR, parametrized by rate R, for a compact class of signals Q ⊂ Rn. The set of natural images and JPEG2000 at different rates are examples of Q and Cr, respectively. We establish a connection between the rate-distortion performance of CR, and the number of linear measurement required for successful recovery in CS. We then propose compressible signal pursuit (CSP) algorithm and prove that, with high probability, it accurately and robustly recovers signals from an underdetermined set of linear measurements.

A host of problems involve the recovery of structured signals from a dimensionality reduced representation such as a random projection; examples include sparse signals (compressive sensing) and low-rank matrices (matrix completion). Given the wide range of different recovery algorithms developed to date, it is natural to ask whether there exist “universal” algorithms for recovering “structured” signals from their linear projections. We recently answered this question in the affirmative in the noise-free setting. In this paper, we extend our results to the case of noisy measurements.

We propose an approach to lossy compression of finite-alphabet sources that utilizes Markov chain Monte Carlo (MCMC) and simulated annealing methods. The idea is to define an energy function over the space of reconstruction sequences. The energy of a candidate reconstruction sequence is defined such that it incorporates its distortion relative to the source sequence, its compressibility, and the point sought on the rate-distortion curve. The proposed algorithm samples from the Boltzmann distribution associated with this energy function using the "heat-bath" algorithm. The complexity of each iteration is independent of the sequence length and is only linearly dependent on a certain context parameter, which grows sub-logarithmically with the sequence length. We show that the proposed algorithm achieves optimum rate-distortion performance in the limits of large number of iterations, and sequence length, when employed on any stationary ergodic source. Inspired by the proposed block-coding algorithm, we also propose an algorithm for constructing sliding-block (SB) codes using similar ideas.

We present a new lossy compressor for finite-alphabet sources. For coding a sequence xn, the encoder starts by assigning a certain cost to each possible reconstruction sequence. It then finds the one that minimizes this cost and describes it losslessly to the decoder via a universal lossless compressor. The cost of each sequence is a linear combination of its distance from the sequence xnand a linear function of its kthorder empirical distribution. The structure of the cost function allows the encoder to employ the Viterbi algorithm to find the sequence with minimum cost. We identify a choice of the coefficients used in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance for any stationary ergodic source, in the limit of large , provided that increases as o(log n). Iterative techniques for approximating the coefficients, which alleviate the computational burden of finding the optimal coefficients, are proposed and studied.

Characterizing the set of achievable distortions in lossy transmission of dependent sources over multi-user channels is an open problem. Even for a channel such as the multiple access channel, where the capacity is well-understood, the complete characterization of achievable distortions is still unknown. Since separation of source coding and channel coding is sub-optimal for this case, bounds on achievable distortions require tools beyond prior channel capacities and rate-distortion bounds. In this paper we propose a systematic approach for finding lower bounds on the set of distortions achievable through joint source-channel coding.

This paper proves the separation between source-network coding and channel coding in networks of noisy, discrete, memoryless channels. We show that the set of achievable distortion matrices in delivering a family of dependent sources across such a network equals the set of achievable distortion matrices for delivering the same sources across a distinct network which is built by replacing each channel by a noiseless, point-to-point bit-pipe of the corresponding capacity. Thus a code that applies source-network coding across links that are made almost lossless through the application of independent channel coding across each link asymptotically achieves the optimal performance across the network as a whole.

We consider the Wyner-Ziv (WZ) problem of lossy compression where the decompressor observes a noisy version of the source, whose statistics are unknown. A new family of WZ coding algorithms is proposed and their universal optimality is proven. Compression consists of sliding-window processing followed by Lempel-Ziv (LZ) compression, while the decompressor is based on a modification of the discrete universal denoiser (DUDE) algorithm to take advantage of side information. The new algorithms not only universally attain the fundamental limits, but also suggest a paradigm for practical WZ coding. The effectiveness of our approach is illustrated with experiments on binary images, and English text using a low complexity algorithm motivated by our class of universally optimal WZ codes.

We present a new lossy compressor for discrete sources. For coding a source sequence xn, the encoder starts by assigning a certain cost to each reconstruction sequence. It then finds the reconstruction that minimizes this cost and describes it losslessly to the decoder via a universal lossless compressor. The cost of a sequence is given by a linear combination of its empirical probabilities of some order k+1 and its distortion relative to the source sequence. The linear structure of the cost in the empirical count matrix allows the encoder to employ a Viterbi-like algorithm for obtaining the minimizing reconstruction sequence simply. We identify a choice of coefficients for the linear combination in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance of any Markov source in the limit of large n, provided k is increased as o(log n).

We present a new lossy compression algorithm for discrete sources. The encoder assigns a certain cost to each reconstruction sequence, finds the sequence that minimizes the cost, and describes it losslessly to the decoder via a universal lossless compressor. The cost of a sequence is defined as a linear combination of its empirical probabilities of some order k + 1 and its distortion relative to the source sequence. The linear structure of the cost in the empirical count matrix allows the encoder to employ a Viterbi-like algorithm for obtaining the minimizing reconstruction sequence simply. We identify a choice of coefficients for the linear combination in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance of any Markov source in the limit of large n, provided k is increased as o(log n). Finding the optimal coefficients is complex and requires solving a non-convex optimization problem. As a detour, we propose a simple heuristic iterative procedure, and demonstrate its efficiency through our experimental results.

We propose a new approach to lossy source coding. The idea is to sample a reconstruction sequence from a Boltzmann distribution associated with an energy function that incorporates the distortion between the source and reconstruction, the compressibility of the reconstruction, and the point sought on the rate-distortion curve. To sample from this distribution, we use a heat bath algorithm: Starting from an initial candidate reconstruction (say the original source sequence), at every iteration, an index i is chosen and the ith sequence component is replaced by drawing from the conditional probability distribution for that component given all the rest. At the end of this process, the encoder losslessly conveys the reconstruction to the decoder using universal lossless compression. An appropriate choice of the energy function leads to an algorithm whose complexity, in each iteration, is independent of the sequence length and only linearly dependent on a certain context parameter (which grows sub-logarithmically with the sequence length). The algorithm is universal: for any stationary ergodic source, it achieves the optimal rate-distortion performance in the limits of large number of iterations and sequence length. Initial experimentation shows promising performance in practice.

We consider the Wyner-Ziv (WZ) problem of rate- distortion coding with decoder side information, for the case where the source statistics are unknown or non-existent. A new family of WZ coding algorithms is proposed and its universal optimality is proven. Encoding is based on a sliding window operation followed by LZ compression, while decoding is based on a natural extension of the Discrete Universal DEnoiser (DUDE) algorithm to the case where side information is present. The effectiveness of our approach is illustrated with experiments on binary images using a low complexity algorithm motivated by our class of universally optimal WZ codes.

This paper addresses the problem of bounding the rate-distortion function of a binary symmetric Markov source. We derive a sequence of upper and lower bounds on the rate- distortion function of such sources. The bounds are indexed by k, which corresponds to the dimension of the optimization problem involved. We obtain an explicit bound on the difference between the derived upper and lower bounds as a function of k. This allows to identify the value of k that suffices to compute the rate distortion function to a given desired accuracy. In addition to these bounds, a tighter lower bound which is also a function of k is derived. Our numerical results show that the new bounds improve on the Berger's upper and lower bounds even with small values of k.

In this paper, we address the issue of power distribution and decoding order in the uplink side of a multirate code division multiple access (CDMA) system based on linear successive interference cancellation (SIC). First, the closed form expressions for the required received powers at the base station, in order to achieve the users bit rate and quality of service (QoS) requirements, is derived. Then, we investigate the problem of optimal decoding order of the users under imperfect interference cancellation condition and show that optimum decoding order of users, unlike the case of perfect SIC, is a function of their requested SINR values in addition to their path gains. Finally, we derive new criteria for decoding order of users in multirate SIC-based CDMA systems.

In this paper, we will address the issue of power distribution and decoding order in the uplink side of a multirate code division multiple access (CDMA) system based on linear successive interference cancellation (SIC). First, the closed form expressions for the required received powers at the base station, in order to achieve the users bit rate and quality of service (QoS) requirements, will be derived. Then, we will investigate the problem of optimal decoding order of the users under imperfect interference cancellation condition and will show that optimum decoding order of users, unlike the case of perfect SIC, is a function of their requested SINR values in addition to their path gains. Finally, we will derive new criteria for decoding order of users in multirate SIC-based CDMA systems.