Improved sparse Fourier approximation results: Faster implementations and stronger guarantees (Q2376358): Difference between revisions

From MaRDI portal
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
 
(3 intermediate revisions by 3 users not shown)
Property / describes a project that uses
 
Property / describes a project that uses: CoSaMP / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/s11075-012-9621-7 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1977453732 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3078293 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Design of Deterministic Matrices for Fast Recovery of Fourier Compressible Functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Iterative hard thresholding for compressed sensing / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2781419 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information / rank
 
Normal rank
Property / cites work
 
Property / cites work: Stable signal recovery from incomplete and inaccurate measurements / rank
 
Normal rank
Property / cites work
 
Property / cites work: Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies? / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4515159 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Compressed sensing and best 𝑘-term approximation / rank
 
Normal rank
Property / cites work
 
Property / cites work: An Algorithm for the Machine Calculation of Complex Fourier Series / rank
 
Normal rank
Property / cites work
 
Property / cites work: Combinatorial Algorithms for Compressed Sensing / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Sparse Spectral Method for Homogenization Multiscale Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Compressed sensing / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fast Fourier Transforms for Nonequispaced Data / rank
 
Normal rank
Property / cites work
 
Property / cites work: Near-optimal sparse fourier representations via sampling / rank
 
Normal rank
Property / cites work
 
Property / cites work: Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3549618 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Combinatorial sublinear-time Fourier algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Empirical evaluation of a sub-linear time sparse DFT algorithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning Decision Trees Using the Fourier Spectrum / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4705314 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4839061 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Randomized Interpolation and Approximation of Sparse Polynomials / rank
 
Normal rank
Property / cites work
 
Property / cites work: CoSaMP: Iterative signal recovery from incomplete and inaccurate samples / rank
 
Normal rank
Property / cites work
 
Property / cites work: Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit / rank
 
Normal rank
Property / cites work
 
Property / cites work: On sparse reconstruction from Fourier and Gaussian measurements / rank
 
Normal rank
Property / cites work
 
Property / cites work: Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit / rank
 
Normal rank

Latest revision as of 13:08, 6 July 2024

scientific article
Language Label Description Also known as
English
Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
scientific article

    Statements

    Improved sparse Fourier approximation results: Faster implementations and stronger guarantees (English)
    0 references
    0 references
    0 references
    21 June 2013
    0 references
    The problem of quickly estimating the best \(k\)-term Fourier representation for a given periodic function \(f:\;[0,2\pi]\to \mathbb C\) is studied. Solving this problem requires the identification of \(k\) of the largest magnitude Fourier series coefficients of \(f\) in worst case \(k^2\cdot\log^{O(1)}N\) time. Randomized sublinear-time Monte Carlo algorithms, which have a small probability of failing to output accurate answers for each input signal, have been developed for solving this problem (Gilbert et al. 2002, 2005). These methods were implemented as the Ann Arbor fast Fourier transform (AAFFT) and empirically evaluated by \textit{M. A. Iwen, A. Gilbert} and \textit{M. Strauss} [Commun. Math. Sci. 5, No. 4, 981--998 (2007; Zbl 1134.65093)]. In this paper, the authors present a new implementation, called the Gopher fast Fourier transform (GFFT), of more recently developed sparse Fourier transform techniques (cf. [\textit{M. A. Iwen}, Found. Comput. Math. 10, No. 3, 303--338 (2010; Zbl 1230.65145); Appl. Comput. Harmon. Anal. 34, No. 1, 57--82 (2013; Zbl 1260.65115)]). Experiments indicate that GFFT is faster than AAFFT.
    0 references
    sparse Fourier approximation
    0 references
    fast Fourier transforms
    0 references
    randomized algorithms
    0 references
    numerical examples
    0 references
    Fourier series coefficients
    0 references
    Monte Carlo algorithm
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references