本論文有兩個主要部份：第二部份和第三部份。在第二部份我們介紹了Ramanujan sum以及它在信號處理的一些應用。在第三部份我們介紹一些關於Pade展開式及Prony分析的研究和應用，並提出一套新的方法來做阻尼振蕩的諧波分析。

Ramanujan sum是一個數論領域中的算術函數，近年來才開始被應用到信號處理中。在這些應用之中，最主要的是Ramanujan傅利葉轉換，它利用Ramanujan sum獨特的週期特性，產生一個類似傅利葉轉換的頻率轉換，而這個工具可以成功分析出許多傅利葉轉換無法分析的整數頻率成份。

在本論文的第二部份，我們主要在探討這個數學轉換的物理意義。從前人的相關研究中，我們觀察到幾個Ramanujan傅利葉轉換的優點和缺點，從這些觀點出發，我們認為Ramanujan傅利葉轉換有需要修正的地方，因而提出純粹整數週期函數的概念，並加上了時間平移，定義了一種新的RS圖。純粹整數週期函數可以說是頻率成份最單純的整數週期離散訊號，而我們又用數學證明出，RS圖可以將一個普通的週期訊號之各個純粹整數週期函數成份，呈現在其各個欄位上，也就是說，RS圖等同於純粹整數週期函數成份分解的數學運算。以這個RS圖的成份分解的觀點出發，我們成功解釋了Ramanujan傅利葉轉換的物理意義，並修正了其中的缺點。

在本論文的第三部份，我們從Z轉換的Pade展開式與Prony分析之間的等價性質出發，提出一種利用Pade展開式來改進Prony分析的演算法。由Pade展開式，我們可以分析一個離散訊號的極點和零點，而根據上面所提到的等價性質，那些極點就是Prony分析所得到的振蕩基底。在極點零點圖中，大部份極點和零點都會成雙成對出現，但我們知道主要的振蕩基底之極點不會和零點成對出現，所以我們引用了一篇文章的想法，將成對的極點和零點從複數平面上移除，再利用所剩的極點，用原有的Prony分析方式，把訊點重建出來。我們設計了幾個判定成對極點和零點的方法，也進行了許多實驗，結果顯示我們的方法比Prony分析更能對抗雜訊。

This thesis contains two main parts: Part I and Part II. In Part I we give a summary of an arithmetic function, Ramanujan sum, and its applications in signal processing. In Part II we introduce a novel method for harmonic analysis of damped oscillators.

Ramanujan sum is an arithmetic function, which is recently applied to signal processing. Among its applications, the most important one is the Ramanujan Fourier transform, which uses the unique periodic property of Ramanujan sum to create a Fourier-transform-like frequency transform. This transform can successfully extract some integer periodic components which Fourier transform cannot extract from the signals.

In Part I, we mainly discuss about the physical meaning of this mathematical transform. According to previous works, we observed some advantages and disadvantages of Ramanujan Fourier transform. Based on these points, we conclude that there is something to improve on Ramanujan Fourier transform. Then, we introduce the concept of intrinsic integer-periodic functions. We also define a new RS map by considering time shift in the Ramanujan Fourier transform. The intrinsic integer-periodic functions can be regarded to be pure in periodic component, and we prove in mathematics that RS map presents the intrinsic integer-periodic components of a general signal on the column of the map. That is to say, RS map is equivalent to the intrinsic integer-periodic function decomposition, and with this decomposition by RS map, we can explain the physical meaning of Ramanujan Fourier transform.

In Part II, we start with the equivalence between Pade approximation of Z-transform and Prony analysis and end up to propose a new algorithm to improve Prony analysis. By Pade approximation, we can analysis the poles and zeros of a discrete signal, and by the equivalent property mentioned above, those poles analyzed are the bases obtained by Prony analysis. In the pole-zero plot, most poles appear together with zeros, but we know that for the main bases of oscillators, their poles do not come up with zeros. Thus, we based on the idea in a previous work that we can remove pole-zero pairs from the complex plane so that we can use Prony analysis with the remaining poles to recover the original signal. We design several methods to recognition paired poles and zeros and do many experiments. The results show that our method work better than Prony analysis in noisy environment.

