Lossy Compression of Decimated Gaussian Random Walks
Georgia Murray Alon Kipnis Andrea J. Goldsmith




Magnetic field dependence of electronic properties of MoS_2 quantum dots with different edges
    F. M. Peeters^2[ Email: francois.peeters@uantwerpen.be]
    December 30, 2023
=============================================================================================

empty
empty


    We consider the problem of estimating a Gaussian random walk from a lossy compression of its decimated version. Hence, the encoder operates on the decimated random walk, and the decoder estimates the original random walk from its encoded version under a mean squared error (MSE) criterion. It is well-known that the minimal distortion in this problem is attained by an estimate-and-compress (EC) source coding strategy, in which the encoder first estimates the original random walk and then compresses this estimate subject to the bit constraint. In this work, we derive a closed-form expression for this minimal distortion as a function of the bitrate and the decimation factor. Next, we consider a compress-and-estimate (CE) source coding scheme, in which the encoder first compresses the decimated sequence subject to an MSE criterion (with respect to the decimated sequence), and the original random walk is estimated only at the decoder. 
    We evaluate the distortion under CE in a closed form and show that there exists a non-zero gap between the distortion under the two schemes. This difference in performance illustrates the importance of having the decimation factor at the encoder. 
    



    Indirect source coding, Gaussian random walk, Wiener process




§ INTRODUCTION 






Consider the situation in which one is interested in compressing or transmitting a data sequence X^N = (X_1,…,X_N), generated by a source X, but can only access its factor M decimated version

    Y_n = X_Mn,   n = 1,…, N/M.


Assuming a compression or communication rate of R bits per symbol to describe X, the encoder has at most RN bits to represent Y^N_M, where N_M≜ N/M. Without loss of generality, we assume here and throughout the paper that N_M is an integer. The problem of finding the NR bit representation that minimizes the MSE with respect to X^N is known as the indirect (or remote) source coding problem. Classical results in source coding <cit.> show that optimal compression is achieved by an estimate-and-compress (EC) strategy: the encoder first computes X^N, the optimal estimate of X^N from its decimated version Y^N_M, and then compresses X^N under a MSE criterion subject to the bit constraint (Fig. <ref>). The resultant expected MSE is called the indirect DRF of X^N given Y^N_M, and we denote it here by D_EC(M,R). As N goes to infinity, D_EC(M,R) is a function of only the bitrate R and the decimation factor M <cit.>.


This work focuses on the fact that, in many situations, the encoder cannot compute X^N. This may be the result of an unknown decimation factor M or a lack of computing resources. When the encoder is unable to estimate X^N prior to encoding, a different scheme known as compress-and-estimate is often employed <cit.>. In this scheme, depicted in Fig. <ref>, the observed decimated sequence Y^N_M is encoded in an optimal manner subject to an MSE criterion. The original sequence X^N is estimated at the decoder from the compressed version of Y^N_M. The distortion under this scheme is denoted as D_CE(M,R) and provides an upper bound for the distortion under EC. That is, it bounds from above the minimal distortion in the indirect source coding problem of X^N given Y^N_M when the decimation factor M is unknown at the encoder.


In this paper we focus on the case where the source X is a standard Gaussian random walk, defined as

    X_n = ∑_i=1^n W_i,   n=1,2,…,

where W_1,…,W_n are standard normal and independent of each other. The process (<ref>) arises as the uniform samples of the Wiener process <cit.>, or the discrete-time Wiener process. Applications of the random walk are many, ranging from diffusion models in physics to option pricing in financial mathematics <cit.>. The main contributions of this paper are closed form expressions of the distortion functions D_EC(M,R) and D_CE(M,R) for the Gaussian random walk X defined by (<ref>). These expressions fully characterize the fundamental limit arising from representing a Gaussian random walk by quantizing its samples at a fixed bitrate, as is necessary when, for example, transmitting them over a rate-limited link. Moreover, we show that for any decimation factor M>1 and bitrate R>0, the distortion under CE is strictly sub-optimal compared to the minimal distortion achieved by EC. That is, the scheme that encodes the decimated sequence Y so as to recover Y with minimal distortion, attains distortion in recovering X that is strictly larger than the scheme that encodes Y so as to recover X with minimal distortion. This result illustrates that, in problems involving inference from lossy compressed information, the optimal lossy compression procedure depends on the end inference problem. As a result, ad-hoc lossy compression techniques that do not take into account the final inference procedure are necessarily sub-optimal. Nevertheless, our results reveal that the difference between D_EC(M,R) and D_CE(M,R) is relatively small, and may be insignificant in many applications.











