Làm thế nào để thực hiện * Fast * DCT (Chuyển đổi Cosin rời rạc) trong R?

Question

Sử dụng Rprof tiết lộ dct trong gói dtt là kẻ phạm tội chính trong một đoạn mã R đang chạy khá chậm. Trao đổi nó cho fft trong gói thống kê (mà không phải là cùng một chuyển đổi, nhưng nên dùng cùng một thời gian để tính toán) thời gian chạy của tôi được cải thiện đáng kể. Trong thực tế 2/3 dòng Rprof của tôi là các cuộc gọi dct trước đây và chỉ có 3 dòng khoảng 600 cuộc gọi fft sau khi thực hiện chuyển đổi.

Việc triển khai dct trong gói dtt chưa được thực hiện bằng cách sử dụng biến đổi sai số rời nhanh riêng biệt? Nếu vậy, có một gói có một? (Tôi biết người ta có thể nhân đôi dữ liệu, sau đó trích xuất hệ số cho dct từ các hệ số fft đó, nhưng một dct nhanh thẳng chắc chắn sẽ đẹp hơn, và thực sự có nên là một nơi nào đó).

Answer 1

Dường như không có dct nhanh, nhưng có một biến đổi FFT (biến đổi nhanh) trong gói thống kê, do đó, đây là cách bạn có thể thực hiện việc chuyển nhanh bằng FFT.

Hãy tự chịu rủi ro khi sử dụng. Tôi đã không thực hiện bất kỳ kiểm tra nghiêm túc của nó. Tôi đã kiểm tra nó trên một vài vectơ có kích thước khác nhau và nó cho kết quả tương tự như chức năng dct trong gói dtt trên những thứ đó. Nếu bất cứ ai muốn kiểm tra lại tôi bằng cách so sánh nó với đầu ra từ dct thì hãy làm như vậy và đăng kết quả của bạn.

Lấy véc tơ của bạn và mở rộng nó thành véc tơ dài gấp đôi như sau: Nếu vectơ của bạn là v = (1,2,3), sau đó tăng gấp đôi các mục nhập vào w = (1,2,3,3,2, 1). Lưu ý đặt hàng. Nếu vectơ của bạn là v = (1,2,4,9) thì hãy tăng gấp đôi các mục nhập w = (1,2,4,9,9,4,2,1)

Hãy để N là độ dài của vector ban đầu của bạn (trước khi bạn tăng gấp đôi chiều dài của nó).

Sau đó, N hệ số đầu tiên của .5 * FFT (w)/exp (phức tạp (tưởng tượng = pi/2/N) * (seq (2 * N) -1)) nên đồng ý với máy tính DCT (v) ngoại trừ nó sẽ nhanh hơn đáng kể trong hầu hết các trường hợp.

Cân nhắc tốc độ. Nếu bạn là hệ số nguyên tố N thì thời gian cần để tính toán dct nhanh là thời gian cần để thực hiện một dct chậm cho mỗi yếu tố chính. Vì vậy, nếu N là 2^K nó giống như làm một K khác nhau chậm dct biến đổi trên một vector chiều dài hai, do đó, thực sự của nó nhanh. Nếu N là số nguyên tố (trường hợp xấu nhất) thì không có tốc độ nào cả. Tốc độ tăng tốc lớn nhất là trên các vectơ có sức mạnh hai chiều dài.

Lưu ý: Mã R ở trên trông cực kỳ không thân thiện, vì vậy hãy để tôi nói những gì đang diễn ra. Sau khi tăng gấp đôi chiều dài theo đúng cách, hệ số N đầu tiên của fft bạn nhận được là gần như điều đúng. Tuy nhiên các hệ số cần phải được tinh chỉnh một chút. Đặt P cho e^(pi * i/2/N). Để nguyên hệ số đầu tiên. Chia hệ số thứ hai bằng P, chia số thứ ba bằng P^2, chia số thứ tư bằng P^3, vv ... Sau đó chia tất cả hệ số bằng 2 (bao gồm số đầu tiên) để đồng ý với chuẩn hóa R sử dụng cho dct.

Điều này nên cho cùng một điều như sử dụng chức năng dct trong gói dtt nhưng nhanh hơn đáng kể trong hầu hết các trường hợp.