Перетворення Уолша

Немає цієї сторінки; ймовірно, її ще не перевіряли на відповідність правилам проекту.

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

Перетворення Адамара
Підтримується Вікіпроєктом

Добуток булевої функції на матрицю Уолша є спектром Уолша:
(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. Воно розкладає довільний вхідний вектор на суперпозицію функцій Уолша.

Перетворення названо на честь французького математика Жака Адамара, німецько-американського математика (інші мови) та американського математика (інші мови).

Визначення

Перетворення Адамара H_m це 2^m × 2^m матриця, матриця Адамара (масштабована коефіцієнтом нормалізації), яка перетворює 2^m дійсних чисел x_n у 2^m дійсних чисел X_k. Перетворення Адамара може бути визначене двома способами: рекурсивно, або за допомогою представлення у двійковій системі числення індексів n і k.

Рекурсивно перетворення Адамара 1 × 1 визначається як H₀ за ідентичністю H₀ = 1, і після визначається H_m для m > 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}}$

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

Еквівалентно, матриця Адамара може бути визначена за її (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}+\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 та n_j — це двійкові цифри (0 та 1) k і n відповідно. Зверніть увагу, що для елемента у верхньому лівому куті визначається: ${\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}$ ДПФ нормується щоб бути унітарним, якщо входи та виходи розглядаються як багатовимірні масиви, проіндексовані n_j and 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}}$.

H₁ є саме ДПФ розміру 2. Це також можна розглядати як перетворення Фур'є над двоелементною адитивною групою Z/(2).

Рядки матриць Адамара — це функції Уолша.

Обчислювальна складність

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

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

Застосування у квантових обчисленнях

У квантовій інформатиці перетворення Адамара, яке в цьому контексті частіше називають вентилем Адамара (див. Квантовий вентиль), є однокубітним обертанням, відображенням станів кубіта ${\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 }$ and ${\displaystyle \left|{\boldsymbol {-}}\right\rangle }$ відповідно, і разом складають полярний базис у квантових обчисленнях.

Багато квантових алгоритмів використовують перетворення Адамара як початковий крок, оскільки воно відображає m кубітів, ініціалізованих за допомогою ${\displaystyle |0\rangle }$ у суперпозицію всіх 2^m ортогональних станів у ${\displaystyle |0\rangle ,|1\rangle }$ рівноважному базисі.

Примітно, що обчислення квантового перетворення Адамара — це просто застосування вентиля Адамара до кожного кубіта окремо через тензорну структуру добутку у перетворенні Адамара. Цей простий результат означає, що квантове перетворення Адамара вимагає log nоперацій порівняно з класичним випадком у n log n операцій.

Операції з вентилем Адамара

${\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 з однаковою ймовірністю (як це видно на перших двох операціях). Це точно як підкидання справедливої монети у стандартній імовірнісній моделі обчислення. Однак, якщо вентиль Адамара застосовується двічі поспіль (як це робиться в останніх двох операціях), то кінцевий стан завжди збігається з початковим.

Застосування у молекулярній філогенетиці (еволюційній біології)

Перетворення Адамара може бути використано для оцінки філогенетичних дерев за молекулярними даними. Філогенетика — це галузь еволюційної біології, орієнтоване на розуміння взаємозв'язків між організмами. Перетворення Адамара, застосоване до вектора (або матриці) частот шаблонів сайтів, отриманих з ДНК множинним вирівнюванням послідовностей, може бути використано для створення іншого вектора, який несе інформацію про топологію дерева. Оборотна природа філогенетичного перетворення Адамара також дозволяє обчислювати ймовірності ділянок за вектором дерева топології, дозволяючи використовувати перетворення Адамара для оцінки максимальної правдоподібності філогенетичних дерев. Однак останнє застосування менш корисне, ніж перетворення з вектора шаблонів сайту на вектор дерева, оскільки існують інші способи обчислення ймовірності сайту які набагато ефективніші. Однак оборотний характер філогенетичного перетворення Адамара справді забезпечує елегантний інструмент для математичної філогенетики.

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

Індекс	Двійковий шаблон	Шаблони вирівнювання	${\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	RYRR і YRYY	0.2	-0.45	0.6376	0.1283
5*	0101	RYRY і YRYR	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)); у ^[en]. Шаблони сайтів написані в порядку ABCD. Це конкретне дерево має дві довгі кінцеві гілки (0,2 ^[en] на сайт), дві короткі кінцеві гілки (0,025 трансверсії на сайт) і коротку внутрішню гілку (0,025 заміни трансверсії на сайт); таким чином, це буде записано як ((A: 0,025, B: 0,2): 0,025, (C: 0,025, D: 0,2)); у форматі newick. У цьому дереві буде показано ^[en], якщо дані аналізуються за допомогою ^[en] (припускаючи, що проаналізована послідовність досить довга, щоб частоти спостережуваних картин сайту були близькі до очікувані частоти, показаної в стовпці ${\displaystyle s(T)=H^{-1}\rho }$). Тривале притягання гілок відображає той факт, що очікувана кількість шаблонів сайтів з індексом 6 — які підтримують дерево ((A, C), (B, D)); — перевищує очікувану кількість шаблонів сайтів, які підтримують справжнє дерево (індекс 4). Очевидно, що обернена природа філогенетичного перетворення Адамара означає, що вектор дерева ${\displaystyle \gamma (T)}$ відповідає правильному дереву. Тому аналіз ощадливості після перетворення є статистично узгодженим, як це було б стандартним аналізом максимальної правдоподібності з використанням правильної моделі (у цьому випадку моделі CFN).