This paper is organized as follows. In Sec. <ref> we define our general source coding problem and the EC and CE schemes. 
In Sec. <ref> we review relevant known results with respect to our general indirect source coding problem. In Sec. <ref> we characterize the distortion under the EC and CE schemes. In Sec. <ref> we evaluate the resulting distortion expressions numerically and derive conclusions regarding the loss of performance when the decimation factor is unknown to the encoder. Finally, we provide concluding remarks and discuss future work in Sec. <ref>.









§ PROBLEM FORMULATION 

We consider the source coding problem described in Figs. <ref> and <ref>. In this problem, the standard Gaussian random walk X of (<ref>) is decimated by a factor M to yield the process Y. Note that Y is also a Gaussian random walk, though with variance M rather than unit variance. For a time horizon N, the vector Y^N_M is encoded using the encoder 

    f : ℝ^N_M→{0,1}^NR.

The decoder g :  {0,1}^NR→ℝ^N receives the binary word at the output of the encoder and provides a reconstruction sequence X^N = g(f(Y^N_M)). The distortion is defined as the normalized MSE between X^N and X^N:

    D_f,g≜1/N∑_n=1^N 𝔼(X_n - X_n )^2.

Our goal in this paper is to characterize D_f,g in the limit as N →∞ under two different of encoder and decoder designs: the optimal design which has knowledge of the decimation factor at the encoder and decoder, and a suboptimal design which does not have this knowledge at the encoder. 









 §.§ Optimal Source Coding via EC

The optimal source coding performance with respect to the source coding problem of Fig. <ref> is defined as the minimum of D_f,g under all pairs of encoders and decoders. Since the encoder in this problem has no direct access to the signal X^N it aims to accurately represent, the characterization of this minimal distortion is an indirect source coding problem <cit.>. Classical results in source coding show that the minimum of D_f,g is attained by the EC strategy illustrated in Fig. <ref>. That is, the encoder first estimates X^N from the observed signal Y^N_M, and then compresses this estimated version in an optimal manner as in classical source coding <cit.>. 
For this reason, we set

    D_EC(M,R) ≜lim inf_N→∞inf_f,g D_f,g.

D_EC(M,R) is called the indirect DRF of the process X given the process Y as it describes the asymptotic optimal performance in indirect source coding.



 §.§ CE Source Coding

The CE scheme is defined by a particular sequence of encoders that generally differ from the optimal one used in EC. Specifically, the encoder f_CE in CE is a minimum distance encoder with respect to a set of 2^NR codewords drawn from the distribution that attains the DRF of the Gaussian vector Y^N_M at bitrate not exceeding R. The decoder g_CE receives the index of the codeword ŷ^N_M nearest to the input sequence and outputs x̂^N, obtained by linearly interpolating ŷ^N_M as in

    x_n = M-n/My_n^- + n/My_n^+,   n=1,…,N,

where n^+ = ⌈n/M⌉ and n^- = ⌊n/M⌋. Note that in the CE setting, although the encoding is optimal with respect to Y^N_M, it is not necessarily optimal with respect to X^N. However, the decimation factor M is not used by the encoder in CE, and hence this scheme may be useful when M is unknown. A distortion D is said to be achievable under CE if there exists a sequence of encoders of the form f_CE such that D_f,g converges to D as N→∞. We denote by D_CE(M,R) the infimum over all achievable distortions under CE. 


















§ BACKGROUND 

