преобразование Адамара

Инволютивное изменение базиса в линейной алгебре

Произведение булевой функции и матрицы Адамара — это ее спектр Уолша: ^{[1] (1, 0, 1, 0, 0, 1} , 1, 0) × H(8) = (4, 2, 0, −2, 0, 2, 0, 2)

Быстрое преобразование Уолша–Адамара , более быстрый способ вычисления спектра Уолша (1, 0, 1, 0, 0, 1, 1, 0).

Исходную функцию можно выразить с помощью ее спектра Уолша как арифметического полинома.

Преобразование Адамара (также известное как преобразование Уолша–Адамара , преобразование Адамара–Радемахера–Уолша , преобразование Уолша или преобразование Уолша–Фурье ) является примером обобщенного класса преобразований Фурье . Оно выполняет ортогональную , симметричную , инволютивную , линейную операцию над 2 ^m действительными числами (или комплексными , или гиперкомплексными числами , хотя сами матрицы Адамара являются чисто действительными).

Преобразование Адамара можно рассматривать как построенное из дискретных преобразований Фурье (ДПФ) размера 2, и фактически оно эквивалентно многомерному ДПФ размера 2 × 2 × ⋯ × 2 × 2. [ ^2] Оно разлагает произвольный входной вектор в суперпозицию функций Уолша .

Преобразование названо в честь французского математика Жака Адамара ( фр. [adamaʁ] ), немецко-американского математика Ганса Радемахера и американского математика Джозефа Л. Уолша .

Определение

Преобразование Адамара H _m представляет собой матрицу размером 2 ^m  × 2 ^m , матрицу Адамара (масштабированную с помощью нормировочного коэффициента), которая преобразует 2 ^m действительных чисел x _n в 2 ^m действительных чисел X _k . Преобразование Адамара можно определить двумя способами: рекурсивно или с использованием двоичного ( по основанию -2) представления индексов n и k .

Рекурсивно мы определяем преобразование Адамара H ₀ размером 1 × 1 с помощью тождества H ₀ = 1, а затем определяем H _m для m  > 0 с помощью: где 1/ √ 2 — это нормализация, которая иногда опускается. $${\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}}$$

Для m  > 1 мы также можем определить H _m как: где представляет собой произведение Кронекера . Таким образом, за исключением этого нормировочного фактора, матрицы Адамара полностью состоят из 1 и −1. $${\displaystyle H_{m}=H_{1}\otimes H_{m-1}}$$ ${\displaystyle \otimes }$

Эквивалентно, мы можем определить матрицу Адамара по ее ( k ,  n )-му элементу, записав $${\displaystyle {\begin{aligned}k&=\sum _{i=0}^{m-1}{k_{i}2^{i}}=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\dots +k_{1}2+k_{0}\\n&=\sum _{i=0}^{m-1}{n_{i}2^{i}}=n_{m-1}2^{m-1}+n_{m-2}2^{m-2}+\dots +n_{1}2+n_{0}\end{aligned}}}$$

где k _j и n _j — это битовые элементы (0 или 1) k и n , соответственно. Обратите внимание, что для элемента в верхнем левом углу мы определяем: . В этом случае мы имеем: ${\displaystyle k=n=0}$ $${\displaystyle (H_{m})_{k,n}={\frac {1}{2^{m/2}}}(-1)^{\sum _{j}k_{j}n_{j}}}$$

Это в точности многомерное ДПФ, нормализованное до унитарного , если входы и выходы рассматривать как многомерные массивы, индексированные n _j и k _j соответственно. ${\textstyle 2\times 2\times \cdots \times 2\times 2}$