Зверніть увагу, що шаблон сайту з 0 відповідає сайтам, які не змінилися (після кодування нуклеотидів як пуринів або піримідинів). Індекси із зірочками (3, 5 та 6) є «інформаційними», і решта індексів представляють схеми ділянок, де один таксон відрізняється від інших трьох таксонів (тому вони еквівалентні довжинам кінцевих гілок у стандартному філогенетичному дереві з максимальною правдоподібністю).

Якщо хтось хоче використовувати дані нуклеотидів без перекодування як R і Y (і, зрештою, як 0 і 1), можна закодувати шаблони сайтів як матрицю. Якщо ми розглянемо дерево з чотирма таксонами, то загалом існує 256 візерунків (чотири нуклеотиди у 4-й степені). Однак симетрії ^[en] дозволяють нам звести 256 можливих моделей ділянок ДНК до 64 шаблонів, що робить можливим кодування нуклеотидних даних для чотири-таксонного дерева як матриці 8х8 способом, аналогічним вектору з 8 елементів, що використовувались вище для схеми перетворення (RY). Це досягається шляхом перекодування даних за допомогою 4-групи Клейна:

Кодування 4-групи Клейна для філогенетичного перетворення Адамара

Нуклеотид 1	Нуклеотид 2	Нуклеотид 3	Нуклеотид 4
A (0,0)	G (1,0)	C (0,1)	T (1,1)
C (0,0)	T (1,0)	A (0,1)	G (1,1)
G (0,0)	A (1,0)	T (0,1)	C (1,1)
T (0,0)	C (1,0)	G (0,1)	A (1,1)

Як і у даних RY, шаблони сайтів індексуються відносно бази в довільно обраному першому таксоні з базами в наступних таксонах, кодованих щодо цієї першої бази. Таким чином, перший таксон отримує бітову пару (0,0). Використовуючи ці бітові пари, можна створити два вектори, подібні до RY-векторів, а потім заповнити матрицю, використовуючи ці вектори. Це можна проілюструвати на прикладі Hendy et al. (1994), який заснований на множинному вирівнюванні послідовностей чотирьох псевдогенів гемоглобіну приматів:

