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
editIn 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
editShannon'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
editGenerally, 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
edit- ^ a b c Brown, J.L.; Cabrera, S.D. (May 1991). "On well-posedness of the Papoulis generalized sampling expansion". IEEE Transactions on Circuits and Systems. 38 (5): 554–6. doi:10.1109/31.76494.
- ^ a b c Cheung, K.F.; Marks II, R.J. (1985). "Ill-posed sampling theorems". IEEE Transactions on Circuits and Systems. 32 (5): 481–4. doi:10.1109/TCS.1985.1085735.
- ^ Seidner, D. (2000). "Vector sampling expansion". IEEE Transactions on Signal Processing. 48 (5): 1401–16. Bibcode:2000ITSP...48.1401S. doi:10.1109/78.839986.
- ^ Bracewell, R.N. (2000). The Fourier Transform and Its Applications (3rd ed.). McGraw Hill. ISBN 978-0-07-116043-8.
- ^ Shannon, Claude E. (January 1949). "Communication in the presence of noise" (PDF). Proc. Institute of Radio Engineers. 37 (1): 10–21. doi:10.1109/JRPROC.1949.232969. S2CID 52873253. Also doi:10.1109/JPROC.1998.65949
- ^ Papoulis, Athanasios (1977). Signal Analysis. McGraw-Hill. ISBN 978-0-07-048460-3. OCLC 489738322.
- ^ Unser, M.; Zerubia, J. (1997). "Generalized sampling: stability and performance analysis". IEEE Transactions on Signal Processing. 45 (12): 2941–50. Bibcode:1997ITSP...45.2941U. doi:10.1109/78.650255.
- ^ Unser, M. (April 2000). "Sampling – 50 years after Shannon" (PDF). Proceedings of the IEEE. 88 (4): 569–587. doi:10.1109/5.843002. S2CID 11657280.