Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 9 of 9 for “"sparse Fourier transform"”.
-
Sub-linear sparse fourier transform algorithm
The Discrete Fourier Transform (DFT) plays a crucial role in signal processing and scientific computing. The most famous algorithm for computing the DFT is the Fast Fourier Transform (FFT), which has runtime O(N log N) for an input vector with length N. However, with the increasing size of data …
-
High-Performance Sparse Fourier Transform on Parallel Architectures
Fast Fourier Transform (FFT) is one of the most important numerical algorithms widely used in numerous scientific and engineering computations. With the emergence of big data problems, however, in which the size of the processed data can easily exceed terabytes, it is challenging to acquire, …
-
Sparsity in the spectrum : sparse fourier transforms and spectral methods for functions of many dimensions
The Fourier basis has been a cornerstone of numerical approximations due in part to its amenable algebraic properties resulting in efficient algorithmic approaches. Primary among these is the Fast Fourier Transform (FFT) which transforms a collection samples of a univariate function into that …
-
Sparse reconstruction of multidimensional light transport signals
… of sampled light paths and do so by exploiting sparse reconstruction techniques. These techniques allow the recovery of signals even when sampled at unusually low frequencies, in fact, well below the Nyquist limit. This is possible by exploiting some a priori knowledge, namely, the fact that the …
-
Sub-linear Fourier algorithms : theory and implementation
We present a new deterministic algorithm for the sparse Fourier transform problem, in which we seek to identify k << N significant Fourier coefficients from a signal of bandwidth N. Previous deterministic algorithms exhibit quadratic runtime scaling in k, while our algorithm scales linearly with k …
-
Sparse Polynomial Interpolation and Testing
… evaluations. We consider the interpolation of a sparse polynomial, i.e., where f is comprised of a small, bounded number of terms. Sparse interpolation dates back to work in the late 18th century by the French mathematician Gaspard de Prony, and was revitalized in the 1980s due to advancements by …
-
Applications of Coding Theory to Sub-Linear Time Sparse Recovery Problems
… connection between coding theory and classical sparse recovery problems like sparse Fourier and Hadamard transform computations to understand properties of existing recovery algorithms under various signal models, propose improvements, and adopt them to interesting applications in theoretical …
-
Matrix theory : optimization, concentration, and algorithms
… tasks, and we give fast algorithms for the sparse Fourier transform problem, which can be thought of as a sparse recovery problem where one cannot freely choose the matrix. We now describe our contributions in more detail. Linear programming is one of the fundamental problems in computer …
-
Using and saving randomness
… useful in computer science. For example, in sparse recovery, randomized algorithms are more efficient and robust than their deterministic counterparts. At the same time, because random sources from the real world are often biased and defective with limited entropy, high-quality randomness is …