2016 • 116 Pages • 1.19 MB • English

Posted April 14, 2020 • Uploaded
by elza.shields

PREVIEW PDF

Page 1

FAST ALGORITHMS FOR SELECTION AND MULTIDIMENSIONAL SPARSE FOURIER TRANSFORM by Andr´e Rauh A dissertation submitted to the Faculty of the University of Delaware in partial fulﬁllment of the requirements for the degree of Doctor of Philosophy in Electrical and Computer Engineering Fall 2015 ⃝c 2015 Andr´e Rauh All Rights Reserved

Page 2

ProQuest Number: 10014748 All rights reserved INFORMATION TO ALL USERS The quality of this reproduction is dependent upon the quality of the copy submitted. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if material had to be removed, a note will indicate the deletion. ProQuest 10014748 Published by ProQuest LLC (2016). Copyright of the Dissertation is held by the Author. All rights reserved. This work is protected against unauthorized copying under Title 17, United States Code Microform Edition © ProQuest LLC. ProQuest LLC. 789 East Eisenhower Parkway P.O. Box 1346 Ann Arbor, MI 48106 - 1346

Page 3

FAST ALGORITHMS FOR SELECTION AND MULTIDIMENSIONAL SPARSE FOURIER TRANSFORM by Andr´e Rauh Approved: Kenneth E. Barner, Ph.D. Chair of the Department of Electrical and Computer Engineering Approved: Babatunde Ogunnaike, Ph.D. Dean of the College of Engineering Approved: Ann L. Ardis, Ph.D. Interim Vice Provost for Graduate and Professional Education

Page 4

I certify that I have read this dissertation and that in my opinion it meets the academic and professional standard required by the University as a dissertation for the degree of Doctor of Philosophy. Signed: Gonzalo R. Arce, Ph.D. Professor in charge of dissertation I certify that I have read this dissertation and that in my opinion it meets the academic and professional standard required by the University as a dissertation for the degree of Doctor of Philosophy. Signed: Javier Garcia-Frias, Ph.D. Member of dissertation committee I certify that I have read this dissertation and that in my opinion it meets the academic and professional standard required by the University as a dissertation for the degree of Doctor of Philosophy. Signed: Xiang-Gen Xia, Ph.D. Member of dissertation committee I certify that I have read this dissertation and that in my opinion it meets the academic and professional standard required by the University as a dissertation for the degree of Doctor of Philosophy. Signed: Jose Luis Paredes, Ph.D. Member of dissertation committee

Page 5

ACKNOWLEDGEMENTS First of all I would like to thank my advisor, Dr. Gonzalo Arce for giving me the opportunity to pursue this long and rewarding journey, and for his help and guidance. I would also like to thank my friends in Newark who have supported me throughout the years. I am especially grateful for the friendships I have in my home country in Germany which have continuously reached out to me even though I sometimes fell oﬀ the face oﬀ the earth. In particular I would like to mention my friend Sandra who has helped me when I most needed it. And my dear friend Violet who has enriched my life with so much with just being there. Most of all I would like to thank my family in Germany who has supported me throughout the years and always oﬀered help if I needed some. Without the continuous support of all of these people this endeavour would have been a much tougher one, and for this I would like to say: Thank You! iv

Page 6

TABLE OF CONTENTS LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii LIST OF ALGORITHMS . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv Chapter 1 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Dissertation Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Organization of the Dissertation . . . . . . . . . . . . . . . . . . . . . 7 2 FAST WEIGHTED MEDIAN SEARCH . . . . . . . . . . . . . . . . 10 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 The Quickselect Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4 Optimal Order Statistics In Pivot Selection . . . . . . . . . . . . . . . 21 2.4.1 First pivot p1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.2 Second pivot p2 . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4.3 Subsequent Pivots . . . . . . . . . . . . . . . . . . . . . . . . 31 2.5 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.6 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3 OPTIMIZED SPECTRUM PERMUTATION FOR THE MULTIDIMENSIONAL SPARSE FFT . . . . . . . . . . . . . . . . . 45 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 v

Page 7

3.2 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.2.1 Dual Lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.2.2 Permutation Candidates Algorithm . . . . . . . . . . . . . . . 57 3.2.2.1 Complexity Analysis . . . . . . . . . . . . . . . . . . 60 3.3 Odd Determinant Algorithm . . . . . . . . . . . . . . . . . . . . . . . 61 3.3.1 Error and Complexity Analysis . . . . . . . . . . . . . . . . . 65 3.3.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.4 Sparse FFT Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.5 Multidimensional sparse FFT Algorithm . . . . . . . . . . . . . . . . 69 3.5.1 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . 74 3.6 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4 DICUSSION AND CONCLUDING REMARKS . . . . . . . . . . . 86 4.1 Recommendations for Future Work . . . . . . . . . . . . . . . . . . . 88 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 Appendix A OPTIMALITY PROOF FOR MEDIAN SEARCH . . . . . . . . . 97 B PROOF OF CONVEXITY FOR COST FUNCTION . . . . . . . . 98 C COPYRIGHT NOTICE . . . . . . . . . . . . . . . . . . . . . . . . . . 100 vi

Page 8

