In this paper, we consider the (N,K,L) multi-access caching network where K users and K caches are connected to a server with N files, each of size F bits, through a shared error-free broadcast channel. Each user has access to L nearby caches, each of size MF bits, in a cyclic wrap-around manner. Even after several previous attempts, the exact characterization of the optimal rate memory tradeoff is still an open problem except in the case where L = K − 1 and L = 1 with large cache $M \in \left[ {\frac{N}{L} \cdot \frac{{K - 1}}{K},\frac{N}{L}} \right]$. This paper determines the optimal rate memory tradeoff for the cache network with L = K − 2 and $M \in \left[ {\frac{N}{{K - 2}} \cdot \frac{{K - 1}}{K},\frac{N}{{K - 2}}} \right]$. This is done by proposing a new caching scheme that operates at the memory rate pair $\left( {\frac{N}{{K - 2}},\frac{{K - 1}}{K},\frac{1}{K}} \right)$ and deriving a set of lower bounds to demonstrate the optimality of the scheme.

The idea of coded caching for content distribution networks was introduced by Maddah-Ali and Niesen, who considered the canonical$(N, K)$cache network in which a server with$N$files satisfies the demands of$K$users (each equipped with an independent cache of size$M$). The optimal rate memory tradeoff for demands where all files are requested by at least one user has been characterized only for small caches where$M\leq \frac {1}{K}$and large caches where$M\geq N-\frac {N}{K}$. For the case$N \leq K \leq 2N-1$, we derive new lower bounds for small and large caches and propose a new coded caching scheme for large caches. Along with the scheme proposed by Gómez-Vilardebó, this leads to a characterization of the optimal rate memory tradeoff for$M\leq \frac {1}{K}+\frac {1}{K(N-1)}$and$M\geq N-\frac {N}{K}-\frac {N-1}{K(K-1)}$. For the case$2N-1\leq K$, we derive a new lower bound for large caches, which proves the optimality of the scheme proposed by Yu et al. and leads to a characterization of the optimal rate memory tradeoff for$M\geq N-\frac {2N}{K}$. We also derive a new lower bound for small caches, which improves upon previously known lower bounds.

The problem of coded caching was introduced by Maddah-Ali and Niesen and has been extensively studied in recent years. The problem is fundamentally a multi-objective optimization problem where the rates achieved for each demand type is of interest and Pareto optimality is a natural framework. Under the constraint that the placement phase is uncoded, Yu et al. introduced the YMA scheme which was shown to be universal for all demand types. Vijith et al. showed that there are no universal schemes when coded placement is permitted and introduced the problem of finding Pareto optimal schemes. In this paper we study the possibility of finding schemes that dominate the YMA scheme and demonstrate, rather surprisingly, that they continue to operate at the Pareto optimal frontier of coded caching for (N, K) cache networks when$K$≤ 3. We introduce new lower bounds which partially characterize the tradeoffs between different demand types.