In this section we review relevant known results for encoding the Gaussian random walk X^N of (<ref>). Since X^N is Gaussian and Markovian, the minimal MSE (MMSE) estimate of X^N from Y^N_M is simply the interpolation of the decimated version. That is

    X_n ≜𝔼[X_n | Y^N_M] 
        = M-n/M Y_n^- + n/M Y_n^+,   n=1,2,…,

where n^+ = ⌈n/M⌉ and n^- = ⌊n/M⌋. The resulting MMSE, which we denote by (M), is given by

    (M) ≜1/N∑_n=1^N 𝔼(X_n - X_n )^2  =M-M^-1/6.

 Note that due to the properties of conditional expectation, for any encoder f : ℝ^N_M→{1,…,2^NR} 
we have

    (X^N| f(Y^N_M) )    
     =     (M) + ( X^N | f(Y^N_M)).

Therefore, (M) is a trivial lower bound to the functions D_EC(M,R) and D_CE(M,R). Moreover, as explained in <cit.>, it follows from (<ref>) that the minimal distortion in estimating X^N from any NR-bit representation of Y^M/N is attained by the optimal encoding of X^N subject to this bit constraint. Hence, the EC scheme, in which the encoder first estimates X^N and then encodes it, is optimal. 


Another, trivial lower bound to D_EC(M,R) and D_CE(M,R) is given by the (standard) DRF of the process X. This DRF is defined as the limit infimum as N→∞ of the normalized distortion of the Gaussian vector X^N. The latter is given via Kolmogorov's expression <cit.> 

 

    D_X^N(θ)    = 1/N∑_k=1^N min[θ, λ_k]
    
        R_X^N(θ)    = 1/2N∑_k=1^N max[0, log (λ_k/θ)],



where λ_k's are the eigenvalues of the covariance matrix Σ_X^N of X^N. In our case of X^N as a standard Gaussian random walk, Berger <cit.> showed that

    λ_k =  [2 sin (2k-1/2N+1π/2 )  ]^-2,      k = 0, ..., N-1,

 and concluded, upon taking the limit in (<ref>), that



    D_X(R_θ)     = ∫_0^1 min{θ, S(ϕ) } dϕ
    
        R_θ    =  1/2∫_0^1 max{0,log(S(ϕ)/θ) }dϕ,


where S(ϕ) = (2 sin( πϕ/2 ) )^-2 is the asymptotic density of the eigenvalues of Σ_X^N.



§ DISTORTION UNDER EC AND CE 

We now derive our main results by characterizing the distortion under EC and CE in recovering the random walk X from its decimated version Y. 




 §.§ Estimate-and-Compress

From the definition of D_EC(M,R) and the decomposition (<ref>), it follows that 


    D_EC(M,R)    = (M) + lim inf_N→∞inf_f(X^N|f(Y^N_M)) 
        = (M) +  D_X(R),


where D_X(R) is the DRF of the process X. Therefore, characterizing the distortion in EC is obtained by solving a source coding problem with respect to X. Now the process B defined as B_n ≜( X_n - X_n ) returns to zero at least every M steps and has average variance equals to (M). Hence the variance of X_n = X_n - B_n increases at the same rate as the variance of X_n, and Berger's coding theorem for X_n <cit.> can be applied to X_n. Therefore, the DRF of X is given by the limiting expression for the DRF of the Gaussian vector X^N, using Kolmogorov's expression (<ref>) leading to the following result:
 
Let 

    S(ϕ) ≜(2 sin(ϕπ/2 ) )^-2 - 1-M^-2/6.

Then the indirect DRF of the random walk X given its factor M decimated version Y equals
 

    D_EC(M,R_θ)    = (M) +  M∫_0^1 min{θ, S(ϕ) } dϕ
    
        R_θ   = 1/2 M∫_0^1 max{0, log(S(ϕ) / θ) } dϕ,




We show in the Appendix that the N_M non-zero eigenvalues of the covariance matrix of X^N are given by


    λ_k(M)    = M^2[2sin( (2k-1)M/2N+1π/2) ]^-2 - M^2-1/6,
            k = 0...N_M-1


