Low-density linear IED schemes for lossless source coding with decoder only side information

In this paper we investigate the performance of linear interactive encoding and decoding (IED) for lossless source coding with decoder only side information. Assume that the source alphabet chi is a finite field and that the side information alphabet is finite. It is shown that there exist universal linear IED schemes which are asymptotically optimal for any stationary, ergodic source-side information pair. Our analysis of low-density IED schemes further reveals that as long as isin_np_n ^* = Omega(log n/n), where isin_n and p_n ^* are real numbers, one can always construct a sequence of universal linear IED schemes {I_n} such that the average density of the parity check matrices associated with I_n is concentrated around (|chi|-1)p_n ^*, and the resulting symbol error probability is upper bounded by isin_n + o(isin_n).