Ниже приведены некоторые примеры матриц Адамара. где — побитовое скалярное произведение двоичных представлений чисел i и j. Например, если , то , что соответствует вышесказанному (игнорируя общую константу). Обратите внимание, что первый элемент строки и первого столбца матрицы обозначается как . $${\displaystyle {\begin{aligned}H_{0}&=+{\begin{pmatrix}1\end{pmatrix}}\\[5pt]H_{1}&={\frac {1}{\sqrt {2}}}\left({\begin{array}{rr}1&1\\1&-1\end{array}}\right)\\[5pt]H_{2}&={\frac {1}{2}}\left({\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{array}}\right)\\[5pt]H_{3}&={\frac {1}{2^{3/2}}}\left({\begin{array}{rrrrrrrr}1&1&1&1&1&1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&1&1&1&-1&-1&-1&-1\\1&-1&1&-1&-1&1&-1&1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\end{array}}\right)\\[5pt](H_{n})_{i,j}&={\frac {1}{2^{n/2}}}(-1)^{i\cdot j}\end{aligned}}}$$ ${\displaystyle i\cdot j}$ ${\textstyle n\;\geq \;2}$ $${\displaystyle (H_{n})_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1}$$ ${\textstyle (H_{n})_{0,0}}$

H ₁ — это в точности ДПФ размера 2. Его также можно рассматривать как преобразование Фурье на двухэлементной аддитивной группе Z /(2).

Строки матриц Адамара — это функции Уолша .

Преимущества преобразования Уолша–Адамара

Настоящий

Согласно данному выше определению матрицы H , здесь мы положим H = H [ m , n ] $${\displaystyle H[m,n]={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}$$

В преобразовании Уолша в матрице появятся только 1 и −1. Числа 1 и −1 являются действительными числами, поэтому нет необходимости выполнять комплексные вычисления.

Умножение не требуется.

DFT требует иррационального умножения, а преобразование Адамара — нет. Даже рациональное умножение не нужно, поскольку достаточно просто сменить знак.

Некоторые свойства аналогичны свойствам DFT

В матрице преобразования Уолша все элементы в первой строке (и столбце) равны 1. $${\displaystyle H[m,n]=\left({\begin{array}{rrrrrrrr}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&-1&-1&1&-1&1&1&-1\\1&-1&1&-1&-1&1&-1&1\\1&-1&1&-1&1&-1&1&-1\end{array}}\right)}$$

Дискретное преобразование Фурье： $${\displaystyle e^{-j2\pi mn/N}}$$

В дискретном преобразовании Фурье, когда m равно нулю (среднее значение первой строки), результат ДПФ также равен 1. Во второй строке, хотя она и отличается от первой строки, мы можем наблюдать такую ​​характеристику матрицы, что сигнал в первой необработанной матрице имеет низкую частоту, и он будет увеличивать частоту во второй строке, увеличивая частоту еще больше до последней строки.

Если мы вычислим переход через ноль:

Первая строка = 0 переход через нольВторая строка = 1 переход через нольТретья строка = 2 нулевых перехода ⋮Восемь строк = 7 нулевых переходов

Связь с преобразованием Фурье

Преобразование Адамара фактически эквивалентно многомерному ДПФ размером 2 × 2 × ⋯ × 2 × 2 . ^[2]

Другой подход заключается в том, чтобы рассматривать преобразование Адамара как преобразование Фурье на булевой группе . ^{[3] [4]} Используя преобразование Фурье на конечных (абелевых) группах , преобразование Фурье функции является функцией, определяемой как , где является символом . Каждый символ имеет вид для некоторого , где умножение является булевым скалярным произведением на битовых строках, поэтому мы можем идентифицировать входные данные с помощью ( двойственность Понтрягина ) и определить как ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$ ${\displaystyle f\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} }$ ${\displaystyle {\widehat {f}}}$ $${\displaystyle {\widehat {f}}(\chi )=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a){\bar {\chi }}(a)}$$ ${\displaystyle \chi }$ ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$ ${\displaystyle \chi _{r}(a)=(-1)^{a\cdot r}}$ ${\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}}$ ${\displaystyle {\widehat {f}}}$ ${\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}}$ ${\displaystyle {\widehat {f}}\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} }$ $${\displaystyle {\widehat {f}}(r)=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a)(-1)^{r\cdot a}}$$

Это преобразование Адамара для , рассматривающее входные данные и как логические строки. ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle {\widehat {f}}}$

В терминах приведенной выше формулировки, где преобразование Адамара умножает вектор комплексных чисел слева на матрицу Адамара, эквивалентность видна, если взять в качестве входных данных битовую строку, соответствующую индексу элемента , и получить на выходе соответствующий элемент . ${\displaystyle 2^{n}}$ ${\displaystyle v}$ ${\displaystyle H_{n}}$ ${\displaystyle f}$ ${\displaystyle v}$ ${\displaystyle f}$ ${\displaystyle v}$

