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

Продукт из булевой функции и матрицы Уолша является его спектр Уолша : ^[1]
(1, 0, 1, 0, 0, 1, 1, 0) × Н (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 ^м  × 2 ^м, матрицу Адамара (масштабируемую с помощью коэффициента нормализации), которая преобразует 2 ^m действительных чисел x _n в 2 ^m действительных чисел X _k . Преобразование Адамара можно определить двумя способами: рекурсивно или с использованием двоичного (с основанием -2) представления индексов n и k .

Рекурсивный, мы определим преобразование 1 × 1 Адамара H ₀ по идентичности H ₀ = 1, а затем определить Н _м для т  > 0 по:

${\ displaystyle H_ {m} = {\ frac {1} {\ sqrt {2}}} {\ begin {pmatrix} H_ {m-1} & H_ {m-1} \\ H_ {m-1} & - H_ {m-1} \ end {pmatrix}}}$

где 1 / √ 2 - нормализация, которая иногда опускается.

Для m  > 1 мы также можем определить H _{m следующим} образом:

${\ displaystyle H_ {m} = H_ {1} \ otimes H_ {m-1}}$

где представляет собой произведение Кронекера . Таким образом, за исключением этого коэффициента нормализации, матрицы Адамара полностью состоят из 1 и -1.${\ displaystyle \ otimes}$

Эквивалентно, мы можем определить матрицу Адамара по ее ( k ,  n ) -й записи, написав

${\ Displaystyle {\ begin {align} k & = \ sum _ {i = 0} ^ {m-1} {k_ {i} 2 ^ {i}} = k_ {m-1} 2 ^ {m-1} + k_ {m-2} 2 ^ {m-2} + \ cdots + 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} + \ cdots + n_ {1} 2 + n_ {0} \ конец {выровнен}}}$

где k _j и n _j - это двоичные цифры (0 или 1) чисел k и n соответственно. Обратите внимание , что для элемента в верхнем левом углу, мы определяем: . В этом случае мы имеем:${\ Displaystyle к = п = 0}$

${\ displaystyle \ left (H_ {m} \ right) _ {k, n} = {\ frac {1} {2 ^ {\ frac {m} {2}}}} (- 1) ^ {\ sum _ {j} k_ {j} n_ {j}}}$

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

Ниже приведены некоторые примеры матриц Адамара.

${\displaystyle {\begin{aligned}H_{0}=+&{\begin{pmatrix}{\begin{array}{r}1\end{array}}\end{pmatrix}}\\H_{1}={\frac {1}{\sqrt {2}}}&{\begin{pmatrix}{\begin{array}{rr}1&1\\1&-1\end{array}}\end{pmatrix}}\\H_{2}={\frac {1}{2}}&{\begin{pmatrix}{\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{array}}\end{pmatrix}}\\H_{3}={\frac {1}{2^{\frac {3}{2}}}}&{\begin{pmatrix}{\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}}\end{pmatrix}}\\\left(H_{n}\right)_{i,j}={\frac {1}{2^{\frac {n}{2}}}}&(-1)^{i\cdot j}\end{aligned}}}$

где - побитовое скалярное произведение двоичных представлений чисел i и j. Например, если , то согласен с вышеизложенным (игнорируя общую константу). Обратите внимание, что первая строка, первый элемент столбца матрицы обозначается .${\displaystyle i\cdot j}$${\displaystyle \scriptstyle n\;\geq \;2}$${\displaystyle \scriptstyle \left(H_{n}\right)_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1}$${\displaystyle \scriptstyle \left(H_{n}\right)_{0,0}}$

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

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

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