誌謝 i
中文摘要 iii
ABSTRACT v
I Introduction 1
Chapter 1 Introduction 3
1.1 Introduction 3
1.2 Notation and Convention 6
1.2.1 Notation 6
1.2.2 Convention 7
Chapter 2 Background of Number Theory 11
2.1 Roots of Unity 12
2.2 Chinese Remainder Theorem 13
2.3 Arithmetic Function 15
2.3.1 Arithmetic Functions 15
2.3.2 Additive and Multiplicative Properties 17
2.3.3 Euler Totient Function 20
2.4 Dirichlet Convolution 22
2.4.1 Dirichlet Convolution 23
2.4.2 M&;#1255;bius Inversion 26
2.5 Generating Function 28
II The Values and Applications of Ramanujan Sum in Signal Processing 33
Chapter 3 The Values and Applications of Ramanujan Sum in Signal Processing 35
3.1 The Ramanujan Sum 36
3.2 The Ramanujan Fourier Transform 47
3.2.1 Definition 47
3.2.2 Related Works 47
3.3 Discussion 52
3.4 Summary 54
Chapter 4 The Intrinsic Integer-Periodic Functions 57
4.1 Motivation 58
4.1.1 Periodicity 58
4.1.2 Intrinsic Integer Periods 62
4.2 The IIPFs 65
4.2.1 Definition 65
4.2.2 Properties 66
4.3 IIPF Decomposition 73
4.3.1 Existence and Uniqueness 73
4.3.2 Properties of IIPF Decomposition 77
4.3.3 Experimental Results 84
4.4 Summary 87
Chapter 5 The RS Map 89
5.1 Motivation 90
5.1.1 The First Definition 90
5.1.2 The Second Definition 92
5.2 The Relationship Between RS Map and IIPFs 95
5.3 Proof of Theorems 97
5.3.1 Proof of Main Theorem, Part 1 97
5.3.2 Proof of Main Theorem, Part 2 98
5.4 Other Issues on RS Map 106
5.4.1 Implementation Issues and Computational Complexity 106
5.4.2 Norms of Columns of RS Map 108
5.5 Applications 110
5.5.1 IIPF Decomposition 110
5.5.2 Frequency Estimation 114
5.5.3 Harmonic Analysis 114
5.6 Summary 117
III Exponential Fitting by Pade Approximation 119
Chapter 6 Z-transform, Pade Approximation and Prony Analysis 121
6.1 Pade Approximation 122
6.1.1 Motivation 122
6.1.2 Formulation 127
6.2 Pade-Z Transform 132
6.2.1 Pade-Z Transform of Exponential Functions 132
6.2.2 Distribution of Poles and Zeros 134
6.3 Prony Analysis 138
6.3.1 Harmonic Analysis by Fourier Series and Fourier Transform 139
6.3.2 Harmonic Analysis by Prony Analysis 142
6.4 The Equivalence between Pade-Z Transform and Prony Analysis 148
6.5 Summary 149
Chapter 7 The Proposed Exponential Fitting Method 151
7.1 System Model 152
7.1.1 Formulation 152
7.1.2 Z-transform of Damped Oscillators 153
7.2 Proposed Method 158
7.2.1 Previous Works 158
7.2.2 Framework of Proposed Method 163
7.3 P/Z Matching Algorithms 164
7.3.1 Distance Ranking 165
7.3.2 Hungarian Algorithm 166
7.4 P/Z Recognition and Recovering 176
7.4.1 P/Z Recognition 177
7.4.2 P/Z Recovering 181
7.5 Experimental Results 183
7.5.1 Performance Analysis for Each Stage 184
7.5.2 Comparison with Prony Analysis 190
7.5.3 Overall Accuracy Analysis 193
7.6 Summary 193
IV Conclusion and References 197
Chapter 8 Conclusion 199
References 201