Maddah-Ali and Niesen, in a seminal paper, introduced the notion of coded caching. The exact nature of the fundamental limits in this context has remained elusive even as several approximate characterizations have been found. A new optimal scheme for the (3, 3) cache network, operating at the memory rate pair (5/3, 1/2) for the demand where all the users request for distinct files, was introduced recently to partially address this issue. In this paper, an extension of this scheme to the general (K, K) cache network, operating at the memory rate pair ((K2-K -1)/K, 1/(K -1), is proposed. A new lower bound is also derived which demonstrates the optimality of the proposed scheme for the demand where all the users request for distinct files.

Maddah-Ali and Niesen, in a seminal work, initiated the study of rate memory tradeoff for a canonical cache network which operates via a placement phase and a delivery phase. While considering the case of placement phase being uncoded, Yu et al. proved the surprising result of the existence of a universal code, a code which is simultaneously optimal for all demand types. In this paper, we prove that universal codes do not exist when coding is permitted in the placement phase. As part of our proof, we introduce new kinds of lower bounds. In these lower bounds, instead of considering one demand type at a time, we consider several demand types simultaneously. These bounds give us better insight into how the performance for one demand type affects the performance for the other demand types. The non-existence of a universal scheme motivates us to introduce the notion of Pareto optimal schemes, and we prove that Chen's scheme is Pareto optimal.

We propose a patch-based algorithm for demosaicking a mosaicked color image produced by color filter arrays commonly used in acquiring color images. The proposed algorithm exploits a joint color space Gaussian mixture model (JCS-GMM) prior for jointly characterizing the patches from red, green, and blue channels of a color image. The inter channel correlations captured by the covariance matrices of Gaussian models are exploited to estimate the pixel values missing in the mosaicked image. The proposed JCS-GMM demosaicking algorithm can be seen as the GMM analogue of the Color-KSVD algorithm, which has produced impressive results in color image denoising and demosaicking. We demonstrate that our proposed algorithm achieves superior performance in the case of Kodak and Laurent Condat's databases, and competitive performance in the case of IMAX database, when compared with state-of-the-art demosaicking algorithms.

Single image super-resolution (SR) algorithms based on joint dictionaries and sparse representations of image patches have received significant attention in the literature and deliver the state-of-the-art results. Recently, Gaussian mixture models (GMMs) have emerged as favored prior for natural image patches in various image restoration problems. In this paper, we approach the single image SR problem by using a joint GMM learnt from concatenated vectors of high and low resolution patches sampled from a large database of pairs of high resolution and the corresponding low resolution images. Covariance matrices of the learnt Gaussian models capture the inherent correlations between high and low resolution patches, which are utilized for inferring high resolution patches from given low resolution patches. The proposed joint GMM method can be interpreted as the GMM analogue of joint dictionary-based algorithms for single image SR. We study the performance of the proposed joint GMM method by comparing with various competing algorithms for single image SR. Our experiments on various natural images demonstrate the competitive performance obtained by the proposed method at low computational cost.

Recovery of original images from degraded and noisy observations is considered an important task in image processing. Recently, a Piece-wise Linear Estimator (PLE) was proposed for image recovery by using Gaussian Mixture Model (GMM) as a prior for image patches. Despite having much lesser computational requirements, this method yields comparable or better results when compared with the widely used sparse representation techniques for image restoration. In many situations, we might have access to multiple degraded copies of the same image, and would like to exploit the correlation among them for better image recovery. In this work, we extend the GMM based method to the multiple observations scenario, where we estimate the original image by utilizing the collective information available from all degraded copies.

The sliding window Lempel–Ziv (SWLZ) algorithm has been studied extensively in the information theory literature and has been used in several commercial compression packages. The asymptotic behavior of this algorithm has been studied by Wyner and Ziv and by Shields using different approaches. Shields' results proving asymptotic optimality for all individual sequences with respect to the class of all finite state encoders is known to imply the almost sure asymptotic optimality for the class of stationary and ergodic sources. We establish the almost sure asymptotic optimality (without any mixing conditions) by extending the ideas of Wyner and Ziv using results on recurrence times from ergodic theory. A nonuniversal fixed shift version of the algorithm is introduced to gain more insight into its behavior. Pointwise optimality results are also obtained for several variants based on match-length functions introduced by Gavish and Lempel. We also propose variants of the algorithm for sources with countable alphabet and demonstrate their pointwise optimality.

The application of universal source coding algorithms to the problem of classification was initiated by Ziv and has been extended to other problems in statistics such as order estimation. In spite of the large literature, these studies have been limited to problems with fixed number of samples. In this paper we study the application of universal source coding to the problem of sequential hypothesis testing and sequential change detection. Algorithms are proposed which are inspired by Waldpsilas Sequential Probability Ratio Test (SPRT) and Pagepsilas Cumulative Sum Test (CUSUM) for these problems respectively. Performance of the proposed algorithms are studied in the asymptotic regime to demonstrate their effectiveness.