Приклад вирівнювання закодованої послідовності (з Hendy et al. 1994) (значення з підрахунку 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 відповідає перехідним відмінностям, які накопичуються швидше, ніж відмінності трансверсії практично у всіх порівняннях геномних областей (і, безумовно, накопичуються швидше в псевдогенах гемоглобіну, що використовуються для цього працюючого прикладу). Якщо ми розглянемо шаблон сайту 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. У додатках стиснення відео він зазвичай використовується у формі суми абсолютних трансформованих різниць. Це також найважливіша частина алгоритму Грувера та алгоритму Шора в квантових обчисленнях. Перетворення Адамара також застосовується в експериментальних методах, таких як ЯМР, мас-спектрометрія та кристалографія. Воно додатково використовується в деяких версіях локально-чутливого гешування для отримання псевдовипадкових обертань матриці.

Див. також

• ^[en]
• (Гаарів вейвлет#Гаарове перетворення)
• ^[en]

Посилання

• Ritter, Terry (August 1996). Walsh-Hadamard Transforms: A Literature Survey.
• Akansu, A.N.; Poluri, R. (July 2007). Walsh-Like Nonlinear Phase Orthogonal Codes for Direct Sequence CDMA Communications (PDF). IEEE Transactions on Signal Processing. 55 (7): 3800—6. doi:10.1109/TSP.2007.894229.
• Pan, Jeng-shyang Data Encryption Method Using Discrete Fractional Hadamard Transformation (May 28, 2009)
• Lachowicz, Dr. Pawel. Walsh–Hadamard Transform and Tests for Randomness of Financial Return-Series (April 7, 2015)
• Beddard, Godfrey; Yorke, Briony A. (January 2011). Pump-probe Spectroscopy using Hadamard Transforms (PDF).
• Yorke, Briony A.; Beddard, Godfrey; Owen, Robin L.; Pearson, Arwen R. (September 2014). Time-resolved crystallography using the Hadamard transform. Nature Methods. 11 (11): 1131—1134. doi:10.1038/nmeth.3139. PMC 4216935. PMID 25282611.

Примітки

1. Compare Figure 1 in Townsend, W. J.; Thornton, M. A. Walsh Spectrum Computations Using Cayley Graphs. CiteSeerX 10.1.1.74.8029.
2. Kunz, H.O. (1979). On the Equivalence Between One-Dimensional Discrete Walsh-Hadamard and Multidimensional Discrete Fourier Transforms. IEEE Transactions on Computers. 28 (3): 267—8. doi:10.1109/TC.1979.1675334.
3. Hendy, Michael D.; Penny, David (December 1989). A Framework for the Quantitative Study of Evolutionary Trees. Systematic Zoology. 38 (4): 297. doi:10.2307/2992396.
4. Hendy, Michael D.; Penny, David (January 1993). Spectral analysis of phylogenetic data. Journal of Classification (англ.). 10 (1): 5—24. doi:10.1007/BF02638451. ISSN 0176-4268.
5. Székely, L. A., Erdős, P. L., Steel, M. A., & Penny, D. (1993). A Fourier inversion formula for evolutionary trees. Applied mathematics letters, 6(2), 13-16.
6. Felsenstein, Joseph (November 1981). Evolutionary trees from DNA sequences: A maximum likelihood approach. Journal of Molecular Evolution (англ.). 17 (6): 368—376. doi:10.1007/BF01734359. ISSN 0022-2844.
7. Stamatakis, Alexandros (2019), Warnow, Tandy (ред.), A Review of Approaches for Optimizing Phylogenetic Likelihood Calculations, Bioinformatics and Phylogenetics (англ.), Cham: Springer International Publishing, т. 29, с. 1—19, doi:10.1007/978-3-030-10837-3_1, ISBN , процитовано 10 жовтня 2020
8. Chor, Benny; Hendy, Michael D.; Holland, Barbara R.; Penny, David (1 жовтня 2000). Multiple Maxima of Likelihood in Phylogenetic Trees: An Analytic Approach. Molecular Biology and Evolution (англ.). 17 (10): 1529—1541. doi:10.1093/oxfordjournals.molbev.a026252. ISSN 1537-1719.
9. Matsen, Frederick A.; Steel, Mike (1 жовтня 2007). Ané, Cécile; Sullivan, Jack (ред.). Phylogenetic Mixtures on a Single Tree Can Mimic a Tree of Another Topology. Systematic Biology (англ.). 56 (5): 767—775. doi:10.1080/10635150701627304. ISSN 1076-836X.
10. Waddell, Peter J; Steel, M.A (December 1997). General Time-Reversible Distances with Unequal Rates across Sites: Mixing Γ and Inverse Gaussian Distributions with Invariant Sites. Molecular Phylogenetics and Evolution (англ.). 8 (3): 398—414. doi:10.1006/mpev.1997.0452.
11. Steel, M. A.; Hendy, M. D.; Penny, D. (1 грудня 1993). Parsimony Can Be Consistent!. Systematic Biology (англ.). 42 (4): 581—587. doi:10.1093/sysbio/42.4.581. ISSN 1063-5157.
12. Hendy, M. D.; Penny, D.; Steel, M. A. (12 квітня 1994). A discrete Fourier analysis for evolutionary trees. Proceedings of the National Academy of Sciences (англ.). 91 (8): 3339—3343. doi:10.1073/pnas.91.8.3339. ISSN 0027-8424. PMC 43572. PMID 8159749.
13. Miyamoto, M. M.; Koop, B. F.; Slightom, J. L.; Goodman, M.; Tennant, M. R. (1 жовтня 1988). Molecular systematics of higher primates: genealogical relations and classification. Proceedings of the National Academy of Sciences (англ.). 85 (20): 7627—7631. doi:10.1073/pnas.85.20.7627. ISSN 0027-8424. PMC 282245. PMID 3174657.