General
[A1] D. Thomson, “Spectrum estimation and harmonic analysis,” Proceedings of the IEEE, vol. 70, no. 9, pp. 1055–1096, 1982, ISSN: 0018-9219. DOI: 10.1109/PROC.1982.12433.
[A2] V. F. Pisarenko, “The retrieval of harmonics from a covariance function,” Geophysical Journal of the Royal Astronomical Society, vol. 33, no. 3, pp. 347–366, 1973, ISSN: 1365-246X. DOI: 10.1111/j.1365-246X.1973.tb03424.x. [Online]. Available: http://dx.doi.org/10.1111/j.1365- 246X.1973.
tb03424.x.
[A3] A. V. Oppenheim, A. S. Willsky, and S. H. Nawab, Signals &;Amp; Systems (2Nd Ed.) Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 1996, ISBN: 0-13-814757-4.
[A4] A. V. Oppenheim, R. W. Schafer, and J. R. Buck, Discrete-time Signal Processing (2Nd Ed.) Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 1999, ISBN: 0-13-754920-2.
[A5] J. Stewart, Calculus, ser. Available 2010 Titles Enhanced Web Assign Series.Cengage Learning, 2007, ISBN: 9780495011606. [Online]. Available: http://books.google.com.tw/books?id=jBD0yTh64wAC.
[A6] R. A. Horn and C. R. Johnson, Eds., Matrix Analysis. New York, NY, USA: CambridgeUniversity Press, 1986, ISBN: 0-521-30586-1.
Number Theory
[B1] I. Niven, H. L. Montgomery, and H. S. Zuckerman, An introduction to the theoryof numbers, English, 5th ed. New York : Wiley, 1991, Includes indexes, ISBN:0471625469.
[B2] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, English, 4th ed., 2nd (corr.) impression. Clarendon Press Oxford, 1960, xvi, 421 p.
[B3] J. Wrench John W., “Evaluation of Artin’s constant and the twin-prime constant,” English, Mathematics of Computation, vol. 15, no. 76, pp. 396–398, 1961, ISSN:00255718. [Online]. Available: http://www.jstor.org/stable/2003029.
Ramanujan Sum
[C1] S. Ramanujan, “On certain trigonometric sums and their applications,” Trans. Cambridge Philos. Soc., vol. 22, pp. 259–276, 1918.
[C2] Laszlo Toth. (2007). Ramanujan sum, [Online]. Available: http://ttk.pte.
hu/matek/ltoth/Ramanujan07.pdf.
[C3] R. D. von Sterneck. Sitzungsber, Duke Mathematical Journal, pp. 1567–1601,1902.
[C4] M. Planat, H. C. Rosu, and S. Perrine, “Ramanujan sums for signal processing of low frequency noise,” Phys. Rev. E, vol. 66, 2002.
[C5] P. Haukkanen, “Discrete Ramanujan-Fourier transform of even functions (mod r),” Indian J. Math. Math. Sci., vol. 3, no. 1, pp. 75–80, 2007.
[C6] L. Toth and P. Haukkanen, “The discrete Fourier transform of r-even functions,” Acta Univ. Sapientiae, Mathematica, vol. 3, no. 1, pp. 5–25, 2011.
[C7] V. Laohakosol, P. Ruengsinsub, and N. Pabhapote, “Ramanujan sums for signal processing of low frequency noise,” Phys. Rev. E, 2006.
[C8] D. R. Anderson and T. M. Apostol, “The evaluation of Ramanujan’s sum and generalizations,” Duke Mathematical Journal, vol. 20, no. 2, pp. 211–216, Jun. 1953. DOI: 10.1215/S0012-7094-53-02021-3. [Online]. Available: http:
//dx.doi.org/10.1215/S0012-7094-53-02021-3.
[C9] T. M. Apostol, “Arithmetical properties of generalized Ramanujan sums,” Pacific J. of Mathematics, vol. 41, no. 2, 1972.
[C10] P. J. McCarthy, “A generalization of Smith’s determinant,” Canad. Math. Bull., vol. 29, no. 1, pp. 109–113, 1986.
[C11] S. Samadi, M. O. Ahmad, and M. N. S. Swamy, “Ramanujan sums and discrete Fourier transform,” IEEE Signal Process. Lett., vol. 12, no. 4, pp. 293–296, 2005.
[C12] S.-C. Pei and K.-W. Chang, “Odd Ramanujan sums of complex roots of unity,” IEEE Signal Process. Lett., vol. 14, no. 1, pp. 20–23, 2007.
[C13] C. F. Fowler, S. R. Garcia, and G. Karaali, “Ramanujan sums as supercharacters,” arXiv, 2012.
[C14] L. Sugavaneswaran, S. Xie, K. Umapathy, and S. Krishnon, “Time-frequency analysis via Ramanujan sums,” IEEE Signal Process. Lett., vol. 19, no. 6, pp. 352–355, 2012.
[C15] L. T. Mainardi, L. Pattini, and S. Cerutti, “Application of the Ramanujan Fourier transform for the analysis of secondary structure content in amino acid sequences,” Meth. Inf. Med., vol. 46, no. 2, pp. 126–129, 2007.
[C16] L. T. Mainardi, M. Bertinelli, and R. Sassi, “Analysis of T-wave alternans using the Ramanujan sums,” Comput. Cardiol., vol. 35, pp. 605–608, 2008.
[C17] M. Lagha and M. Bensebti, “Doppler spectrum estimation by Ramanujsn-Fourier transform (RFT),” Digital Signal Process., vol. 19, no. 5, pp. 843–851, 2009.
[C18] G. Chen, S. Kishnan, and T. B. Bui, “Matrix-based Ramanujan-sums transforms,” IEEE Signal Process. Lett., vol. 20, no. 10, 2013.
[C19] G. Y. Chen, S. Krishnon, W. Liu, and W. F. Xie, “Ramanujan sums for sparse signal analysis,” Proc. Minth Int. Conf. Intelligent Computing (ICIC), 2013.
[C20] X. Guo, S. Huang, Z. Wang, and L. Zhou, “Research on Ramanujan-FMT modulation and the efficient implementation algorithm,” Journal of Beijing University of Aeronautics and Astronautics, 2013.
[C21] G. Chen, S. Krishnan, and T. D. Bui, “Ramanujan sums for image pattern analysis,” International Journal of Wavelets, Multiresolution and Information Processing, vol. 12, no. 01, p. 1 450 003, 2014. [Online]. Available: http://spectrum.library.concordia.ca/978239/.
[C22] M. Planat, M. Minarovjech, and M. Saniga, “Ramanujan sums analysis of longperiod sequences and 1/f noise,” Mathematical Physics, 2009.
[C23] G. Y. Chen, S. Krishnon, W. Liu, and W. F. Xie, “Ramanujan sums-wavelet transform for signal analysis,” Proc. Int. Conf. on Wavelet Anal. and Pattern Recognition (ICWAPR), 2013.
[C24] I. Korkee and P. Haukkanen, “On a general form of meet matrices associated with incidence functions,” Linear and Multilinear Algebra, vol. 53, no. 5, pp. 309–321, 2005.
Pade Approximation and Prony Analysis
[D1] L. Perotti, D. Vrinceanu, and D. Bessis, “Beyond the Fourier Transform: Signal Symmetry Breaking in the Complex Plane,” IEEE Signal Process. Lett., vol. 19, no. 12, pp. 865–867, 2012.
[D2] C. Brezinski, History of Continued Fractions and Pade Approximants. Springer-Verlag, 1991.
[D3] R. Prony, “Essai Experimental et Analytique, etc.,” Paris J. l’Ecole Polytechnique, vol. 1, pp. 24–76, 1795.
[D4] T. J. Ulrych and R. W. Clayton, “Time series modelling and maximum entropy,” Physics of the Earth and Planetary Interiors, vol. 12, no. 2–3, pp. 188 –200, 1976, ISSN: 0031-9201. DOI: http : / / dx . doi . org / 10 . 1016 / 0031 - 9201(76 ) 90047-9. [Online]. Available: http://www.sciencedirect.com/science/
article/pii/0031920176900479.
[D5] A. Nuttall, N. U. S. C. NEWPORTRI., and N. U. S. C. U. N. L. Laboratory, Spectral Analysis of a Univariate Process with Bad Data Points, Via Maximum Entropy, and Linear Predictive Techniques, ser. NUSC technical report. New London Laboratory, Naval Underwater Systems Center, 1976. [Online]. Available: http://books.google.com.tw/books?id=7gUJywAACAAJ.
[D6] G. H. Golub and C. Van Loan, “An analysis of the total least squares problem,” Ithaca, NY, USA, Tech. Rep., 1980.
[D7] M. Rahman and K.-B. Yu, “Total least squares approach for frequency estimation using linear prediction,” Acoustics, Speech and Signal Processing, IEEE Transactions on, vol. 35, no. 10, pp. 1440–1454, 1987, ISSN: 0096-3518. DOI: 10. 1109/TASSP.1987.1165059.
[D8] D. Tufts and R. Kumaresan, “Singular value decomposition and improved frequency estimation using linear prediction,” Acoustics, Speech and Signal Processing, IEEE Transactions on, vol. 30, no. 4, pp. 671–675, 1982, ISSN: 0096-3518. DOI: 10.1109/TASSP.1982.1163927.
[D9] L. Weiss and R. McDonough, “Prony’s Method, Z-Transforms, and Pade Approximation,” SIAM Review, vol. 5, no. 2, pp. 145–149, 1963. DOI: 10.1137/
1005035. eprint: http://epubs.siam.org/doi/pdf/10.1137/1005035. [Online]. Available: http://epubs.siam.org/doi/abs/10.1137/1005035.
[D10] J Gilewicz and B Truong-Van, “Froissart doublets in the Pade approximation and noise,” CNRS Marseille. Cent. Phys. Theor., Marseille, Tech. Rep. CPT-2014. M-CPT-2014, 1987.
[D11] J. Gilewicz and Y. Kryakin, “Froissart doublets in Pade approximation in the case of polynomial noise,” Journal of Computational and Applied Mathematics, vol. 153, no. 1–2, pp. 235 –242, 2003, Proceedings of the 6th International Symposium on Orthogonal Poly nomials, Special Functions and their Applications, Rome, Italy, 18-22 June 2001, ISSN: 0377-0427. DOI: http://dx.doi.org/10 . 1016 / S0377 - 0427(02 ) 00674 - X. [Online]. Available: http : / / www .sciencedirect.com/science/article/pii/S037704270200674X.
[D12] P. Barone, “On the distribution of poles of Pade approximants to the Z-transform of complex Gaussian white noise,” Journal of Approximation Theory, vol. 132, no. 2, pp. 224–240, 2005, ISSN: 0021-9045. DOI: http://dx.doi.org/10.1016/j.jat.2004.10.014. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S002190450400187X.
[D13] D. Bessis and L. Perotti, “Universal analytic properties of noise. Introducing the J-Matrix formulation,” J. Phys., vol. 42, no. A365202, p. 15, 2009.
Other
[E1] M. Elfeky, W. Aref, and A. Elmagarmid, “Periodicity detection in time series databases,” Knowledge and Data Engineering, IEEE Transactions on, vol. 17, no. 7, pp. 875–887, 2005, ISSN: 1041-4347. DOI: 10.1109/TKDE.2005.114.
[E2] ——, “Warp: time warping for periodicity detection,” in Data Mining, Fifth IEEE International Conference on, 2005, 8 pp.–. DOI: 10.1109/ICDM.2005.152.
[E3] S. Papadimitriou, A. Brockwell, and C. Faloutsos, “Adaptive, hands-off stream mining,” in Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29, ser. VLDB ’03, Berlin, Germany: VLDB Endowment, 2003, pp. 560–571, ISBN: 0-12-722442-4. [Online]. Available: http://dl.acm.org/citation.cfm?id=1315451.1315500.
[E4] F. Rasheed, M. Alshalalfa, and R. Alhajj, “Efficient periodicity mining in time series databases using suffix trees,” Knowledge and Data Engineering, IEEE Transactions on, vol. 23, no. 1, pp. 79–94, 2011, ISSN: 1041-4347. DOI: 10.1109/TKDE.2010.76.
[E5] N Levinson, “The Wiener RMS (root mean square) error criterion in filter design and prediction,” 1947.
[E6] W. F. Trench, “An algorithm for the inversion of finite Toeplitz matrices,” Journal of the Society for Industrial &; Applied Mathematics, vol. 12, no. 3, pp. 515–522, 1964.
[E7] D. A. Bini, L. Gemignani, and V. Y. Pan, “Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations,” English, Numerische Mathematik, vol. 100, no. 3, pp. 373–408, 2005, ISSN: 0029-599X. DOI: 10.1007/s00211-005-0595-4. [Online]. Available: http://dx.doi.org/10.1007/s00211-005-0595-4.
[E8] A. Eisinberg and G. Fedele, “On the inversion of the Vandermonde matrix,” Applied Mathematics and Computation, vol. 174, no. 2, pp. 1384 –1397, 2006, ISSN: 0096-3003. DOI: http://dx.doi.org/10.1016/j.amc.2005.06.014. [On-line]. Available: http://www.sciencedirect.com/science/article/pii/S0096300305005576.
[E9] H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, no. 1-2, pp. 83–97, 1955, ISSN: 1931-9193. DOI: 10.1002/nav.3800020109. [Online]. Available: http://dx.doi.org/10.1002/nav.3800020109.
[E10] G. A. Korsah, A. T. Stentz, and M. B. Dias, “The dynamic Hungarian algorithm for the assignment problem with changing costs,” Robotics Institute, Pittsburgh, PA, Tech. Rep. CMU-RI-TR-07-27, 2007.
[E11] D. Comaniciu and P. Meer, “Mean shift: a robust approach toward feature space analysis,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 24, no. 5, pp. 603–619, 2002, ISSN: 0162-8828. DOI: 10.1109/34.1000236.
[E12] B. Finkston. (2006). Mean shift clustering, [Online]. Available: http://www.mathworks . com / matlabcentral / fileexchange / 10161 - mean - shift - clustering/content/MeanShiftCluster.m.199