Có FFT sử dụng phân chia tần số logarit không?

Question

Wikipedia Wavelet article chứa văn bản này:

Các wavelet rời rạc cũng ít tính toán phức tạp, lấy O (N) lần so với O (N log N) cho fast Fourier transform. Lợi thế tính toán này không phải là vốn có của phép biến đổi, mà phản ánh sự lựa chọn của một phân chia tần số logarit, ngược lại với các phân chia tần số khoảng cách đều nhau của FFT.

Điều này có nghĩa là cũng có một thuật toán giống FFT sử dụng phân chia tần số logarit thay vì tuyến tính? Nó cũng là O (N)? Điều này rõ ràng là thích hợp hơn cho rất nhiều ứng dụng.

Answer 1

Có. Vâng. Số

Nó được gọi là Biến đổi Fourier lôgarit. Nó có thời gian O (n). Tuy nhiên nó rất hữu ích cho các chức năng phân rã chậm với tăng miền/abscissa.

Nhắc lại bài viết wikipedia:

Sự khác biệt chính là wavelets được khoanh vùng trong cả thời gian và tần số trong khi Fourier chuẩn transform chỉ khu trú trong tần số.

Vì vậy, nếu bạn chỉ có thể được bản địa hóa theo thời gian (hoặc không gian, chọn cách giải thích abscissa) thì Wavelets (hoặc biến đổi cosin rời rạc) là một cách tiếp cận hợp lý. Nhưng nếu bạn cần phải tiếp tục và cứ tiếp tục, thì bạn cần biến đổi bẩn thỉu.

Đọc thêm về LFT tại http://homepages.dias.ie/~ajones/publications/28.pdf

Dưới đây là tóm tắt:.

"Chúng tôi trình bày một biểu thức chính xác và phân tích cho biến đổi Fourier của một hàm đã được lấy mẫu loga Thủ tục là hiệu quả hơn đáng kể tính toán so với phép biến đổi Fourier nhanh (FFT) để chuyển đổi các hàm hoặc các đáp ứng đo được mà phân rã từ từ với giá trị abscissa tăng dần.Chúng ta minh họa phương pháp được đề xuất với một ví dụ từ địa vật lý điện từ, trong đó tỉ lệ thường là biến đổi Fourier logarit của chúng ta (LFT) Đối với ví dụ được chọn, chúng tôi có thể lấy lại các sults đồng ý với những người từ một FFT đến trong vòng 0,5 phần trăm trong một thời gian đó là một yếu tố của 1,0e2 ngắn hơn. Các ứng dụng tiềm năng của LFT của chúng tôi trong địa vật lý bao gồm việc chuyển đổi các đáp ứng tần số điện từ băng rộng sang các đáp ứng tức thời, tải trọng và tải xuống băng, vấn đề nạp nước, chế độ bình thường và nghiên cứu thủy triều trong địa chấn và mô hình sóng xung kích. "

Answer 2

EDIT: Sau khi đọc lên trên này tôi nghĩ rằng thuật toán này không thực sự hữu ích cho câu hỏi này, tôi sẽ cung cấp cho một mô tả nào cho người đọc khác. được tìm thấy trong Bí quyết số [Luận án tiến sĩ] [1] này Khoảng thời gian là khoảng cách được ghi nhật ký như là kết quả frequeny quy mô.

Thuật toán này được sử dụng cho dữ liệu/hàm bị phân hủy thành 0 trong khoảng thời gian quan sát (có thể không phải trường hợp của bạn), một ví dụ đơn giản điển hình sẽ là phân rã theo cấp số mũ.

Nếu dữ liệu của bạn được ghi chú theo điểm (x_0, y_0), (x_1, y_1) ... (x_i, y_i) và bạn muốn tính phổ A (f) trong đó f là tần số cho phép nói f_min = 1/x_max đến f_max = 1/x_min khoảng cách nhật ký. Phần thực cho mỗi tần số f sau đó được tính bằng:

A (f) = tổng từ i = 0 ... i-1 {(y_i + 1 - y_i)/(x_i + 1 - x_i) * [cos (2 * pi * f * t_i + 1) - cos (2 * pi * f * t_i)]/((2 * pi f *)^2)}

phần tưởng tượng là:

A (f) = y_0/(2 * pi * f) + tổng từ i = 0 ... i-1 {(y_i + 1 - y_i)/(x_i + 1 - x_i) * [sin (2 * pi * f * t_i + 1) - sin (2 * pi * f * t_i)]/((2 * pi * f)^2)}

[1] Blochowicz, Thomas: Quang phổ điện môi băng rộng trong Gọn gàng và Binary phân tử thủy tinh Formers. Đại học Bayreuth, 2003, Chương 3.2.3

Answer 3

Để làm những gì bạn muốn, bạn cần đo thời gian Windows khác nhau, có nghĩa là tần số thấp hơn được cập nhật ít nhất thường xuyên (tỷ lệ nghịch với lũy thừa của 2).

Kiểm tra FPPO đây: https://www.rationalacoustics.com/files/FFT_Fundamentals.pdf

này có nghĩa là tần số cao hơn sẽ cập nhật thường xuyên hơn, nhưng bạn luôn có trung bình (di chuyển trung bình là tốt), nhưng cũng có thể để cho nó di chuyển nhanh hơn. Tất nhiên, nếu kế hoạch sử dụng FFT nghịch đảo, bạn không muốn bất kỳ điều này. Ngoài ra, để có độ chính xác tốt hơn (băng thông nhỏ hơn) ở tần số thấp hơn, có nghĩa là những nhu cầu này cần cập nhật chậm hơn nhiều, như Windows 16k (1/3 m/s).

Vâng, tín hiệu tần số thấp tự nhiên di chuyển chậm, và do đó tất nhiên, bạn cần rất nhiều thời gian để phát hiện chúng. Đây không phải là vấn đề mà toán học có thể khắc phục. Đó là một giao dịch tự nhiên và bạn không thể có độ chính xác cao, tần số thấp hơn và phản hồi nhanh.

Tôi nghĩ rằng liên kết tôi cung cấp sẽ làm rõ một số tùy chọn của bạn ... 7 năm sau khi bạn đặt câu hỏi, thật không may.