350 rub
Journal Achievements of Modern Radioelectronics №6 for 2015 г.
Article in number:
Reconstruction of non-uniform sampled discrete-time signals with unknown sampling locations
Keywords: non-uniform sampling reconstruction interpolation unknown locations irregular sampling
Authors:
S.V. Porshnev - Dr.Sc. (Eng.), Professor, Head of Department «Electronics Information Systems», Ural Federal University named after the first President of Russia B.N.Yeltsin, Ekaterinburg. E-mail: sergey_porshnev@mail.ru D.V. Kusaykin - Post-graduate Student, Ural Technical Institute of Communication and Computer Science, Ekaterinburg. E-mail: kusaykin@mail.ru
Abstract:
Irregularly sampled signals are employed in various areas of radio engineering and telecommunications, e.g. in stochastic and quasistochastic coding; in synchronous time division multiplexing; asynchronous transfer mode, in data transmission multiple access; in mobile telecommunication system by the consecutive, regular cell site-s search of the called zones where the object happens to be randomly located resulting in discrete-time irregular sampling; in satellite communication systems (especially in communication with airplanes) being time-sensitive due to constant communication delay (caused by mutual movements of destination and retranslator) and jump ones (caused by retranslator settings), etc. The paper is concerned with analyzing the known irregular sampling models, the results enabled to find enlarged irregular sampling class methods and classify them. Basing on the proposed classification we have drawn a conclusion that the problem of reconstruction of discrete-time signals with non-uniform sampling and discrete-time signals with irregular sampling falls into two groups: 1) discrete-time signals with non-uniform sampling with known sampling locations of non-uniform sampling; 2) discrete-time signals of the set location with unknown sampling locations. The first problem is similar to a well-known table-set function interpolation problem, meanwhile the development of the second problem solution methods has only recently started, and that is why their consideration and classification is bearing a practical aspect. Having implemented the analysis of the known methods of the reconstruction of irregularly sampled discrete-time bandlimited signals with unknown sampling locations we draw a conclusion that most of their reconstruction algorithms are treated as a combinatorial optimization problem to find all unknown sampling signal locations. However, neither of the works studied proposes any recommendations to select initial approximation parameters search areas, meanwhile, to guarantee a finding of a global rather than a local optimized function maximum seems to be of a problem. In this respect the following statements are certain to present practical value: firstly, an application of the considered algorithms to reconstruct irregularly sampled discrete-time bandlimited signals with unknown sampling locations, secondly, a development of the simpler «quasioptimal» methods to approximate the signals considering their local features. The paper is organized as follows. In Section 1 discussed are examples of technical systems employing irregular sampling; in Section 2 kinds of irregular sampling and their features are described; in Section 3 we provide classification of the irregular sampling kinds; in Section 4 considered are algorithms to reconstruct irregularly sampled discrete-time bandlimited signals with unknown sampling locations.
Pages: 3-35
References

 

  1. Landau H. Necessary density conditions for sampling and interpolation of certain entire functions / Acta Math. 117. 1967. P. 37-52.
  2. Unser M.Sampling - 50 years after Shannon / Proceedings of the IEEE. 2000. V. 88. № 4. P. 569-587.
  3. Unser M.Sampling: 60 Years After Shannon / Plenary talk, Sixteenth International Conference on Digital Signal Processing (DSP2009). Santorini. Greece. July 2009. P. 42.
  4. Dzherri A. Dzh. Teorema otschetov SHennona, ee razlichnye obobshhenija i prilozhenija. Obzor // TIIEHR. 1977. T. 65. № 11. S. 53-89.
  5. Senay S.Signal reconstruction from Nonuniform samples using prolate spheroidal wave functions: theory and application / Doctoral Dissertation. University of Pittsburgh. 2011.
  6. Feichtinger H.G., Grochenig K., Strohmer T. Efficient numerical methods in non-uniform sampling theory // Numerische Mathematik. 1995. №69. P. 423-440.
  7. Tuncer T.E., Serdaroglu B. Block-based methods for the reconstruction of finite-length signals from nonuniform samples // IEEE Trans. Signal Process. 2007. V. 5. P. 530-541.
  8. Marvasti F. Nonuniform Sampling: Theory and Practice. Information Technology: Transmission, Processing and Storage. 2000.
  9. Efimov V.M., Kasperovich A.N., Reznik A.L. Vosstanovlenie signala s konechnym chislom stepenejj svobody pri ego neravnomernojj diskretizacii // Avtometrija. 2000. № 3. S. 26-31.
  10. Margolis E., Eldar Y.C. Nonuniform Sampling of Periodic Bandlimited Signals // IEEE Transactionson signal Processing. 2008.V. 56. № 7. P. 2728-2745.
  11. Bondarenko JU.V., Kasperovich A.N. Nelinejjnoe vosstanovlenie signalov po neravnomernym otschetam // Avtometrija. 1999. № 4. C. 61-70.
  12. Cenker C., Feichtinger H.G. Martin Herrmann. Iterative algorithms in irregular sampling a first comparison of methods // 10-th IEEE IPCCC. 1991. R. 483-489.
  13. Strohmer T. Efficient methods for digital signal and image reconstruction from nonuniform samples / PhD. Thesis, Univ. of Vienna, 1993.
  14. Selva J. Functionally weighted Lagrange interpolation of band-limited signals from nonuniform samples. / IEEE Transactions on Signal Processing. 2009. V. 57. № 1. P. 168-181.
  15. Grochenig K., Schwab H. Fast Local Reconstruction Methods for Nonuniform Sampling in Shift Invariant Spaces // SIAM Journal on Matrix Analysis and Applications. 2003. V. 24. № 4. P.899-913.
  16. Qu. L., Routh P.S., Anno P.D. Wavelet Reconstruction of Nonuniformly Sampled Signals // IEEE signal processing letters. 2009. V. 16. № 2. P. 73-76.
  17. Ford C., Etter D.M. Wavelet Basis Reconstruction of Nonuniformly Sampled Data //IEEE Transactions on circuits and systems-II: analog and digital signal processing. 1998. V. 45. № 8. P. 1165-1168.
  18. Ferreira P. The stability of a procedure for the recovery of lost samples in band-limited signals / Signal Processing.1994. V. 40. № 2-3. P. 195-205.
  19. Porshnev S.V., Kusajjkin D.V. Issledovanie tochnosti metodov vosstanovlenija diskretnykh signalov, zadannykh na neravnomernojj vremennojj setke // V mire nauchnykh otkrytijj. 2013. T. 46. № 10. S. 261-279.
  20. Gorelov G.V. Nereguljarnaja diskretizacija signalov. M.: Radio i svjaz. 1982.
  21. Bilinskis I. Digital Alias-free Signal Processing. London: Wiley. 2007. P. 430.
  22. Qu D., Ma B., Zhou J. Optimal Weighted Periodic Nonuniform Sampling Sequences for Digital Alias-free Signal Processing // Signal Processing (ICSP). 2010. IEEE 10-th International Conference. 2010. P. 147-150.
  23. Sommen P., Janse K. On the Relationship Between Uniform and Recurrent Nonuniform Discrete-Time Sampling Schemes // IEEE Transactions on signal Processing. 2008. V. 56. № 10. P. 5147-5156.
  24. Divi V., Wornell G. Signal recovery in time-interleaved analog-to-digital converters // Proc. IEEE Int. Conf. Acoust. Speech Signal Process. 2004. P. 593-596.
  25. Hofner T.C. Boost your sampling rate with time-interleaved data converters, Sensors Mag. 2001. V. 18. № 2.
  26. Huang S., Levy B.C. Blind calibration of timing offsets for four channel time-interleaved ADCs // IEEE Trans. Circuits Syst. I, 2007. V. 54. № 4. P. 863-876.
  27. McNeill J.A., David C., Coln M., Croughwell R. Split ADC calibration for all-digital correction of time-interleaved ADC errors // IEEE Trans. Circuits Syst. II. 2009. V. 56. № 5. P. 344-348.
  28. Lu Y.M., Vetterli M. Multichannel sampling with unknown gains and offsets: A fast reconstruction algorithm // Proc. Allerton Conference on Communication, Control and Computing. Monticello. IL. 2010.
  29. Hormati A., Roy O., Lu Y.M., Vetterli M.Distributed sampling of correlated signals linked by sparse filtering: Theory and applications // IEEE Trans. Signal Process. 2010. V. 58. № 3. P. 1095-1109.
  30. Park S.C., Park M.K., Kang M.G. Super-resolution image reconstruction: A technical overview // IEEE Signal Process. Mag. 2003.V. 20. № 3. P. 21-36.
  31. Vandewalle P., Susstrunk S., Vetterli M. A frequency domain approach to registration of aliased images with application to super-resolution // EURASIP J. Appl. Signal Process. Special Issue on Super-Resolution Imaging 2006. 2006. P. 1-14.
  32. Patwari N., Ash J.N., Kyperountas S., Moses R.L., Correal N.S. Location the nodes: Cooperative localization in wireless sensor networks // IEEE Signal Processing Magazine, 2005. V. 22. № 4. P. 54-69.
  33. Ganesan D., Ratnasamy S., Wang H., Estrin D. Coping with irregular spatio-temporal sampling in sensor networks // ACM SIGCOMM Computer Communication Review. January 2004. V. 34. № 1. P. 125-130.
  34. The Autonomous Ocean Sampling Network (AOSN) project [EHlektronnyjj resurs]. Rezhim dostupa: http://www.mbari.org/aosn/.
  35. Bokser V., Oberg C., Sukhatme G.S., Requicha A.A. A small submarine robot for experiments in underwater sensor networks // IFAC -International Federation of Automatic Control Symposium on Intelligent Autonomous Vehicles. 2004.
  36. Cayirci E., Tezcan H., Dogan Y., Coskun V. Wireless sensor networks for underwater surveillance systems // Ad Hoc Networks. 2006. V. 4. № 4. P. 431-446.
  37. Majumdar S.J., Aberson S.D., Bishop C.H., Buizza R., Peng M.S., Reynolds C.A. A comparison of adaptive observing guidance for Atlantic tropical cyclones // 27-th Conference on Hurricanes and Tropical Meteorology. Apr. 2006.V. 134. P. 2354-2372.
  38. Kahn J.M., Katz R.H., PisterK.S.J.Next century challenges: Mobile networking for «smart dust» // ACM International Conference on Mobile Computing and Networking (MOBICOM). 1999. P. 271-278.
  39. Tian J. Reconstruction of irregularly sampled interferograms in imaging Fourier transform spectrometry. / Thesis (Ph. D.) ? School of Electrical and Computer Engineering. Georgia Institute of Technology. 2004.
  40. Godsill S.J. The restoration of degraded audio signals. PhD thesis. Dept. of Engineering. University of Cambridge. 1993.
  41. Golanski R., Kolodziej J. Adaptive nonuniform sampling delta modulation: practical design studies // WSEAS Transactions on Circuits and Systems. 2010. V. 9. № 10. P. 617-626.
  42. Zolghadrasli A. Adaptive Non-Uniform Rate Sampling and Application in Data Compression / International Journal of Information Science and Management (IJISM). 2005. V. 3. № 1. P. 47-56.
  43. Christini D.J., Bennett F.H., Lutchen K.R., Ahmed H.M. Application of linear and nonlinear time series analysis modeling to heart rate dynamics analysis // IEEE Trans. Biomedical Eng. 1995. V. 42. P. 411-415.
  44. Laguna P., Moody G.B., Mark R.G. Power spectral density of unevenly sampled heart rate data // Proc. IEEE-EMBC - 95. 1995. P. 157-158.
  45. Sauer T. Reconstruction of dynamical systems from interspike intervals / Phys. Rev. Lett. 1994. V. 72. P. 3811-3814.
  46. Baevskijj R.M., Ivanov G.G., CHirejjkin L.V. Analiz variabelnosti serdechnogo ritma pri ispolzovanii razlichnykh ehlektrokardiograficheskikh sistem / Vestnik aritmologii. 2001. № 24. S. 67-95.
  47. Banning R., Koning W.L. Spectral Analysis of Laser Doppler Anemometry Velocity Measurements in Turbulent Flows. In Sampling Theory and Applications // Proc. Workshop SAMPTA\'97. Aveiro. Portugal. June 1997. P. 121-126.
  48. Shapiro H.S., Silverman R.A. Alias free sampling of random noise // Journal Society for Industrial and Applied Mathematics. 1960. V. 8. № 2. P. 225-248.
  49. Bilinskijj I.JA., Mikelson A.K. Stokhasticheskaja cifrovaja obrabotka nepreryvnykh signalov. Riga: Zinatne. 1983.
  50. Wojtiuk J.J. Randomized Sampling for Radio Design. PhD Thesis. University of South Australia. School of Electrical and Information Engineering. 2000.
  51. Sun Y., Signell S. Effects of noise and jitter on algorithms for bandpass sampling in radio receivers // In Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS). 2004. V. 1. P. 761-764.
  52. Aldroubi A., Leonetti C. Non-Uniform Sampling and Reconstruction from Sampling Sets with Unknown Jitter // Sampling Theory in Signal & Image Processing . 2008. V. 7. № 2. P. 187-195.
  53. Kumar A. Bandlimited Signal Reconstruction From the Distribution of Unknown Sampling Locations // Proc. of the Sampling Theory and Applications (SampTA) workshop. July 2013. CoRR abs/1303.1285.
  54. Cui-Ping Li, Bing-zhao Li, Tian-Zhou Xu Approximating bandlimited signals associated with the LCT domain from nonuniform samples at unknown locations // Signal Processing. 2012. V. 92. № 7. P. 1658-1664.
  55. Browning J. A method of finding unknown continuous-time nonuniform sample locations of band-limited functions / Advanced Signal Processing Algorithms, Architectures and Implementations XIV. 2004. V. 5559. P. 289-296.
  56. Browning J. Approximating Signals From Nonuniform Continuous Time Samples at Unknown Locations // IEEE Transactions on Signal Processing. 2007. V. 55. № 4. P. 1549-1554.
  57. Sbaiz L., Vandewalle P., Vetterli M. Groebner Basis Methods for Multichannel Sampling with Unknown Offsets // Applied and Computational Harmonic Analysis. 2008. V. 25. № 3. P. 277-294.
  58. Marziliano P., Vetterli M. Irregular sampling with unknown locations // IEEE International Conference on Acoustics, Speech, and Signal Processing. 1999. V. 3. P. 1657-1660.
  59. Marziliano P., Vetterli M. Reconstruction of irregularly sampled discrete-time bandlimited signals with unknown sampling locations // IEEE Transactions on Signal Processing. 2000. V. 48. № 12. P. 3462-3471.
  60. Marziliano P. Sampling Innovations. PhD. Thesis. Swiss Federal Institute of Technology Lausanne, Switzerland. 2001.
  61. Nordio A.,  Chiasserini C., Viterbo E. Performance of Linear Field Reconstruction Techniques With Noise and Uncertain Sensor Locations // IEEE Transactions on signal Processing. 2008. V. 56. № 8. P. 3535-3547.
  62. Nordio A., Chiasserini C., Viterbo E. Signal Reconstruction Errors in Jittered Sampling // IEEE Transactions on signal Processing. 2009. V. 57. № 12. P. 4711-4718.
  63. Nordio A., Chiasserini C., Viterbo E. Linear Signal Reconstruction  from Jittered Sampling // Author manuscript, published in \"SAMPTA\'09. Marseille. France. 2009.
  64. Ferreira P.J.S.G., Vieira J.M.N. Detection and Correction of Missing Samples // Proceedings of the 1997 Workshop on Sampling Theory and Applications. Aveiro, Portugal. 1997. P. 169-174.
  65. Ferreira P.J.S.G., Vieira J.M.N. Locating and correcting errors in images // International Conference on Image Processing. 1997. V. 1. P. 691-694.
  66. Vandewalle P., Sbaiz L., Vandewalle J., Vetterli M.Aliasing is Good for You: Joint Registration and Reconstruction for Super-Resolution. Technical Report. 2006.
  67. Vandewalle P., Sbaiz L., Vandewalle J., Vetterli M.Super-Resolution from Unregistered and Totally Aliased Signals Using Subspace Methods // IEEE Transactions on Signal Processing. 2007. V. 55. № 7. Part 2. P. 3687-3703.
  68. Eng F. Nonuniform sampling in statistical signal processing. PhD Thesis. Department of Electrical Engineering. Linkoping University. Linkoping. Sweden. 2007.
  69. Beutler F.J., Leneman A.Z. The theory of Stationary Points Processes // Acta Math. 1966. V. 116. P. 159197.
  70. Beutler F.J., Leneman A.Z. Random Sampling of Random Processes: Stationary Points Processes // Information and Control. 1966. V. 9. P. 325344.
  71. Bilinskis I., Mikelson A. Randomized Signal Processing. Cambridge: Prentice Hall. 1992. P. 665.
  72. Serdaroglu B. Signal reconstruction from nonuniform samples. Msc Thesis. 2005. P. 102.
  73. Ljung L. System Identification: Theory for the User. Prentice Hall, 2 ed. 1999.
  74. Marques M., Neves R., Marques J. S., Sanches J. The papoulis-gerchberg algorithm with unknown signal bandwidth // Proceeding ICIAR\'06 Proceedings of the Third international conference on Image Analysis and Recognition. 2006. V. 4141. P. 436-445.
  75. Ferreira P.J.S.G. Interpolation and the Discrete Papoulis-Gerchberg Algorithm // IEEE Transactions on Signal Processing. 1994. V. 42. № 10. P. 2596-2606.
  76. Oliveira P. Interpolation of signals with missing data using PCA // IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP - 06). May 2006. V. 3. P. 828-831.
  77. Karthik M., Prabhu K.M.M. On the Eigenvalues of Matrices for the Reconstruction of Missing Uniform Samples //IEEE Transactions on signal Processing. 2010. V. 58. № 5. P. 2896-2900.
  78. Yen. J.L. On Nonuniform sampling of bandwidth-limited signals // IRE Transactions on Circuit Theory. 1956. V. CT-3. P. 251-259.
  79. Marks R.J. Introduction to Shannon Sampling and Interpolation Theory. Springer Texts in Electrical Engineering. Springer-Verlag. New York. 1991.
  80. Singh M., Lu C., Basu A., Mandal M. Choice of low resolution sample sets for efficient super-resolution signal reconstruction // Journal of Visual Communication and Image Representation. 2012. V. 23. № 1. P. 194-207.
  81. Qu D., Tarczynski A. Weighted PNS sequences for digital alias-free processing signals // Proceedings of the 10th WSEAS International Conference on SYSTEMS. Vouliagmeni. Athens. Greece. July 2006. P. 1-6.
  82. KHurgin JA.I., JAkovlev V.P. Finitnye funkcii v fizike i tekhnike. M.: Nauka. 1971.
  83. Scoular S.C., Fitzgerald W.J. Periodic nonuniform sampling of multiband signals // Signal Processing. 1992. V. 28. № 2. P. 195‑200.
  84. Strohmer T., Tanner J. Fast Reconstruction Methods for Bandlimited Functions from Periodic Nonuniform Sampling // SIAM J. Numerical Analysis. 2006. V. 44. №3. P. 1073-1094.
  85. Amini A., Marvasti F. Reconstruction of multiband signals from non-invertible uniform and periodic Nonuniform samples using an iterative method // SAMPTA. 2007.
  86. Prendergast R.S., Levy B.C., Hurst P.J. Reconstruction of bandlimited periodic nonuniformly sampled signals through multirate filter banks // IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications. 2004. V. 51. P. 1612?1622.
  87. Venkataramani R., Bresler Y. Sampling theorems for uniform and periodic nonuniform MIMO sampling of multiband signals // Signal Processing, IEEE Transactions. 2003. V. 51. № 12. P. 3152-3163.
  88. Margolis E. Reconstruction of periodic bandlimited signals from nonuniform samples. Research Thesis, M.S. Israel Institute of Technology. 2004.
  89. Feng P., Bresler Y. Spectrum-blind minimum-rate sampling and reconstruction of multiband signals // 1996 IEEE International Conference on Acoustics, Speech, and Signal Processing. 1996. V. 3. P. 1688-1691.
  90. Mishali M., Eldar Y.C. Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals // IEEE Transactions on Signal Processing. 2009. V. 57. № 3. P. 993-1009.
  91. Venkataramani R., Bresler Y. Perfect reconstruction formulas and bounds on aliasing error in sub-Nyquist Nonuniform sampling of multiband signals // IEEE Trans. Info. Theory. 2000. V. 46. № 6. P. 2173-2183.
  92. Ariananda D.D., Leus G., Zhi Tian. Multi-coset sampling for power spectrum blind sensing // 17-th International Conference on Digital Signal Processing (DSP). 2011. P. 1-8.
  93. Lexa M., Davies M., Thompson J. Multi-coset Sampling and Recovery of Sparse Multiband Signals // University of Edinburgh Institute of Digital Communications Technical Report. 2011.
  94. Bresler Y., Ping Feng. Spectrum-blind minimum-rate sampling and reconstruction of 2-D multiband signals //roc. 3rd  IEEE Int. Conf. on Image Processing, ICIP\'96. 1996. V. 1. P. 701-704.
  95. Rashidi M. Non-uniform sampling and reconstruction of multi-band signals and its application in wideband spectrum sensing of cognitive radio / ArXive-prints. 2010.
  96. Feizi S., Angelopoulos G., Goyal V., Medard M.Energy-Efficient Time-Stampless Adaptive Nonuniform Sampling // in Sensors, 2011 IEEE. 2011. P. 912-915.
  97. Petkovski M., Bogdanova S., Bogdanov M. A Simple Adaptive Sampling Algorithm // XIV Telecommunications Forum - TELFOR 2006. Belgrade. Serbia. 2006. P. 329-332.
  98. 98.Golanski R., Kolodziej J.Nonuniform sampling delta modulation: decoding problems // WSEAS Transactions on Circuits and Systems. 2008. V.7. № 2. P. 85-92.
  99. Feizi S., Goyal V.K., Medard M. Time-Stampless Adaptive Nonuniform Sampling for Stochastic Signals // IEEE Transactions on Signal Processing. 2012.V. 60. №10. P. 5440-5450.
  100. Prokhorov S.A. Prikladnojj analiz neehkvidistantnykh vremennykh rjadov. Samara: Samar. gos. aehrokosmicheskogo un-ta. 2001.
  101. Berenguer C. Estimation frequentielle et filtrage de signaux non uniformement echantillonnes: Application a I-estimation radar Doppler non ambigue. PhD thesis. University of Nice-Sophia Antipolis. France. 1994.
  102. Legg J.A. Synthetic aperture radar using non-uniform sampling. PhD thesis. University of Adelaide. 1997.
  103. Artjukhina N.K., Klimovich T.V., Kotov M.N. Matematicheskoe modelirovanie Fure ? videospektrometra // Pribory i metody izmerenijj: nauchno-tekhnicheskijj zhurnal. Minsk: Belorusskijj nacionalnyjj tekhnicheskijj universitet. 2012. №1(4). S. 24-29.
  104. De Juan A., Maeder M., Martınez M., Tauler R. Combining hard- and soft-modelling to solve kinetic problems // Chemom. Intell. Lab. Syst. 2000. V. 54. № 2. P. 123-141.
  105. Arzhancev I.V. Bazisy Grjobnera i sistemy algebraicheskikh uravnenijj. M.: MCNMO. 2003.
  106. Matjunin V.A. Algoritmy vychislenija bazisov Grjobnera i involjutivnykh bazisov. Diss. k.f.-m.n. M.: MGU im. M.V. Lomonosova. 2004.
  107. Tao R., B.-Z. Li, Yue Wang On sampling of band-limited signals associated with the linear canonical transform // IEEE Transactions on Signal Processing. 2008. V. 56. № 11. P. 5454-5464.
  108. Moshinsky M., Quesne C. Linear canonical transformations and their unitary representations // Journal of Mathematical Physics. 1971. V.12. № 8. P. 1772-1783.