-
Equivalence of Insertion/Deletion Correcting Codes for $d$-dimensional Arrays
Authors:
Evagoras Stylianou,
Lorenz Welter,
Rawad Bitar,
Antonia Wachter-Zeh,
Eitan Yaakobi
Abstract:
We consider the problem of correcting insertion and deletion errors in the $d$-dimensional space. This problem is well understood for vectors (one-dimensional space) and was recently studied for arrays (two-dimensional space). For vectors and arrays, the problem is motivated by several practical applications such as DNA-based storage and racetrack memories. From a theoretical perspective, it is in…
▽ More
We consider the problem of correcting insertion and deletion errors in the $d$-dimensional space. This problem is well understood for vectors (one-dimensional space) and was recently studied for arrays (two-dimensional space). For vectors and arrays, the problem is motivated by several practical applications such as DNA-based storage and racetrack memories. From a theoretical perspective, it is interesting to know whether the same properties of insertion/deletion correcting codes generalize to the $d$-dimensional space. In this work, we show that the equivalence between insertion and deletion correcting codes generalizes to the $d$-dimensional space. As a particular result, we show the following missing equivalence for arrays: a code that can correct $t_\mathrm{r}$ and $t_\mathrm{c}$ row/column deletions can correct any combination of $t_\mathrm{r}^{\mathrm{ins}}+t_\mathrm{r}^{\mathrm{del}}=t_\mathrm{r}$ and $t_\mathrm{c}^{\mathrm{ins}}+t_\mathrm{c}^{\mathrm{del}}=t_\mathrm{c}$ row/column insertions and deletions. The fundamental limit on the redundancy and a construction of insertion/deletion correcting codes in the $d$-dimensional space remain open for future work.
△ Less
Submitted 10 August, 2022;
originally announced August 2022.
-
Characterization of the Gray-Wyner Rate Region for Multivariate Gaussian Sources: Optimality of Gaussian Auxiliary RV
Authors:
Evagoras Stylianou,
Charalambos D. Charalambous,
Jan H. van Schuppen
Abstract:
Examined in this paper, is the Gray and Wyner achievable lossy rate region for a tuple of correlated multivariate Gaussian random variables (RVs) $X_1 : Ω\rightarrow {\mathbb R}^{p_1}$ and $X_2 : Ω\rightarrow {\mathbb R}^{p_2}$ with respect to square-error distortions at the two decoders. It is shown that among all joint distributions induced by a triple of RVs $(X_1,X_2, W)$, such that…
▽ More
Examined in this paper, is the Gray and Wyner achievable lossy rate region for a tuple of correlated multivariate Gaussian random variables (RVs) $X_1 : Ω\rightarrow {\mathbb R}^{p_1}$ and $X_2 : Ω\rightarrow {\mathbb R}^{p_2}$ with respect to square-error distortions at the two decoders. It is shown that among all joint distributions induced by a triple of RVs $(X_1,X_2, W)$, such that $W : Ω\rightarrow {\mathbb W} $ is the auxiliary RV taking continuous, countable, or finite values, the Gray and Wyner achievable rate region is characterized by jointly Gaussian RVs $(X_1,X_2, W)$ such that $W $ is an $n$-dimensional Gaussian RV. It then follows that the achievable rate region is parametrized by the three conditional covariances $Q_{X_1,X_2|W}, Q_{X_1|W}, Q_{X_2|W}$ of the jointly Gaussian RVs. Furthermore, if the RV $W$ makes $X_1$ and $X_2$ conditionally independent, then the corresponding subset of the achievable rate region, is simpler, and parametrized by only the two conditional covariances $Q_{X_1|W}, Q_{X_2|W}$. The paper also includes the characterization of the Pangloss plane of the Gray-Wyner rate region along with the characterizations of the corresponding rate distortion functions, their test-channel distributions, and structural properties of the realizations which induce these distributions.
△ Less
Submitted 16 May, 2022;
originally announced May 2022.
-
Structural Properties of Optimal Test Channels for Gaussian Multivariate Partially Observable Distributed Sources
Authors:
Michail Gkagkos,
Evagoras Stylianou,
Charalambos D. Charalambous
Abstract:
In this paper, we analyze the operational information rate distortion function (RDF) ${R}_{S;Z|Y}(Δ_X)$, introduced by Draper and Wornell, for a triple of jointly independent and identically distributed, multivariate Gaussian random variables (RVs), $(X^n, S^n, Y^n)= \{(X_{t}, S_t, Y_{t}): t=1,2, \ldots,n\}$, where $X^n$ is the source, $S^n$ is a measurement of $X^n$, available to the encoder,…
▽ More
In this paper, we analyze the operational information rate distortion function (RDF) ${R}_{S;Z|Y}(Δ_X)$, introduced by Draper and Wornell, for a triple of jointly independent and identically distributed, multivariate Gaussian random variables (RVs), $(X^n, S^n, Y^n)= \{(X_{t}, S_t, Y_{t}): t=1,2, \ldots,n\}$, where $X^n$ is the source, $S^n$ is a measurement of $X^n$, available to the encoder, $Y^n$ is side information available to the decoder only, $Z^n$ is the auxiliary RV available to the decoder, with respect to the square-error fidelity, between the source $X^n$ and its reconstruction $\widehat{X}^n$. We also analyze the RDF ${R}_{S;\widehat{X}|Y}(Δ_X)$ that corresponds to the above set up, when side information $Y^n$ is available to the encoder and decoder. The main results include,
(1) Structural properties of test channel realizations that induce distributions, which achieve the two RDFs,
(2) Water-filling solutions of the two RDFs, based on parallel channel realizations of test channels,
(3) A proof of equality ${R}_{S;Z|Y}(Δ_X) = {R}_{S;\widehat{X}|Y}(Δ_X)$, i.e., side information $Y^n$ at both the encoder and decoder does not incur smaller compression, and
(4) Relations to other RDFs, as degenerate cases, which show past literature, contain oversights related to the optimal test channel realizations and value of the RDF ${R}_{S;Z|Y}(Δ_X)$.
△ Less
Submitted 31 August, 2021; v1 submitted 30 August, 2021;
originally announced August 2021.
-
Joint Nonanticipative Rate Distortion Function for a Tuple of Random Processes with Individual Fidelity Criteria
Authors:
Charalambos D. Charalambous,
Evagoras Stylianou
Abstract:
The joint nonanticipative rate distortion function (NRDF) for a tuple of random processes with individual fidelity criteria is considered. Structural properties of optimal test channel distributions are derived. Further, for the application example of the joint NRDF of a tuple of jointly multivariate Gaussian Markov processes with individual square-error fidelity criteria, a realization of the rep…
▽ More
The joint nonanticipative rate distortion function (NRDF) for a tuple of random processes with individual fidelity criteria is considered. Structural properties of optimal test channel distributions are derived. Further, for the application example of the joint NRDF of a tuple of jointly multivariate Gaussian Markov processes with individual square-error fidelity criteria, a realization of the reproduction processes which induces the optimal test channel distribution is derived, and the corresponding joint NRDF is characterized. The analysis of the simplest example, of a tuple of scalar correlated Markov processes, illustrates many of the challenging aspects of such problems.
△ Less
Submitted 29 March, 2021;
originally announced March 2021.
-
Joint Rate Distortion Function of a Tuple of Correlated Multivariate Gaussian Sources with Individual Fidelity Criteria
Authors:
Evagoras Stylianou,
Charalambos D. Charalambous,
Themistoklis Charalambous
Abstract:
In this paper we analyze the joint rate distortion function (RDF), for a tuple of correlated sources taking values in abstract alphabet spaces (i.e., continuous) subject to two individual distortion criteria. First, we derive structural properties of the realizations of the reproduction Random Variables (RVs), which induce the corresponding optimal test channel distributions of the joint RDF. Seco…
▽ More
In this paper we analyze the joint rate distortion function (RDF), for a tuple of correlated sources taking values in abstract alphabet spaces (i.e., continuous) subject to two individual distortion criteria. First, we derive structural properties of the realizations of the reproduction Random Variables (RVs), which induce the corresponding optimal test channel distributions of the joint RDF. Second, we consider a tuple of correlated multivariate jointly Gaussian RVs, $X_1 : Ω\rightarrow {\mathbb R}^{p_1}, X_2 : Ω\rightarrow {\mathbb R}^{p_2}$ with two square-error fidelity criteria, and we derive additional structural properties of the optimal realizations, and use these to characterize the RDF as a convex optimization problem with respect to the parameters of the realizations. We show that the computation of the joint RDF can be performed by semidefinite programming. Further, we derive closed-form expressions of the joint RDF, such that Gray's [1] lower bounds hold with equality, and verify their consistency with the semidefinite programming computations.
△ Less
Submitted 7 May, 2021; v1 submitted 14 February, 2021;
originally announced February 2021.
