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"”.

  1. 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 …

    msu

  2. 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, …

    houston Repository record for High-Performance Sparse Fourier Transform on Parallel Architectures (opens in a new tab)

  3. 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 …

    msu Repository record for Sparsity in the spectrum : sparse fourier transforms and spectral methods for functions of many dimensions (opens in a new tab)

  4. 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 …

    minho-thes Repository record for Sparse reconstruction of multidimensional light transport signals (opens in a new tab)

  5. 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 …

    msu Repository record for Sub-linear Fourier algorithms : theory and implementation (opens in a new tab)

  6. 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 …

    waterloo Repository record for Sparse Polynomial Interpolation and Testing (opens in a new tab)

  7. 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 …

    tamu Repository record for Applications of Coding Theory to Sub-Linear Time Sparse Recovery Problems (opens in a new tab)

  8. 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 …

    texas Repository record for Matrix theory : optimization, concentration, and algorithms (opens in a new tab)

  9. 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 …

    texas Repository record for Using and saving randomness (opens in a new tab)