Substituting (<ref>) into (<ref>) we have

 

    D_X^N(R_θ)    =  1/MM/N∑_k=1^N_Mmin[θ, λ_k] 
    
        R_θ   = 1/MM/2N∑_k=1^N_Mmax[0, log (λ_k/θ)],



where the λ_k's are given by (<ref>). Taking the limit in (<ref>) as N→∞ with kM/N→ϕ∈ (0,1) and θ' = θ/M leads to the integral representation for D_X(R). Finally,  (<ref>) is obtained by adding the MMSE term to D_X(R).




 §.§ Compress-and-Estimate


We now consider the compress-and-estimate scheme. As in EC, we begin from the decomposition in (<ref>). However, instead of using the optimal encoder that attains the DRF of X, we use the encoder f_CE that maps Y^N_M to one of 2^NR possible sequences y^N_M(1),…,y^N_M(2^NR). By linearity of X^N in Y^N_M, we have that the MMSE estimate of X^N from f_EC(Y^N_M) is given by the interpolation (<ref>), hence

    (X^N | Y^N_M) = (X^N | f_CE(Y^N_M) ),

where Y^N_M = g_EC(f_CE( Y^N_M)). Therefore, in order to derive D_CE via (<ref>), it is left to characterize the term (X^N | f_CE(Y^N_M)). 

Note that unlike in EC, this term does not describe a distortion under optimal encoding, since while optimal encoding was performed, it was performed with respect to Y^N_M rather that X^N. Therefore, we characterize (X^N | f_CE(Y^N_M)) by expressing it in terms of the error in encoding Y^N_M with respect to the CE codebook:

    ϵ≜ Y^N_M - Ŷ(f_CE(Y^N_M) ),

This connection is achieved by the following lemma:
 
For any N, M, and encoder f we have:

    (X^N|Y^N_M ) = 2M^2+1/3NM∑_n=1^N_M+1𝔼[ϵ_n^2] 
        + M^2-1/3NM∑_n=1^N_M𝔼[ϵ_n ϵ_n+1]  - 2M^2+3M+1/6NM𝔼[ϵ_N_M^2].


The proof of Lem. <ref> can be found in the Appendix. 



The following upper bound to D_CE(M,R) is a direct consequence of Lem. <ref>:
 
Let f_y describe a sequence of encoders such that

    lim_N→∞( Y^N_M | f_y(Y^N_M) ) = D_Y(M R),

where D_Y(M R) = MD_X(M R) is obtained from (<ref>). Then 

    lim inf_N→∞(X^N | f_y(Y^N_M) ) ≤(M) + MD_X(M R).

In particular 

    D_CE(R) ≤(M) + MD_X(M R).



