क्या कोई एफएफटी है जो आवृत्ति के लॉगरिदमिक विभाजन का उपयोग करता है?

Question

विकिपीडिया के Wavelet article इस टेक्स्ट है:

असतत तरंगिका रूपांतरण भी कम computationally जटिल हे लेने (एन) हे की तुलना में समय fast Fourier transform के लिए (एन लॉग ऑन एन) है। यह कम्प्यूटेशनल लाभ ट्रांसफॉर्म के लिए निहित नहीं है, लेकिन एफएफटी के समान दूरी आवृत्ति डिवीजनों के विपरीत, आवृत्ति के लॉगरिदमिक विभाजन की पसंद को दर्शाता है।

इस मतलब वहाँ भी एक FFT की तरह एल्गोरिथ्म के बजाय आवृत्ति रैखिक की एक लघुगणक विभाजन का उपयोग करता है कि करता है? क्या यह ओ (एन) भी है? यह निश्चित रूप से बहुत से अनुप्रयोगों के लिए बेहतर होगा।

Answer 1

हां। हाँ। संख्या

इसे लॉगरिदमिक फूरियर ट्रांसफॉर्म कहा जाता है। इसमें ओ (एन) समय है। हालांकि यह उन कार्यों के लिए उपयोगी है जो धीरे-धीरे बढ़ते डोमेन/abscissa के साथ क्षय हो जाते हैं।

विकिपीडिया लेख वापस जिक्र करते हुए:

मुख्य अंतर यह है कि तरंगिकाओं दोनों समय में स्थानीयकृत हैं और मानक फूरियर जबकि आवृत्ति को बदलने केवल आवृत्ति में स्थानीयकृत किया गया है।

तो यदि आप केवल समय (या अंतरिक्ष, abscissa की अपनी व्याख्या लेना) में स्थानीयकृत किया जा सकता है तो वेवलेट्स (या अलग कोसाइन ट्रांसफॉर्म) एक उचित दृष्टिकोण है। लेकिन अगर आपको आगे बढ़ने की ज़रूरत है, तो आपको चौकोर परिवर्तन की जरूरत है। ।

"हम पेश फूरियर के लिए एक सटीक और विश्लेषणात्मक अभिव्यक्ति एक समारोह है कि लघुगणकीय नमूना कर दिया गया है के बदलने की प्रक्रिया काफी अधिक कुशल है:

http://homepages.dias.ie/~ajones/publications/28.pdf

यहाँ पर एलएफटी बारे में अधिक पढ़ें सार है फ़ंक्शंस या मापन प्रतिक्रियाओं को बदलने के लिए तेज़ फूरियर ट्रांसफ़ॉर्मेशन (एफएफटी) की तुलना में कम्प्यूटेशनल रूप से, जो धीरे-धीरे abscissa मूल्य के साथ क्षय हो जाता है। हम प्रस्तावित विधि को विद्युत चुम्बकीय भूगर्भ विज्ञान से एक उदाहरण के साथ चित्रित करते हैं, जहां स्केलिंग अक्सर ऐसा होता है कि हमारे लॉगरिदमिक फूरियर ट्रांसफॉर्म (एलएफटी) लागू किया जाना चाहिए। उदाहरण के लिए चुना गया है, हम फिर से प्राप्त करने में सक्षम हैं एसएफटी जो एक एफएफटी से उन लोगों के साथ सहमत हैं जो एक समय में 0.5 प्रतिशत के भीतर हैं जो 1.0e2 कम का कारक है। भूभौतिकी में हमारे एलएफटी के संभावित अनुप्रयोगों क्षणिक प्रतिक्रियाओं, हिमनदों लदान और उतराई, जलभृत पुनर्भरण की समस्याओं, सामान्य मोड और पृथ्वी ज्वार पढ़ाई भूकम्प विज्ञान में करने के लिए वाइड बैंड विद्युत चुम्बकीय आवृत्ति प्रतिक्रियाओं का रूपांतरण है, और आवेगी सदमे की लहर मॉडलिंग। "

Answer 2