LIST OF TABLES ¯ 2.1 This table shows the average number of normalized comparisons C for diﬀerent alpha of alpha input distributions. Note that the number of comparisons are not aﬀected by heavy tailed input distributions. 34 3.1 Overview of the most recent existing sparse FFT algorithms. . . . . 67 3.2 This table show the improvement of the proposed algorithm by avoiding collision generating parameters which can result in a very poor PSNR. 600 input spectra were generated and one iteration of the algorithm was run. The table show the minimum PSNR across all 600 simulations. σp and σr show the corresponding standard deviations of the proposed method and the random method respectively. . . . . 77 vii

Page 9

LIST OF FIGURES 2.1 This ﬁgure visualizes the weighted median sample as the minimum of a cost function. Top: An example cost function TWM(β) with six input samples X1 to X6 and a minimum at β = X(3). Bottom: The ′ derivative T (β) of the cost function (top). Note the zero-crossing WM point at β = X(4) which coincides with the WM. In this example the weights Wi range from 0 to 1, however this is not required in general. 15 2.2 This graph show simulations of the number of comparisons that are needed depending on the subset size chosen for the ﬁrst pivot. Very small subset sizes M0 yield higher overall runtime due to more element-wise comparisons necessary. Very large subset sizes on the other hand are also not optimal since too much runtime is spent on ﬁnding a pivot. The optimal subset size is where the number of comparisons is minimized. This dissertation focuses on ﬁnding a closed form solution to this subset size. The higher M0 is chosen the lower is the variance but the mean increases as well. The lower variance means that the runtime is more reliable which is due to a very good pivot that removes half the elements reliably. (For the graph: N = 8192, 100000 simulations averaged) . . . . . . . . . . . 38 ∗ ˜ ∗ 2.3 The error of the optimal M and the approximated M . The error 0 0 increases as N0 becomes increasingly large. However the relative error stays close to zero since the error grows slower than M0. This result shows the applicability of the approximations. . . . . . . . . . . . . 39 viii

Page 10

2.4 This ﬁgure shows a conceptual depiction of the state of the algorithm after the ﬁrst pivot was chosen and the input sequence partitioned along the pivot p1. In this case the ﬁrst pivot happened to be less than the sought weighted median. During the partitioning step it is 1 easy to calculate the sum of the weighted W which is used to ﬁnd ≤ the optimal second pivot p2. The best strategy for the second pivot is not to choose a pivot as close as possible to the location where the weighted median is expected. This could potentially result in a “wasted” iteration when the second pivot is again less than the WM discard only very few elements. Thus, an overall better strategy is to choose a “safer” pivot which will result in a lower number of comparison on average. . . . . . . . . . . . . . . . . . . . . . . . . . 40 th 2.5 Expected cost Tk for choosing the k order statistic as the second pivot p2. Note that the weighted median is expected to lie at αM. However, choosing this point as the second pivot is far from optimal. This is due the case that the pivot could end up below the weighted median which is highly undesirable. The minimum cost –and hence optimality– is achieved by choosing a slightly larger order statistics as the pivot. (For this plot: N1 = 10000, M1 = 159, α = 0.1) . . . . . . 41 ∗ 2.6 The maximum relative error of the optimal order statistic k and the ˜∗ approximation k . The error decreases as the input size increases. . 42 ∗ 2.7 The relative error of the optimal order statistic k and the ˜∗ 9 13 approximation k for N = 2 (M = 27), N = 2 (M = 175) and 20 N = 2 (M = 4439). It is important to note that the error is small for small α. This is crucial for the algorithm to work well as small α are more likely to occur in practice. . . . . . . . . . . . . . . . . . . 43 2.8 The sample average of the normalized number of comparisons (C/N) for the diﬀerent algorithms. . . . . . . . . . . . . . . . . . . . . . . 44 2.9 Speedup against Floyd and Rivest’s SELECT. . . . . . . . . . . . . 44 3.1 Examples of two dimensional lattice tilings. Left: A simple square lattice. Right: A hexagonal lattice. . . . . . . . . . . . . . . . . . . 52 ix

High Performance Sparse Fast Fourier Transform

2013 • 88 Pages • 703 KB

Mathematics of Multidimensional Fourier Transform Algorithms

1997 • 192 Pages • 15.95 MB

High Performance Sparse Fast Fourier Transform

2013 • 87 Pages • 1.29 MB

Fast Fourier Transform and Convolution Algorithms

1982 • 285 Pages • 5.43 MB

Fast Fourier Transform - Algorithms and Applications

2010 • 443 Pages • 5.13 MB

Fast Fourier Transform - Algorithms and Applications

2012 • 443 Pages • 5.79 MB

Fast Fourier Transform - Algorithms and Applications

2010 • 437 Pages • 11.21 MB

Fast Fourier Transform and Convolution Algorithms

1981 • 259 Pages • 6.64 MB

The Sparse Fourier Transform

2012 • 250 Pages • 5.77 MB

High Performance Sparse Fast Fourier Transform - ETH E-Collection

2013 • 86 Pages • 704 KB

The sparse fourier transform: theory & practice

2016 • 250 Pages • 31.78 MB

An Adaptive Sublinear-Time Block Sparse Fourier Transform

2017 • 82 Pages • 1.38 MB

high-performance sparse fourier transform on parallel architectures

2016 • 226 Pages • 1.36 MB

Algorithms for Discrete Fourier Transform and Convolution

1989 • 363 Pages • 5.9 MB

Fast Fourier Transform Algorithms with Applications

2016 • 341 Pages • 1.42 MB

Algorithms for Discrete Fourier Transform and Convolution (Signal Processing and Digital Filtering)

1997 • 285 Pages • 2.49 MB