Since 𝔼[ϵ_n ϵ_n+1] ≤1/2𝔼[ϵ_n^2 + ϵ_n+1^2 ], it follows from (<ref>) that

    (X^N | f(Y^N_M) ≤N+M/N(Y^N_M+1| f_y(Y^N_M) ).

(<ref>) follows since f_y is such that ( Y^N| f_y(Y^N)) → D_Y(R̅) and since R̅ = MR is the number of bits per symbol allotted to f_y to encode Y^N_M. 




Using Lem. <ref> with the encoder  f_CE, we obtain a closed-form expression for D_CE(M,R), as per the following theorem: 
 
For any decimation factor M and bitrate R, the infimum over all acheivable distortions using the CE scheme is given by



    D_CE(M,R_θ)     = (M) + 2M^2+1/3M∫_0^1 min{S(ϕ),θ} dϕ
        + M^2-1/3M∫_0^1 min{S(ϕ),θ}cos(πϕ) dϕ, 
    
        R_θ  =    1/2M∫_0^1 max[0, log(S(ϕ) /θ) ] dϕ,



where S(ϕ) = (2 sin( πϕ/2 ) )^-2, as in (<ref>). 



Only a sketch of the proof is provided here. The full proof can be found in the Appendix. In view of (<ref>), it is enough to show that (X^N|f_CE(Y^N_M) ) converges to the water-filling part in (<ref>). Using Lem. <ref> with f_CE implies that the first term in the RHS of (<ref>) converges to 
2M^2+1/3MD_X(MR), and leads to the first term in (<ref>). In order to evaluate the term 𝔼[ϵ_n ϵ_n+1] in (<ref>), we consider the properties of the encoder f_CE. The joint distribution of the two sequences Y^N_M and Ŷ^N_M, at the input and output of the encoder, respectively, behaves as if both sequences were drawn from the joint P^*_Y^N_M,Ŷ^N_M that attains the DRF of the vector Y^N_M <cit.>. In our case, this distribution is defined by a Gaussian channel P_Ŷ^N_M,Y^N_M. Therefore, by setting ϵ̂≜ Y - Y, we conclude that 

    𝔼[ ϵ_n ϵ_n+1] = 𝔼[ ϵ̂_nϵ̂_n+1]
     
     = ∑_k=1^N_M u_k[n] u_k[n+1],

where u_k's are the eigenvectors of covarience matrix Σ_Y^N_M, given in <cit.>. The behavior of the last term in the limit N→∞ leads to the second term in (<ref>).













§ ANALYSIS AND INTERPRETATIONS


Since the parameter θ obscures the direct dependency of D_EC and D_CE on R, we will consider the conditions under which we can eliminate the parameter θ.  We will then numerically analyze the dual dependency of D_EC and D_CE and M and R.



 §.§ High Rate Characterizations

When the number of bits per decimated symbol MR is large, θ can be eliminated from (<ref>) and (<ref>), leading to single-line expressions for D_EC(M,R) and D_CE(M,R). This leads to the following proposition.
 


    
  (i) For R M ≥ 1,
    
    D_CE(M,R) = (M) +  2M^2+1/3M 2^-2MR



  (ii) For M R ≥log2 [1 + 3/√(3+6/M^2)] ≥ 1,

    
    D_EC(M,R)     =(M)  
          + 1+(2+√(3+6/M^2)) M^2/6 M 2^-2 M R



 

The proof of Prop. <ref> can be found in the Appendix. Note that, as expected, (<ref>) and (<ref>) reduce to D_X(R) for M=1. It follows from Prop. <ref> that

    D_CE(M,R) -    D_EC(M,R)  
       =  1+(2-√(3+6/M^2)) M^2/6 M 2^-2 M R,

whenever M R≥log2 [1 + 3/√(3+6/M^2)].



 §.§ Discussion


 



Figs. <ref> and <ref> show the distortion expressions as functions of the bitrate R and the decimation factor M, respectively. We see that both D_EC(M,R) and D_CE(M,R) are bounded from below by D_X(R) and (M), representing the minimal distortion only due to lossy compression and decimation, respectively. Further, both D_EC(M,R) and D_CE(M,R) approach the bounds in the two extremes of no decimation (M=1) and infinite bitrate (R→∞). That is, for low values of R compared to M, the distortion under both schemes is dominated by the error due to lossy compression, whereas the distortion is dominated by interpolation error when R is large compared to M. 








The bottom of Figs. <ref> and <ref> illustrate the performance gap in using CE compared to EC, given by (<ref>) for sufficiently large MR. This gap is maximal in the transition region between rate-dominant and decimation-dominant distortion. As can be seen in Fig. <ref>, although the performance gap is positive for any M and R, it is relatively small. For example, when M=100, the maximal value of (<ref>), i.e. the performance loss from using CE instead of the optimal EC, is 2.7%, and thus CE may be used as a near approximation to optimal performance when EC is impractical or, due to an ignorance of M at the encoder, impossible.













§ CONCLUSIONS 


We have derived a closed-form expression for the minimal distortion in recovering a Gaussian random walk from a finite-bit representation of its decimated version. 
This expression quantifies the behavior of the minimal distortion subject to decimation and lossy compression. This expression also confirms the following expected behavior: convergence to the standard DRF of the random walk at low coding rates where encoding error dominates; an interpolation error floor at high coding rates where decimation error dominates; and increased degradation with increasing decimation. 
In addition, we considered the distortion in recovering the random walk under a CE scheme. In this scheme, the encoding of the decimated process is done with respect to a random codebook derived from its rate-distortion achieving distribution. That is, a codebook that is designed to attain the DRF of the decimated process, rather than the original (not decimated) random walk. In particular, the encoder in this scheme is not informed of the decimation factor. 

 The comparison between the two distortion expressions  provides the excess distortion as a result of using the sub-optimal CE encoding. In particular, it provides a distortion bound on the price of an unknown decimation factor at the encoder. We show that this price is small and need be considered only for a narrow band of R and M values where neither source of distortion, i.e. neither the bit constraint nor the decimation, have become dominant distortion factors.



§ ACKNOWLEDGMENTS

This research was supported in part by the NSF Center for Science of Information (CSoI) under grant CCF-0939370.








































IEEEtran






§ APPENDIX





 §.§ Eigenvalues of Σ_X^N

Here we sketch our derivation of the eigenvalues for the covariance matrix of the down-sampled and interpolated sequence X, as given in (<ref>) and used in the characterization of the D_EC in (<ref>). We follow the same proof approach as used by Berger for the non-decimated random Gaussian walk in <cit.>.

Let Σ_X^N be the covariance matrix of the interpolated process X^N with eigenvalues λ and eigenvectors f. Under the assumption of unit variance, this gives us

 
 
 
 λf(i)    = ∑_j = 0^i^- - 1 j f(j) + ∑_j = i^-^i^+ - 1  f(j)(M - j/M i^- + j/M i) + i ∑_j = i^+^N-1 f(j) 

 λ[f(i   +2) - 2f(i+1) + f(i)] = 0 

 
 
 

 From this we conclude that the eigenvectors f must be piece-wise linear. However, since the interpolation and downsampling factors are the same, the boundary conditions remain the same as in the uninterpolated Wiener process case. In <cit.>, they were shown as 
 
 f(0) = 0     λ[f(n)-f(n-1)]=f(n)
 

 Thus to satisfy both the piece-wise linearity as well as the boundary conditions, we consider piece-wise linear interpolations of the decimated eigenvectors of the original Wiener process. That is, if we let λ and f be the eigenvalues and eigenvectors of Σ_X, the covariance of the un-decimated sequence X, as derived in <cit.>,

 
    f_k(n) = B ( n^+ - n/M f_k(n^-) + n - n^-/M f_k(n^+) ) 
                f_k(n) = A sin( 2k - 1/2N + 1π n ) 
       f_k(n) = C (n^+-n/Msin[(2k-1/2N+1) π i^-] +n - n^-/Msin[(2k-1/2N+1) π i^+])


 where n^+ = ⌈n/M⌉ M and n^- = ⌊n/M⌋ M, and A,C are normalization constants. Since each element of X is the result of a linear combination of elements of the decimated sequence Y, the dimensionality of X≤ the dimentionality of Y, and thus (<ref>) only holds for k ≤ N_M. For k > N_M, λ_k = 0, and thus we are unconcerned with the corresponding eigenvectors.

 Now to determine the eigenvalues, let p ≜ jM, where j is an integer.

 
 
 
    f(p) = f(p) = A sin( 2k - 1/2N + 1 πp ) 

    λ[f(p+2M) - 2f(p+M) + f(p)] 
    = - C 1/3 sin(τπ(p + M)) [(M^2 - 1) cos(τπM) + 2M^2 + 1] 

            τ≜2k-1/2N+1 

    λ_k = C/A (M^2 - 1) cos(τπM) + 2M^2 + 1/12 M^2 sin^2(τπ/2 M) 

    λ_k = D ( 2cos^2(τπ/2 M) + 1/12 sin^2(τπ/2 M) + 1/6M^2 )

    λ_k = M^2[2sin( (2k-1)M/2N+1π/2 ) ]^-2 - M^2-1/6,

        D, C, A = normalization constants
 
 
 
This proves Eq <ref>.




 §.§ Proof of Lem. <ref>


We here provide the complete proof for (<ref>).  Note that throughout the main paper, all sequences are treated as 1-indexed (that is, the first element is X_1).  For the simplicity of the calculation, the following derivation is done for a 0-indexed sequence (thus the first element is X_0).  However, by simply re-indexing the final result, we achieve (<ref>).



    
    
    (X | Y)    = 1/N ∑_n=0^N-1 𝔼 [X_n - 𝔼 [ X_n | Y] ]^2

       = 1/N ∑_n=0^N_M-1 ∑_m=nM^(n+1)M-1 𝔼 [X - 𝔼 [ X | Y] ]^2

       = 1/N∑_n=0^N_M-1 ∑_m=nM^(n+1)M-1 𝔼 [X - (n+1)M - m/M Y_n - m - nM/M Y_n+1 ]^2 

           Y_n = Y_n - ϵ_n 

       = 1/N∑_n=0^N_M-1 ∑_m=nM^(n+1)M-1 𝔼 [(n+1)M - m/M ϵ_n + m - nM/M ϵ_n+1 ]^2 

       = 1/NM∑_n=0^N_M-1 2M^2+3M+1/6 𝔼[ϵ_n^2] + M^2-1/3 𝔼[ϵ_n ϵ_n+1] + 2M^2-3M+1/6 𝔼[ϵ_n+1^2]

       = 1/NM( ∑_n=0^N_M [ 2M^2+1/3 𝔼[ϵ_n^2] ] + ∑_n=0^N_M-1 [ M^2-1/3 𝔼[ϵ_n ϵ_n+1]] 
           - 2M^2-3M+1/6 𝔼[ϵ_0^2] - 2M^2+3M+1/6 𝔼[ϵ_N_M^2] ) 

                𝔼 [ϵ_0^2] = 0 

       = 2M^2+1/3NM∑_n=0^N_M 𝔼[ϵ_n^2] + M^2-1/3NM ∑_n=0^N_M-1 𝔼[ϵ_n ϵ_n+1] - 2M^2+3M+1/6NM 𝔼[ϵ_N_M^2]
    
    



Re-indexing from 1 rather than 0 yields (<ref>).



 §.§ Convergence of 𝔼[ϵ̂_n ϵ̂_n+1]


In order to evaluate the cross term in (<ref>), first note that

    1/N_M∑_n=1^N_M-1 u_k[n]u_k[n+1]  
        =  1/N_M∑_n=1^N_M-1 A_k^2 sin(2k-1/2N_M+1π/2n ) 
     sin(2k-1/2N_M+1π/2(n+1) ) 
        = 1/N_M∑_n=1^N_M-1 A_k^2 sin(2k-1/2N_M+1π n ) 
     sin(2k-1/2N_M+1π(n+1) ) 
    
     
         = A_k^2/2cos(2k-1/2N_M+1π) + o(1),

where o(1)N→∞⟶ 0, and this last transition is because 

    ∑_n=1^N_M-1cos(2k-1/2N+1π(2n+1) )

is bounded in N_M. Similarly, we have

    1     = ∑_n=1^N_M(u_k[n])^2 = ∑_n=1^N_M A_k^2 sin^2 (2k-1/2N_M+1π n ) 
        = A_k^2 N_M/N_M∑_n=1^N_M(1/2 - 1/2cos( 2 2k-1/2N_M+1π n ) ),

and hence A_k^2 N_M N→∞⟶ 2. As a result

    1/N_M∑_n=1^N_M-1𝔼 [ϵ̂_n ϵ̂_n+1] 
        = 1/N_M∑_n=1^N_M-1∑_k=1^N_M u_k[n]u_k[n+1]min{θ,λ_k }
        = 1/N_M∑_k=1^N_Mmin{θ, λ_k}∑_n=1^N_M-1 u_k[n]u_k[n+1] 
        = o(1) + 1/N_M∑_k=1^N_MN_M A_k^2/2min{θ, λ_k}cos(2k-1/2N_M+1π)

We now take the limit in (<ref>) as N→∞ with k/N_M = kM/N →ϕ∈ [0,1]. In this limit, the spectrum of Σ_Y converges to M S(ϕ), where

    S(ϕ) ≜[ 2 sin(ϕπ/2) ]^-2.

Therefore, the sum in (<ref>) converges to 

    ∫_0^1 min{θ, M S(ϕ) }cos(πϕ ) dϕ = M ∫_0^1 min{θ', S(ϕ) }cos(πϕ ) dϕ,

where θ' = θ /M. 




 §.§ Proof of Prop. <ref>


When θ≤ 1/4, (<ref>) reduces to 

    D_X(R_θ)     = θ
    
        R_θ    =  log[1/√(θ)]

and hence D_X(R) = 2^-2R. Since D_CE(M,R) depends on the same asymptotic eigenvalue density S(ϕ), we conclude from (<ref>) that 

    D_CE(M,R)     = M-M^-1/6 + ( 2M^2+1/3M) 2^-2MR.




For the function D_EC(M,R), the minimum of S(ϕ) is

    1/2 - 1-M^-2/6 = 1 + M^-2/12,

and for θ smaller than this value we have

    D_EC = M-M^-1/6 + M θ
        M R  = 1/2∫_0^1 log[ (2sin(ϕπ/2))^-2 - 1-M^-2/6] dϕ - log(θ)/2, 
        = -1 + log[1+√(1-4 1-M^-2/6)] - log(θ)/2.

Eliminating θ from the last expression, leads to (<ref>)

    D_EC(M,R) = M-M^-1/6 + ( 1+(2+√(3+6/M^2)) M^2/6 M) 2^-2MR,

which holds whenever 

    MR    ≥ -1 + log[1+√(1+4 1-M^-2/6)] - log[1+M^-2/12] 
        = log√(3)M+√(5M^2-2)/√(2+M^2).
 




 §.§ Proof of Thm. <ref> 

In view of (<ref>), it is enough to show that (X^N|f_CE(Y^N_M) ) converges to the water-filling part in (<ref>). Usign Lem. <ref> we have

    2M^2+1/3M^2N+M/N( Y^N_M|f_CE(Y^N_M) )  
    N→∞⟶2M^2+1/3M^2D_Y(MR) = 2M^2+1/3MD_X(MR),

which, using (<ref>) with θ'=θ/M, leads to (<ref>) and to the first term in (<ref>). In order evaluate the term 𝔼[ϵ_n ϵ_n+1] in (<ref>), we consider the properties of the encoder f_CE. 

The joint distribution of two sequence Y^N_M and Ŷ^N_M, at the input and output of the encoder, respectively, behaves as if both sequences were drawn from the joint P^*_Y^N_M,Ŷ^N_M that attains the DRF of the vector Y^N_M <cit.>. In our case, this distribution is defined by

    Y^N_M = Y^N_M + UZ^N_M,

where U is the matrix of eigenvalues in the eigenvalue decomposition 

 
    Σ_Y = U Λ_Y U^H


of Σ_Y, and Z^N_M∼𝒩(0,Λ_θ) where (Λ_θ)_n,n = min{(Λ_Y)_n,n, θ}. The rows of U and entries of Σ_Y are given by <cit.>:


    λ_k =   σ_Y^2 [2 sin (2k-1/2N_M+1π/2) ]^-2
    
        u_k[n]    = A_k sin(2k-1/2N_M+1π n ),


where k = 1, ..., N_M, σ_Y^2 = M, and A_k is a normalization constant. Let ϵ̂≜ Y - Y. From the above, we conclude 

    𝔼[ ϵ_n ϵ_n+1] = 𝔼[ ϵ̂ϵ̂_n+1]
     
     = ∑_k=1^N_M u_k[n] u_k[n+1].

We showed in the Appendix C that 

    1/N∑_n=1^N_M-1𝔼[ ϵ̂_n ϵ̂_n+1] N→∞⟶∫_0^1 min{θ', S(ϕ) }cos(πϕ) dϕ,

and 𝔼[ϵ_N_M^2]/N → 0. This expression leads to the second term in (<ref>). 


