Как выполнить * Быстрый * DCT (Дискретное косинусное преобразование) в R?

Question

Использование Rprof показало, что dct в пакете dtt является основным нарушителем в фрагменте кода R, который работал довольно медленно. Переставляя его для fft в пакете статистики (который не является одним и тем же преобразованием, но должен занимать одно и то же время для вычисления), мое время выполнения значительно улучшилось. Фактически, 2/3 моих строк Rprof ранее были dct-вызовами, и только 3 строки из 600 были fft-вызовами после включения коммутатора.

Является ли реализация dct в пакете dtt не выполнена с использованием быстро дискретное преобразование Фурье? Если да, есть ли пакет, который имеет его? (Я знаю, что можно удвоить данные, а затем извлечь коэффициенты для dct из этих коэффициентов fft, но прямой быстрый dct, безусловно, будет приятнее, и действительно должен быть где-то).

Answer 1

Похоже, что нет быстрого dct, но в пакете статистики есть fft (быстрое преобразование Фурье), так вот как вы могли бы получить быстрый dct, используя fft.

Используйте это на свой страх и риск. Я не делал серьезных проверок. Я проверил его на нескольких векторах разных размеров и дал те же результаты, что и функция dct в пакете dtt. Если кто-то хочет дважды проверить меня, сравнив его с выходом из dct, тогда вы можете сделать это и опубликовать свои результаты.

Возьмите свой вектор и протяните его до вектора в два раза: если ваш вектор равен v = (1,2,3), то удвоить записи до w = (1,2,3,3,2, 1). Обратите внимание на порядок. Если ваш вектор равен v = (1,2,4,9), то удвоить записи до w = (1,2,4,9,9,4,2,1)

Пусть N - длина ваш вектор ORIGINAL (прежде чем вы удвоите его длину).

Тогда первые N коэффициенты .5 * FFT (ш)/ехр (комплекс (мнимая = пи/2/N) * (сл (2 * N) -1)) следует согласовать с вычислительной DCT (v) , за исключением того, что во всех случаях это должно быть значительно быстрее.

Оценка скорости. Если вы используете коэффициент N, тогда время, затрачиваемое на вычисление быстрого dct, похоже на время, необходимое для выполнения медленного dct для каждого из этих простых факторов. Поэтому, если N равно 2^K, это похоже на выполнение K различных медленных преобразований dct на векторе длины два, поэтому его действительно быстро. Если N является простым (наихудший сценарий), то ускорения вообще не происходит. Наибольшее ускорение - на векторах, мощность которых равна двум по длине.

Примечание: Код R выше выглядит невероятно недружелюбным, поэтому позвольте мне сказать, что происходит. После удвоения длины в правильном направлении, первые N коэффициентов fft вы получаете почти правильная вещь. Однако коэффициенты нужно немного подкорректировать. Пусть P обозначает e^(pi * i/2/N). Оставьте только первый коэффициент. Разделите второй коэффициент на P, разделите третий на P^2, разделите четвертый на P^3 и т. Д. Затем разделите на все коэффициенты на 2 (включая первый), чтобы согласовать с нормировкой R, для dct.

Этот должен дать то же самое, что использовать функцию dct в пакете dtt, но значительно быстрее почти во всех случаях.