Sparse Fourier Transform Algorithm for Real-Time Applications
summary
Algorithms recover k large Fourier coefficients in k log N samples and k log N time for exact sparsity (approximate case at k log N samples and k log^2 N time), using co-prime subsampling and phased rotations to bucketize and estimate. Hardware uses low-speed ADCs and software-defined radios plus MEMS comb filters to sense ~1 GHz with 150 MHz aggregated digital bandwidth, working up to ~5% occupancy. A phased-array implementation achieves sub-millisecond beam alignment, ≈100× faster than 802.11ad and ≈10,000× faster than exhaustive search.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 0:57Fast Fourier Transform
- 2:07Sparse Fourier Transform
- 3:07Algorithms
- 5:17Spectrum Crisis
- 6:38Dynamic Spectrum Access
- 7:48RealTime Spectrum Sensing
- 9:15Sparse Recovery
- 10:40How does it work
- 12:20How to bucket eyes
- 14:49Collisions
- 18:50RealTime Receiver
- 25:10millimeter wave
- 27:30wireless networks
- 31:20phase shifters
- 35:25carrier frequency offset
- 38:40random hashing
related talks
19mSSFFT: Energy-Efficient Selective Scaling for Fast Fourier Transform in Embedded GPUs
36mGNU Radio at the Allen Telescope Array
10mRF-Bouncer: A Programmable Dual-band Metasurface for Sub-6 Wireless Networks
37mOptimizing Radio Settings for Algorithms
37mSpectrum Monitoring Network: Tradeoffs, Results, and Future Directions
28mCommunication Avoiding Algorithms for Linear Algebra and Beyond
23mThursday Lightning Talks
42mEfficient GPU Implementation of Affine Index Permutations on Arrays