Перетворення Адамара

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Добуток булевої функції на матрицю Уолша є спектром Уолша:[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).
Оригінальна функція може бути виражена у термінах її спектра Уолша через арифметичний поліном.

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

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

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

Визначення[ред. | ред. код]

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

Рекурсивно перетворення Адамара 1 × 1 визначається як H0 за ідентичністю H0 = 1, і після визначається Hm для m > 0 як:

де 1/2 — це нормалізація, яку іноді опускають.

Для m > 1 можна також визначити Hm як:

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

Еквівалентно, матриця Адамара може бути визначена за її (kn)-ми елементами

де kj та nj — це двійкові цифри (0 та 1) k і n відповідно. Зверніть увагу, що для елемента у верхньому лівому куті визначається: . У цьому випадку ми маємо:

Це саме багатовимірне ДПФ нормується щоб бути унітарним, якщо входи та виходи розглядаються як багатовимірні масиви, проіндексовані nj and kj, відповідно.

Далі наводяться деякі приклади матриць Адамара.

де  — побітовий добуток двійкових подань чисел i та j. Наприклад, якщо , то , погоджується із вищесказаним (ігноруючи загальну константу). Зверніть увагу, що перший рядок, перший елемент стовпця матриці позначається .

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

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

Обчислювальна складність[ред. | ред. код]

У класичній моделі обчислень перетворення Адамара можна обчислити за операцій (), використовуючи алгоритм швидкого перетворення Адамара[en].

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

Застосування у квантових обчисленнях[ред. | ред. код]

У квантовій інформатиці перетворення Адамара, яке в цьому контексті частіше називають вентилем Адамара (див. Квантовий вентиль), є однокубітним обертанням, відображенням станів кубіта і у суперпозицію станів з однаковою вагою обчислювальних базисів і . Зазвичай фази вибираються таким чином, щоб отримати:

у нотації Дірака. Це відповідає матриці перетворень

у базисі також відомому як обчислювальний базис. Стани і відомі як and відповідно, і разом складають полярний базис у квантових обчисленнях.

Багато квантових алгоритмів використовують перетворення Адамара як початковий крок, оскільки воно відображає m кубітів, ініціалізованих за допомогою у суперпозицію всіх 2m ортогональних станів у рівноважному базисі.

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

Операції з вентилем Адамара[ред. | ред. код]

Одне застосування вентиля Адамара до кубіта 0 або 1 створить квантовий стан, який, якщо його спостерігатимуть, буде рівним 0 або 1 з однаковою ймовірністю (як це видно на перших двох операціях). Це точно як підкидання справедливої монети у стандартній імовірнісній моделі обчислення[en]. Однак, якщо вентиль Адамара застосовується двічі поспіль (як це робиться в останніх двох операціях), то кінцевий стан завжди збігається з початковим.

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

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

Механіка філогенетичного перетворення Адамара включає обчислення вектора , що надає інформацію про топологію та довжини гілок для дерева з використанням вектора або матриці шаблонів сайту .

де  — матриця Адамара відповідного розміру. Це рівняння можна переписати як серію з трьох рівнянь для спрощення його інтерпретації:

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

Ми можемо використовувати двоступінчасту модель замін Кавендера-Фарріса-Неймана (CFN) для ДНК, кодуючи нуклеотиди як двійкові символи (пурини A і G кодуються як R, а піримідини C і T кодуються як Y). Це дає можливість кодувати множинне вирівнювання послідовностей як вектор шаблонів сайту який можна перетворити на вектор дерева , як показано на наступному прикладі:

Приклад, що показує застосування перетворення Адамара до специфічного дерева (значення для прикладу — з Waddell et al. 1997[10])
Індекс Двійковий шаблон Шаблони вирівнювання
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)); у форматі newick[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] (припускаючи, що проаналізована послідовність досить довга, щоб частоти спостережуваних картин сайту були близькі до очікувані частоти, показаної в стовпці ). Тривале притягання гілок відображає той факт, що очікувана кількість шаблонів сайтів з індексом 6 — які підтримують дерево ((A, C), (B, D)); — перевищує очікувану кількість шаблонів сайтів, які підтримують справжнє дерево (індекс 4). Очевидно, що обернена природа філогенетичного перетворення Адамара означає, що вектор дерева відповідає правильному дереву. Тому аналіз ощадливості після перетворення є статистично узгодженим,[11] як це було б стандартним аналізом максимальної вірогідності з використанням правильної моделі (у цьому випадку моделі CFN).

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

Якщо хтось хоче використовувати дані нуклеотидів без перекодування як R і Y (і, зрештою, як 0 і 1), можна закодувати шаблони сайтів як матрицю. Якщо ми розглянемо дерево з чотирма таксонами, то загалом існує 256 візерунків (чотири нуклеотиди у 4-й степені). Однак симетрії трипараметричної (або K81) моделі Кімури[en] дозволяють нам звести 256 можливих моделей ділянок ДНК до 64 шаблонів, що робить можливим кодування нуклеотидних даних для чотири-таксонного дерева як матриці 8х8[12] способом, аналогічним вектору з 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),[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. У додатках стиснення відео він зазвичай використовується у формі суми абсолютних трансформованих різниць. Це також найважливіша частина алгоритму Грувера та алгоритму Шора в квантових обчисленнях. Перетворення Адамара також застосовується в експериментальних методах, таких як ЯМР, мас-спектрометрія та кристалографія. Воно додатково використовується в деяких версіях локально-чутливого гешування для отримання псевдовипадкових обертань матриці.

Див. також[ред. | ред. код]

Посилання[ред. | ред. код]

Примітки[ред. | ред. код]

  1. Compare Figure 1 in Townsend, W. J.; Thornton, M. A. Walsh Spectrum Computations Using Cayley Graphs.  Проігноровано невідомий параметр |citeseerx= (довідка)
  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. ISSN 0176-4268. doi:10.1007/BF02638451. 
  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. ISSN 0022-2844. doi:10.1007/BF01734359. 
  7. Stamatakis, Alexandros (2019). A Review of Approaches for Optimizing Phylogenetic Likelihood Calculations. У Warnow, Tandy. Bioinformatics and Phylogenetics (англ.) (Cham: Springer International Publishing) 29: 1–19. ISBN 978-3-030-10836-6. doi:10.1007/978-3-030-10837-3_1. Процитовано 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. ISSN 1537-1719. doi:10.1093/oxfordjournals.molbev.a026252. 
  9. Matsen, Frederick A.; Steel, Mike (1 жовтня 2007). Phylogenetic Mixtures on a Single Tree Can Mimic a Tree of Another Topology. У Ané, Cécile; Sullivan, Jack. Systematic Biology (англ.) 56 (5): 767–775. ISSN 1076-836X. doi:10.1080/10635150701627304. 
  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. ISSN 1063-5157. doi:10.1093/sysbio/42.4.581. 
  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. ISSN 0027-8424. PMC 43572. PMID 8159749. doi:10.1073/pnas.91.8.3339. 
  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. ISSN 0027-8424. PMC 282245. PMID 3174657. doi:10.1073/pnas.85.20.7627.