संपादित करें: यह मुझे लगता है कि इस एल्गोरिथ्म इस प्रश्न के लिए वास्तव में उपयोगी नहीं है पर पढ़ने के बाद, मैं एक विवरण वैसे भी अन्य पाठकों के लिए दे देंगे

वहाँ भी Filon की एल्गोरिथ्म एक विधि Filon की qudrature के आधार पर जो किया जा सकता है । में पाया गया संख्यात्मक व्यंजन यह [पीएचडी थीसिस] [1] टाइमकेल लॉग स्पेस है परिणामस्वरूप अक्सर पैमाने पर है।

यह एल्गोरिदम डेटा/फ़ंक्शंस के लिए उपयोग किया जाता है जो देखा गया समय अंतराल (जो शायद आपका मामला नहीं है) में 0 तक क्षीण हो जाता है, एक सामान्य सरल उदाहरण एक घातीय क्षय होगा।

यदि आपका डेटा अंक (x_0, y_0), (x_1, y_1) ... (x_i, y_i) द्वारा नोट किया गया है और आप स्पेक्ट्रम ए (एफ) की गणना करना चाहते हैं जहां f आवृत्ति से f_min कहता है = 1/x_max f_max = 1/x_min लॉग दूरी पर। प्रत्येक आवृत्ति च के लिए असली हिस्सा तब तक की जाती है:

एक (च) = योग मैं = 0 ... मैं -1 {(y_i + 1 - y_i) से/(x_i + 1 - x_i) * [क्योंकि (2 * pi * च * t_i +1) - क्योंकि (2 * pi * च * t_i)]/((2 * pi * च)^2)}

काल्पनिक हिस्सा है:

ए (एफ) = y_0/(2 * पीआई * एफ) + i = 0 से योग ... i-1 {(y_i + 1 - y_i)/(x_i + 1 - x_i) * [पाप (2 * पीआई * एफ * टी_आई + 1) - पाप (2 * पीआई * एफ * टी_आई)]/((2 * पीआई * एफ)^2)}

[1] ब्लोचोविज़, थॉमस: नीट में ब्रॉडबैंड डाइलेक्ट्रिक स्पेक्ट्रोस्कोपी और बाइनरी आण्विक ग्लास फॉर्मर्स। बैरथ विश्वविद्यालय, 2003, अध्याय 3.2.3

Answer 3

जो भी आप चाहते हैं उसे करने के लिए, आपको विंडोज़ को अलग-अलग समय मापने की आवश्यकता है, जिसका अर्थ है कि निम्न आवृत्तियों को कम से कम अद्यतन मिलता है (2 की शक्तियों के विपरीत आनुपातिक)।

चेक यहाँ FPPO: https://www.rationalacoustics.com/files/FFT_Fundamentals.pdf

इसका मतलब है कि उच्च आवृत्तियों अधिक बार अपडेट करेगा, लेकिन आप हमेशा औसत (चलती औसत अच्छा है), लेकिन यह भी यह तेजी से आगे बढ़ने कर सकते हैं। बेशक, अगर उलटा एफएफटी का उपयोग करने की योजना है, तो आप इनमें से कोई भी नहीं चाहते हैं। इसके अलावा, कम आवृत्तियों पर बेहतर सटीकता (छोटी बैंडविड्थ) होने का मतलब है कि इन्हें 16k विंडोज (1/3 मीटर/सेकेंड) की तरह धीरे-धीरे अपडेट करने की आवश्यकता है।

हाँ, कम आवृत्ति संकेत स्वाभाविक रूप से धीरे-धीरे यात्रा करता है, और इस प्रकार, आपको उन्हें पहचानने के लिए बहुत समय चाहिए। यह कोई समस्या नहीं है कि गणित ठीक कर सकता है। यह एक प्राकृतिक व्यापार है, और आपके पास उच्च आवृत्ति और कम प्रतिक्रिया की उच्च सटीकता नहीं हो सकती है।

मुझे लगता है कि जो लिंक मैं प्रदान करता हूं वह आपके कुछ विकल्पों को स्पष्ट करेगा ... प्रश्न पूछने के 7 साल बाद, दुर्भाग्यवश।