Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions
Badih GhaziHaitham HassaniehPiotr IndykDina KatabiEric PriceLixin ShiPublished in: CoRR (2013)
Keyphrases
- fourier transform
- average case
- worst case
- frequency domain
- worst case analysis
- competitive ratio
- signal processing
- fourier domain
- radon transform
- learning curves
- fourier analysis
- discrete fourier transform
- uniform distribution
- log polar
- upper bound
- lower bound
- correlation function
- optimal solution
- sample size
- vc dimension
- pattern recognition
- face recognition
- greedy heuristic
- image quality
- polar coordinates
- np hard
- multiresolution
- average case complexity