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

«Преобразование Уолша» перенаправляется сюда. Не следует путать с Матрица Уолша.

В товар из Логическая функция и Матрица Уолша это его Спектр Уолша:^[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^м действительные числа (или сложный, или гиперкомплексные числа, хотя сами матрицы Адамара вполне реальны).

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

Преобразование названо в честь Французский математик Жак Адамар, немецко-американский математик Ганс Радемахер, и американский математик Джозеф Л. Уолш.

Определение

Преобразование Адамара ЧАС_м это 2^м × 2^м матрица, Матрица Адамара (масштабируется с помощью коэффициента нормализации), который преобразует 2^м действительные числа Икс_п в 2^м действительные числа Икс_k. Преобразование Адамара можно определить двумя способами: рекурсивно, или используя двоичный (база -2) представление индексов п и k.

Рекурсивно определим преобразование Адамара 1 × 1 ЧАС₀ посредством идентичность ЧАС₀ = 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 это нормализация, которая иногда опускается.

Для м > 1, мы также можем определить ЧАС_м от:

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

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

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

${\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}+\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}\end{aligned}}}$

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

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

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

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

${\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}}}$

где ${\displaystyle i\cdot j}$ - побитовое скалярное произведение двоичных представлений чисел i и 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}}$.

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

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

Вычислительная сложность

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

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

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

Дальнейшая информация: Квантовые ворота § Ворота Адамара (H)

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

Приложения для молекулярной филогенетики (эволюционной биологии)

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

Механика филогенетического преобразования Адамара включает вычисление вектора ${\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)))}$

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

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

Показатель	Бинарный паттерн	Шаблоны совмещения	${\displaystyle \gamma (T)}$	${\displaystyle \rho =H^{-1}\gamma (T)}$	${\displaystyle r=\exp(\rho )}$	${\displaystyle s(T)=H^{-1}\rho }$
0	0000	РРРР и ГГГГ	-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. Это дерево будет выставлено аттракцион длинной ветви если данные анализируются с помощью максимальная экономия критерий (при условии, что анализируемая последовательность достаточно длинна, чтобы наблюдаемые частоты паттернов сайтов были близки к ожидаемым частотам, показанным ${\displaystyle s(T)=H^{-1}\rho }$ столбец). Привлекательность длинной ветви отражает тот факт, что ожидаемое количество шаблонов сайтов с индексом 6 - которые поддерживают дерево ((A, C), (B, D)); - превышает ожидаемое количество шаблонов сайтов, поддерживающих истинное дерево (индекс 4). Очевидно, обратимый характер филогенетического преобразования Адамара означает, что древовидный вектор означает, что древовидный вектор ${\displaystyle \gamma (T)}$ соответствует правильному дереву. Следовательно, анализ экономичности после преобразования статистически согласованный,^[11] как и стандартный анализ максимального правдоподобия с использованием правильной модели (в данном случае модели CFN).

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

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

Четырехгрупповое кодирование Клейна для филогенетического преобразования Адамара

Нуклеотид 1	Нуклеотид 2	Нуклеотид 3	Нуклеотид 4
А (0,0)	G (1,0)	С (0,1)	Т (1,1)
С (0,0)	Т (1,0)	А (0,1)	G (1,1)
G (0,0)	А (1,0)	Т (0,1)	С (1,1)
Т (0,0)	С (1,0)	G (0,1)	А (1,1)

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

Пример выравнивания кодируемых последовательностей (от Hendy et al. 1994^[12])(значения рассчитаны из 9879 сайтов)

	0	8	16	24	32	40	48	56
0	8988	9	10	12	24			90
1	41	9		**
2	45		13
3	54*			14				3
4	94				20
5			1
6	2				2
7	356		1		1			75

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

использованная литература

1. Сравните рисунок 1 в Townsend, W. J .; Торнтон, М. А. "Вычисления спектра Уолша с использованием графов Кэли". CiteSeerX  10.1.1.74.8029.
2. Кунц, Х. (1979). "Об эквивалентности одномерного дискретного преобразования Уолша-Адамара и многомерного дискретного преобразования Фурье". Транзакции IEEE на компьютерах. 28 (3): 267–8. Дои:10.1109 / TC.1979.1675334.
3. Хенди, Майкл Д .; Пенни, Дэвид (декабрь 1989 г.). «Основы количественного исследования эволюционных деревьев». Систематическая зоология. 38 (4): 297. Дои:10.2307/2992396.
4. Хенди, Майкл Д .; Пенни, Дэвид (январь 1993). «Спектральный анализ филогенетических данных». Журнал классификации. 10 (1): 5–24. Дои:10.1007 / BF02638451. ISSN  0176-4268.
5. Секели, Л. А., Эрдёш, П. Л., Стил, М. А., и Пенни, Д. (1993). Формула обращения Фурье для эволюционных деревьев. Письма по прикладной математике, 6(2), 13-16.
6. Фельзенштейн, Джозеф (ноябрь 1981 г.). «Эволюционные деревья из последовательностей ДНК: подход максимального правдоподобия». Журнал молекулярной эволюции. 17 (6): 368–376. Дои:10.1007 / BF01734359. ISSN  0022-2844.
7. Стаматакис, Александрос (2019), Варнов, Тэнди (ред.), «Обзор подходов к оптимизации вычислений филогенетического правдоподобия», Биоинформатика и филогенетика, Cham: Springer International Publishing, 29, стр. 1–19, Дои:10.1007/978-3-030-10837-3_1, ISBN  978-3-030-10836-6, получено 2020-10-10
8. Чор, Бенни; Хенди, Майкл Д .; Голландия, Барбара Р .; Пенни, Дэвид (2000-10-01). «Множественные максимумы правдоподобия в филогенетических деревьях: аналитический подход». Молекулярная биология и эволюция. 17 (10): 1529–1541. Дои:10.1093 / oxfordjournals.molbev.a026252. ISSN  1537-1719.
9. Matsen, Frederick A .; Сталь, Майк (2007-10-01). Ане, Сесиль; Салливан, Джек (ред.). «Филогенетические смеси на одном дереве могут имитировать дерево с другой топологией». Систематическая биология. 56 (5): 767–775. Дои:10.1080/10635150701627304. ISSN  1076-836X.
10. Уодделл, Питер Дж; Стил, Массачусетс (декабрь 1997 г.). «Общие обратимые во времени расстояния с неравными скоростями между сайтами: смешивание Γ и обратных гауссовских распределений с инвариантными сайтами». Молекулярная филогенетика и эволюция. 8 (3): 398–414. Дои:10.1006 / mpev.1997.0452.
11. Steel, M. A .; Hendy, M.D .; Пенни, Д. (1993-12-01). «Экономия может быть последовательной!». Систематическая биология. 42 (4): 581–587. Дои:10.1093 / sysbio / 42.4.581. ISSN  1063-5157.
12. Hendy, M.D .; Penny, D .; Стил, М.А. (1994-04-12). «Дискретный анализ Фурье для эволюционных деревьев». Труды Национальной академии наук. 91 (8): 3339–3343. Дои:10.1073 / пнас.91.8.3339. ISSN  0027-8424. ЧВК  43572. PMID  8159749.
13. Миямото, М. М .; Koop, B. F .; Slightom, J. L .; Goodman, M .; Теннант, М. Р. (1988-10-01). «Молекулярная систематика высших приматов: генеалогические отношения и классификация». Труды Национальной академии наук. 85 (20): 7627–7631. Дои:10.1073 / pnas.85.20.7627. ISSN  0027-8424. ЧВК  282245. PMID  3174657.