Преобразование Адамара фактически эквивалентно многомерному ДПФ размером 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 - это квантовый логический вентиль, известный как вентиль Адамара, и параллельное применение вентильного элемента Адамара к каждому кубиту n-кубитного регистра эквивалентно преобразованию Адамара .${\displaystyle H_{1}}$${\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\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\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 с равной вероятностью (как показано в первых двух операциях). Это в точности похоже на подбрасывание справедливой монеты в стандартной вероятностной модели вычислений . Однако, если вентиль Адамара применяется дважды подряд (как это фактически делается в последних двух операциях), то конечное состояние всегда совпадает с начальным.

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

Вычисление квантового преобразования Адамара - это просто применение логического элемента Адамара к каждому кубиту индивидуально из-за структуры тензорного произведения преобразования Адамара. Этот простой результат означает, что квантовое преобразование Адамара требует log n операций по сравнению с классическим случаем n  log  n операций.

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

Приложения молекулярной филогенетики (эволюционной биологии) [ править ]

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

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

${\displaystyle \gamma (T)=H^{-1}(\ln(Hs(T)))}$

где - матрица Адамара подходящего размера. Это уравнение можно переписать в виде серии из трех уравнений, чтобы упростить его интерпретацию:${\displaystyle H}$

${\displaystyle r=Hs(T)}$

${\displaystyle \rho =\ln(r)}$

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

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

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

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

Пример, показывающий преобразование Адамара для определенного дерева (значения для рабочего примера адаптированы из Waddell et al. 1997 ^[12] )

Индекс	Бинарный паттерн	Шаблоны совмещения	${\displaystyle \gamma (T)}$	${\displaystyle \rho =H^{-1}\gamma (T)}$	${\displaystyle r=\exp(\rho )}$	${\displaystyle s(T)=H^{-1}\rho }$
0	0000	RRRR и YYYY	-0,475	0	1	0,6479
1	0001	RRRY и YYYR	0,2	-0,5	0,6065	0,1283
2	0010	RRYR и YYRY	0,025	-0,15	0,8607	0,02
3 *	0011	RRYY и YYRR	0,025	-0,45	0,6376	0,0226
4	0100	РЫРР и ЫРЫЙ	0,2	-0,45	0,6376	0,1283
5 *	0101	РЫРЬ и ИРЫР	0	-0,85	0,4274	0,0258
6 *	0110	RYYR и YRRY	0	-0,5	0,6065	0,0070
7	0111	RYYY и YRRR	0,025	-0,9	0,4066	0,02

В примере, показанном в этой таблице, используется упрощенная схема трех уравнений, и это для дерева четырех таксонов, которое может быть записано как ((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). Очевидно, обратимая природа филогенетического преобразования Адамара означает, что вектор дерева означает, что вектор дерева соответствует правильному дереву. Анализ Экономичность после трансформации, следовательно , статистически соответствует , ^[13] , как будет стандартный анализ максимального правдоподобия , используя правильную модель (в данном случае модель НКС).${\displaystyle s(T)=H^{-1}\rho }$${\displaystyle \gamma (T)}$

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

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

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

Гораздо большее количество паттернов сайтов в столбце 0 отражает тот факт, что столбец 0 соответствует различиям переходов , которые накапливаются быстрее, чем различия трансверсии практически во всех сравнениях геномных областей (и определенно накапливаются быстрее в псевдогенах гемоглобина, используемых для этого рабочего примера. ^[15]). Если мы рассмотрим шаблон сайта 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, AN; Полури, Р. (июль 2007 г.). "Нелинейные фазовые ортогональные коды типа Уолша для прямой последовательной связи CDMA" (PDF) . Транзакции IEEE по обработке сигналов . 55 (7): 3800–6. DOI : 10.1109 / TSP.2007.894229 .
• Пан, Дженг-шян, метод шифрования данных с использованием дискретного дробного преобразования Адамара (28 мая 2009 г.)
• Лахович, доктор Павел. Преобразование Уолша – Адамара и серия тестов на случайность финансовой отдачи (7 апреля 2015 г.)
• Беддард, Годфри; Йорк, Бриони А. (январь 2011 г.). «Спектроскопия насос-зонд с использованием преобразований Адамара» (PDF) .
• Yorke, Briony A .; Беддард, Годфри; Оуэн, Робин Л .; Пирсон, Арвен Р. (сентябрь 2014 г.). «Кристаллография с временным разрешением с использованием преобразования Адамара» . Методы природы . 11 (11): 1131–1134. DOI : 10.1038 / nmeth.3139 . PMC  4216935 . PMID  25282611 .

Ссылки [ править ]