Cheung–Marks theorem

In information theory, the Cheung–Marks theorem^[1], named after K. F. Cheung and Robert J. Marks II, specifies conditions^[2] where restoration of a signal by the sampling theorem can become ill-posed. It offers conditions whereby "reconstruction error with unbounded variance [results] when a bounded variance noise is added to the samples."^[3]

Background

In the sampling theorem, the uncertainty of the interpolation as measured by noise variance is the same as the uncertainty of the sample data when the noise is i.i.d.^[4] In his classic 1948 paper founding information theory, Claude Shannon offered the following generalization of the sampling theorem:^[5]

The 2TW numbers used to specify the function need not be the equally spaced samples used above. For example, the samples can be unevenly spaced, although, if there is considerable bunching, the samples must be known very accurately to give a good reconstruction of the function. The reconstruction process is also more involved with unequal spacing. One can further show that the value of the function and its derivative at every other sample point are sufficient. The value and first and second derivatives at every third sample point give a still different set of parameters which uniquely determine the function. Generally speaking, any set of 2TW independent numbers associated with the function can be used to describe it.

Although true in the absence of noise, many of the expansions proposed by Shannon become ill-posed. An arbitrarily small amount of noise on the data renders restoration unstable. Such sampling expansions are not useful in practice since sampling noise, such as quantization noise, rules out stable interpolation and therefore any practical use.

Example

Shannon's suggestion of simultaneous sampling of the signal and its derivative at half the Nyquist rate results in well behaved interpolation.^[6] The Cheung–Marks theorem shows counter-intuitively that interlacing signal and derivative samples makes the restoration problem ill-posed.^[1][2]

The theorem also shows sensitivity increases with derivative order.^[7]

The theorem

Generally, the Cheung–Marks theorem shows the sampling theorem becomes ill-posed when the area (integral) of the squared magnitude of the interpolation function over all time is not finite.^[1][2] "While the generalized sampling concept is relatively straightforward, the reconstruction is not always feasible because of potential instabilities."^[8]

References

1. ^ ^{a b c} J.L. Brown and S.D.Cabrera, "On well-posedness of the Papoulis generalized sampling expansion," IEEE Transactions on Circuits and Systems, May 1991 Volume: 38 , Issue 5, pp. 554–556
2. ^ ^{a b c} K.F. Cheung and R. J. Marks II, "Ill-posed sampling theorems", IEEE Transactions on Circuits and Systems, vol. CAS-32, pp.829–835 (1985).
3. ^ D. Seidner, "Vector sampling expansion," IEEE Transactions on Signal Processing. v. 48. no. 5. 2000. p. 1401–1416.
4. ^ R.C. Bracewell, The Fourier Transform and Its Applications, McGraw Hill (1968)
5. ^ Claude E. Shannon, "Communication in the presence of noise", Proc. Institute of Radio Engineers, vol. 37, no.1, pp. 10–21, Jan. 1949. Reprint as classic paper in: Proc. IEEE, Vol. 86, No. 2, (Feb 1998)
6. ^ Athanasios Papoulis, Signal Analysis, McGraw-Hill Companies (May 1977)
7. ^ Unser, M.; Zerubia, J. (1997). "Generalized sampling: stability and performance analysis". Signal Processing, IEEE Transactions 45 (12): 2941–2950. http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=650255&isnumber=14183. 
8. ^ M. Unser, "Sampling – 50 years after Shannon," Proceedings of the IEEE, Vol 88, Issue 4, pp. 569–587, April 2000