稀疏傅里叶变换,sparse fourier transform,fft的革命性演进

《稀疏傅里叶变换,sparse fourier transform,fft的革命性演进》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、TheSFT:FromTheorytoPracticeHistoryWhatishappening……WorkshoponSparseFourierTransformDate:17-18February,2013Location:MIT15talkscoveringtopicsfromtheorytoapplication(includingphotography,arrayprocesing,sepctralcompressivesensing,FPGA-baseddesign....)DFT&FFTTimecomplexit

2、y:O(n2)FFTisan algorithm tocomputetheDFTTimecomplexity:O(n*logn)SparseFourierTransformGivenacomplexvectorxoflengthn,andaparameterk,estimatetheklargestcoefficientsoftheFouriertransformofx.Inmanyapplications,mostoftheFouriercoefficientsofasignalaresmallorequaltozero.Spa

3、rseFourierTransformSFTworksbybinningtheFouriercoefficientsintoasmallnumberofbuckets.Duetothesparsity,eachbucketislikelytohaveonlyonelargecoefficient,whichcanbelocated(tofinditsposition)andestimated(tofinditsvalue)Usingann-dimensionalfiltervectorGthatisconcentratedboth

4、intimeandfrequencypassregionOnecanrandomizethepositionsofthefrequenciesbysamplingthesignalintimedomainappropriatelySparseFourierTransformEstimation：thephasedifferencebetweentwosamplesofthefilteredsignalislinearintheindexofthecoefficient,andhencewecanrecovertheindexbye

5、stimatingthephasesUpdatingthesignal:thefilteringprocessneedstoberepeatedtoensurethateachcoefficientiscorrectlyidentifiedOngoingsFFTProjects(BeyondTheory)LightFieldPhotographySpectrumSharingMedicalImagingGPSsFFTChipSpectrumCrisisTheFCCpredictsaspectrumcrunchstarting201

6、3Butatanytime,mostofthespectrumisunusedSpectrumSharingSensetofindunusedbands;Usethem!HowdoyoucaptureGHzofspectrum?SeattleJanuary7,2013ChallengesinSparseGHzAcquisitionGHzsamplingisexpensiveandhigh-powerTensofMHzADC

7、rCompressivesensingusingGHzanalogmixingisexpensive,andrequiresheavycomputationHashthespectrumintoafewbucketsfEstimatethelargecoefficientineachnon-emptybucketRecapofsFFT1-Bucketize2-EstimateCanignoreemptybucketSpectrumSensing&DecodingwithsFFTBucketizeEstimateSpectrumS

8、ensing&DecodingwithsFFTBucketizeEstimateSub-samplingtimeAliasingthefrequenciesSpectrumSensing&DecodingwithsFFTHashfreqs.usi