Сравните это с обычным дискретным преобразованием Фурье , которое при применении к вектору комплексных чисел вместо этого использует символы циклической группы . ${\displaystyle v}$ ${\displaystyle 2^{n}}$ ${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$

Сложность вычислений

В классической области преобразование Адамара можно вычислить за операций ( ), используя быстрый алгоритм преобразования Адамара . ${\displaystyle n\log n}$ ${\displaystyle n=2^{m}}$

В квантовой области преобразование Адамара можно вычислить во времени, поскольку оно представляет собой квантовый логический вентиль , который можно распараллелить . ${\displaystyle O(1)}$

Приложения квантовых вычислений

Преобразование Адамара широко используется в квантовых вычислениях . Преобразование Адамара 2 × 2 — это квантовый логический вентиль, известный как вентиль Адамара, и применение вентиля Адамара к каждому кубиту -кубитного регистра параллельно эквивалентно преобразованию Адамара . ${\displaystyle H_{1}}$ ${\displaystyle n}$ ${\displaystyle H_{n}}$

ворота Адамара

В квантовых вычислениях вентиль Адамара представляет собой однокубитное вращение , отображающее состояния кубитного базиса и в два суперпозиционных состояния с равным весом состояний вычислительного базиса и . Обычно фазы выбираются так, чтобы ${\displaystyle |0\rangle }$ ${\displaystyle |1\rangle }$ ${\displaystyle |0\rangle }$ ${\displaystyle |1\rangle }$ $${\displaystyle H={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}\langle 0|+{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\langle 1|}$$

в нотации Дирака . Это соответствует матрице преобразования в базисе, также известном как вычислительный базис. Состояния и известны как и соответственно, и вместе составляют полярный базис в квантовых вычислениях . $${\displaystyle H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}$$ ${\displaystyle |0\rangle ,|1\rangle }$ ${\textstyle {\frac {\left|0\right\rangle +\left|1\right\rangle }{\sqrt {2}}}}$ ${\textstyle {\frac {\left|0\right\rangle -\left|1\right\rangle }{\sqrt {2}}}}$ ${\displaystyle \left|{\boldsymbol {+}}\right\rangle }$ ${\displaystyle \left|{\boldsymbol {-}}\right\rangle }$

Операции с воротами Адамара

$${\displaystyle {\begin{aligned}H(|0\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle =:|+\rangle \\H(|1\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle =:|-\rangle \\H(|+\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}+{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|0\rangle \\H(|-\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}-{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|1\rangle \end{aligned}}}$$

Одно применение вентиля Адамара к кубиту 0 или 1 создаст квантовое состояние, которое, если его наблюдать, будет 0 или 1 с равной вероятностью (как видно из первых двух операций). Это в точности как подбрасывание честной монеты в стандартной вероятностной модели вычислений . Однако, если вентили Адамара применяются дважды подряд (что фактически и делается в последних двух операциях), то конечное состояние всегда будет таким же, как и начальное.

Преобразование Адамара в квантовых алгоритмах

Вычисление квантового преобразования Адамара — это просто применение вентиля Адамара к каждому кубиту по отдельности из-за структуры тензорного произведения преобразования Адамара. Этот простой результат означает, что квантовое преобразование Адамара требует операций по сравнению с классическим случаем операций. ${\displaystyle \log _{2}N}$ ${\displaystyle N\log _{2}N}$

Для системы -кубитов вентили Адамара , действующие на каждый из кубитов (каждый инициализирован в ), могут использоваться для подготовки однородных квантовых суперпозиционных состояний, когда имеет вид . В этом случае с кубитами объединенный вентиль Адамара выражается как тензорное произведение вентилей Адамара: ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle |0\rangle }$ ${\displaystyle N}$ ${\displaystyle N=2^{n}}$ ${\displaystyle n}$ ${\displaystyle H_{n}}$ ${\displaystyle n}$ ${\displaystyle H_{n}=\underbrace {H\otimes H\otimes \ldots \otimes H} _{n{\text{ times}}}}$

Результирующее однородное квантовое суперпозиционное состояние тогда имеет вид: Это обобщает приготовление однородных квантовых состояний с использованием вентилей Адамара для любого . ^[5] ${\displaystyle H_{n}|0\rangle ^{\otimes n}={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}|j\rangle }$ ${\displaystyle N=2^{n}}$

Измерение этого однородного квантового состояния приводит к случайному состоянию между и . ${\displaystyle |0\rangle }$ ${\displaystyle |N-1\rangle }$

Многие квантовые алгоритмы используют преобразование Адамара в качестве начального шага, поскольку, как объяснялось ранее, оно отображает n кубитов, инициализированных с помощью, в суперпозицию всех 2 ⁿ ортогональных состояний в базисе с равным весом. Например, это используется в алгоритме Дойча–Йожи , алгоритме Саймона , алгоритме Бернштейна–Вазирани и в алгоритме Гровера . Обратите внимание, что алгоритм Шора использует как начальное преобразование Адамара, так и квантовое преобразование Фурье , которые оба являются типами преобразований Фурье на конечных группах ; первое на , а второе на . ${\displaystyle |0\rangle }$ ${\displaystyle |0\rangle ,|1\rangle }$ ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$ ${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$

Подготовка однородных квантовых суперпозиционных состояний в общем случае, когда ≠ нетривиальна и требует больше работы. Недавно был представлен эффективный и детерминированный подход для подготовки суперпозиционного состояния со сложностью вентиля и глубиной схемы только для всех . ^[6] Этот подход требует только кубитов. Важно, что ни вспомогательные кубиты, ни какие-либо квантовые вентили с множественным управлением не нужны в этом подходе для создания однородного суперпозиционного состояния . ${\displaystyle N}$ ${\displaystyle 2^{n}}$ $${\displaystyle |\Psi \rangle ={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}|j\rangle }$$ ${\displaystyle O(\log _{2}N)}$ ${\displaystyle N}$ ${\displaystyle n=\lceil \log _{2}N\rceil }$ ${\displaystyle |\Psi \rangle }$

Молекулярная филогенетика (эволюционная биология) приложения

Преобразование Адамара может быть использовано для оценки филогенетических деревьев из молекулярных данных. ^{[7] [8] [9]} Филогенетика является подразделом эволюционной биологии, сосредоточенным на понимании взаимосвязей между организмами. Преобразование Адамара, примененное к вектору (или матрице) частот шаблонов сайтов, полученных из множественного выравнивания последовательностей ДНК , может быть использовано для генерации другого вектора, который несет информацию о топологии дерева. Обратимая природа филогенетического преобразования Адамара также позволяет вычислять вероятности сайтов из вектора топологии дерева, что позволяет использовать преобразование Адамара для оценки максимального правдоподобия филогенетических деревьев. Однако последнее применение менее полезно, чем преобразование из вектора шаблона сайта в вектор дерева, поскольку существуют другие способы вычисления вероятностей сайтов ^{[10] [11]} , которые гораздо более эффективны. Однако обратимая природа филогенетического преобразования Адамара действительно предоставляет элегантный инструмент для математической филогенетики. ^{[12] [13]}

Механизм филогенетического преобразования Адамара включает в себя вычисление вектора , который предоставляет информацию о топологии и длинах ветвей дерева с использованием вектора или матрицы шаблона сайта . ${\displaystyle \gamma (T)}$ ${\displaystyle T}$ ${\displaystyle s(T)}$

$${\displaystyle \gamma (T)=H^{-1}(\ln(Hs(T)))}$$где — матрица Адамара соответствующего размера. Это уравнение можно переписать в виде ряда из трех уравнений, чтобы упростить его интерпретацию: ${\displaystyle H}$

$${\displaystyle {\begin{aligned}r&=Hs(T)\\\rho &=\ln r\\\gamma (T)&=H^{-1}\rho \end{aligned}}}$$

Обратимый характер этого уравнения позволяет рассчитать ожидаемый вектор структуры сайта (или матрицу) следующим образом:

$${\displaystyle s(T)=H^{-1}(\exp(H\gamma (T)))}$$

Мы можем использовать модель двухстадийной замены Кавендера–Фарриса– Неймана (CFN) для ДНК, кодируя нуклеотиды как бинарные символы ( пурины A и G кодируются как R, а пиримидины C и T кодируются как Y). Это позволяет кодировать множественное выравнивание последовательностей как вектор шаблона сайта , который может быть преобразован в вектор дерева , как показано в следующем примере: ${\displaystyle s(T)}$ ${\displaystyle \gamma (T)}$

Пример, показанный в этой таблице, использует упрощенную схему из трех уравнений, и это для дерева из четырех таксонов, которое можно записать как ((A,B),(C,D)); в формате newick . Паттерны сайтов записаны в порядке ABCD. Это конкретное дерево имеет две длинные конечные ветви (0,2 трансверсионных замены на сайт), две короткие конечные ветви (0,025 трансверсионных замены на сайт) и короткую внутреннюю ветвь (0,025 трансверсионных замены на сайт); таким образом, оно будет записано как ((A:0,025,B:0,2):0,025,(C:0,025,D:0,2)); в формате newick. Это дерево будет демонстрировать притяжение длинных ветвей , если данные анализируются с использованием критерия максимальной экономии (предполагая, что анализируемая последовательность достаточно длинная, чтобы наблюдаемые частоты паттернов сайтов были близки к ожидаемым частотам, указанным в столбце). Привлекательность длинных ветвей отражает тот факт, что ожидаемое количество шаблонов сайтов с индексом 6, которые поддерживают дерево ((A,C),(B,D)); — превышает ожидаемое количество шаблонов сайтов, которые поддерживают истинное дерево (индекс 4). Очевидно, что обратимая природа филогенетического преобразования Адамара означает, что вектор дерева означает, что вектор дерева соответствует правильному дереву. Анализ экономии после преобразования, таким образом, статистически последователен , ^[15] , как и стандартный анализ максимального правдоподобия с использованием правильной модели (в данном случае модели CFN). ${\displaystyle s(T)=H^{-1}\rho }$ ${\displaystyle \gamma (T)}$

Обратите внимание, что шаблон сайта с 0 соответствует сайтам, которые не изменились (после кодирования нуклеотидов как пуринов или пиримидинов). Индексы со звездочками (3, 5 и 6) являются «экономно-информативными», а остальные индексы представляют шаблоны сайтов, где один таксон отличается от трех других таксонов (поэтому они эквивалентны длинам конечных ветвей в стандартном филогенетическом дереве максимального правдоподобия).

Если кто-то хочет использовать данные нуклеотидов без перекодировки как R и Y (и в конечном итоге как 0 и 1), можно закодировать шаблоны сайтов как матрицу. Если мы рассмотрим дерево из четырех таксонов, то всего будет 256 шаблонов сайтов (четыре нуклеотида в четвертой степени). Однако симметрия трехпараметрической модели Кимуры (или K81) позволяет нам сократить 256 возможных шаблонов сайтов для ДНК до 64 шаблонов, что позволяет закодировать данные нуклеотидов для дерева из четырех таксонов как матрицу 8 × 8 ^[16] способом, аналогичным вектору из 8 элементов, использованному выше для шаблонов сайтов трансверсии (RY). Это достигается путем перекодировки данных с использованием четырехгруппы Клейна :

Как и в случае с данными RY, паттерны сайтов индексируются относительно базы в произвольно выбранном первом таксоне с базами в последующих таксонах, закодированными относительно этой первой базы. Таким образом, первый таксон получает пару битов (0,0). Используя эти пары битов, можно создать два вектора, похожих на векторы RY, а затем заполнить матрицу, используя эти векторы. Это можно проиллюстрировать на примере из Hendy et al. (1994), ^[16], который основан на множественном выравнивании последовательностей четырех псевдогенов гемоглобина приматов:

Гораздо большее количество шаблонов сайтов в столбце 0 отражает тот факт, что столбец 0 соответствует различиям в переходах , которые накапливаются быстрее, чем различия в трансверсиях практически во всех сравнениях геномных регионов (и определенно накапливаются быстрее в псевдогенах гемоглобина, используемых для этого рабочего примера ^[17] ). Если мы рассмотрим шаблон сайта AAGG, то он будет двоичным шаблоном 0000 для второго элемента пары битов группы Клейна и 0011 для первого элемента. В этом случае двоичный шаблон, основанный на первом элементе, соответствует индексу 3 (поэтому строка 3 в столбце 0; обозначена одной звездочкой в ​​таблице). Шаблоны сайтов GGAA, CCTT и TTCC будут кодироваться точно таким же образом. Шаблон сайта AACT будет кодироваться двоичным шаблоном 0011 на основе второго элемента и 0001 на основе первого элемента; это дает индекс 1 для первого элемента и индекс 3 для второго. Индекс, основанный на второй паре битов группы Клейна, умножается на 8, чтобы получить индекс столбца (в данном случае это будет столбец 24). Ячейка, которая будет включать количество шаблонов сайтов AACT, обозначена двумя звездочками; однако отсутствие числа в примере указывает на то, что выравнивание последовательностей не включает шаблонов сайтов AACT (аналогично шаблоны сайтов CCAG, GGTC и TTGA, которые кодировались бы таким же образом, отсутствуют).

Другие приложения

Преобразование Адамара также используется в шифровании данных , а также во многих алгоритмах обработки сигналов и сжатия данных , таких как JPEG XR и MPEG-4 AVC . В приложениях сжатия видео оно обычно используется в виде суммы абсолютных преобразованных разностей . Оно также является важной частью значительного числа алгоритмов в квантовых вычислениях. Преобразование Адамара также применяется в экспериментальных методах, таких как ЯМР , масс-спектрометрия и кристаллография . Оно также используется в некоторых версиях локально-чувствительного хеширования для получения псевдослучайных вращений матриц.

Смотрите также

• Быстрое преобразование Уолша-Адамара
• Псевдо-преобразование Адамара
• преобразование Хаара
• Обобщенный распределительный закон

Внешние ссылки

• Риттер, Терри (август 1996 г.). «Преобразования Уолша–Адамара: обзор литературы».
• Akansu , Ali N.; Poluri, R. (июль 2007 г.). "Нелинейные фазовые ортогональные коды типа Уолша для прямой последовательности CDMA-коммуникаций" (PDF) . IEEE Transactions on Signal Processing . 55 (7): 3800–6. Bibcode : 2007ITSP...55.3800A. doi : 10.1109/TSP.2007.894229. S2CID  6830633.
• Пан, Метод шифрования данных Дженг-шян с использованием дискретного дробного преобразования Адамара (28 мая 2009 г.)
• Лахович, д-р Павел. Преобразование Уолша-Адамара и тесты на случайность финансовых рядов доходности (7 апреля 2015 г.)
• Beddard, Godfrey; Yorke, Briony A. (январь 2011 г.). "Pump-probe Spectroscopy using Adamard Transforms" (PDF) . Архивировано из оригинала (PDF) 2014-10-18 . Получено 2012-04-28 .
• Йорк, Брайони А.; Беддард, Годфри; Оуэн, Робин Л.; Пирсон, Арвен Р. (сентябрь 2014 г.). «Кристаллография с временным разрешением с использованием преобразования Адамара». Nature Methods . 11 (11): 1131–1134. doi :10.1038/nmeth.3139. PMC  4216935 . PMID  25282611.

Ссылки

1. Сравните рисунок 1 в Townsend, WJ; Thornton, MA "Вычисления спектра Уолша с использованием графов Кэли". Труды 44-го симпозиума IEEE 2001 Midwest Symposium on Circuits and Systems (MWSCAS 2001) . MWSCAS-01. IEEE. doi :10.1109/mwscas.2001.986127.
2. Kunz, HO (1979). «Об эквивалентности между одномерным дискретным преобразованием Уолша–Адамара и многомерным дискретным преобразованием Фурье». IEEE Transactions on Computers . 28 (3): 267–8. doi :10.1109/TC.1979.1675334. S2CID  206621901.
3. Анализ Фурье булевых отображений – Учебное пособие –, стр. 12–13
4. Лекция 5: Базовые квантовые алгоритмы, Раджат Миттал, стр. 4–5
5. Нильсен, Майкл А.; Чуан , Айзек (2010). Квантовые вычисления и квантовая информация. Кембридж: Cambridge University Press . ISBN 978-1-10700-217-3. OCLC  43641333.
6. Алок Шукла и Пракаш Ведула (2024). «Эффективный квантовый алгоритм для подготовки однородных квантовых суперпозиционных состояний». Квантовая обработка информации . 23:38 (1): 38. arXiv : 2306.11747 . Bibcode :2024QuIP...23...38S. doi :10.1007/s11128-024-04258-4.
7. Хенди, Майкл Д.; Пенни, Дэвид (декабрь 1989 г.). «Структура количественного изучения эволюционных деревьев». Систематическая зоология . 38 (4): 297. doi :10.2307/2992396. JSTOR  2992396.
8. Хенди, Майкл Д.; Пенни, Дэвид (январь 1993 г.). «Спектральный анализ филогенетических данных». Журнал классификации . 10 (1): 5–24. doi :10.1007/BF02638451. ISSN  0176-4268. S2CID  122466038.
9. Székely, LA, Erdős, PL, Steel, MA, & Penny, D. (1993). Формула обращения Фурье для эволюционных деревьев. Письма в журнал прикладной математики , 6 (2), 13–16.
10. Фельзенштейн, Джозеф (ноябрь 1981 г.). «Эволюционные деревья из последовательностей ДНК: подход максимального правдоподобия». Журнал молекулярной эволюции . 17 (6): 368–376. Bibcode : 1981JMolE..17..368F. doi : 10.1007/BF01734359. ISSN  0022-2844. PMID  7288891. S2CID  8024924.
11. Стаматакис, Александрос (2019), Уорнов, Тэнди (ред.), «Обзор подходов к оптимизации расчетов филогенетического правдоподобия», Биоинформатика и филогенетика , Вычислительная биология, т. 29, Cham: Springer International Publishing, стр. 1–19, doi : 10.1007/978-3-030-10837-3_1, ISBN 978-3-030-10836-6, S2CID  145834168 , получено 2020-10-10
12. Чор, Бенни ; Хенди, Майкл Д.; Холланд, Барбара Р.; Пенни, Дэвид (2000-10-01). «Множественные максимумы правдоподобия в филогенетических деревьях: аналитический подход». Молекулярная биология и эволюция . 17 (10): 1529–1541. doi : 10.1093/oxfordjournals.molbev.a026252 . ISSN  1537-1719. PMID  11018159.
13. Matsen, Frederick A.; Steel, Mike (2007-10-01). Ané, Cécile ; Sullivan, Jack (ред.). «Филогенетические смеси на одном дереве могут имитировать дерево другой топологии». Systematic Biology . 56 (5): 767–775. arXiv : 0704.2260 . doi : 10.1080/10635150701627304 . ISSN  1076-836X. PMID  17886146.
14. Waddell, Peter J; Steel, MA (декабрь 1997 г.). «Общие обратимые во времени расстояния с неравными скоростями по сайтам: смешивание Γ и обратных гауссовых распределений с инвариантными сайтами». Молекулярная филогенетика и эволюция . 8 (3): 398–414. doi :10.1006/mpev.1997.0452. PMID  9417897.
15. Стил, MA; Хенди, MD; Пенни, D. (1993-12-01). «Экономия может быть последовательной!». Систематическая биология . 42 (4): 581–587. doi :10.1093/sysbio/42.4.581. ISSN  1063-5157.
16. Хенди, МД; Пенни, Д.; Стил, МА (1994-04-12). «Дискретный анализ Фурье для эволюционных деревьев». Труды Национальной академии наук . 91 (8): 3339–3343. Bibcode : 1994PNAS...91.3339H. doi : 10.1073/pnas.91.8.3339 . ISSN  0027-8424. PMC 43572. PMID 8159749  . 
17. Миямото, ММ; Куп, БФ; Слайтом, ДжЛ; Гудман, М.; Теннант, МР (1988-10-01). «Молекулярная систематика высших приматов: генеалогические связи и классификация». Труды Национальной академии наук . 85 (20): 7627–7631. Bibcode : 1988PNAS...85.7627M. doi : 10.1073/pnas.85.20.7627 . ISSN  0027-8424. PMC 282245. PMID 3174657  .