Преобразование Адамара (также известное как преобразование Уолша-Адамара , преобразование Адамара-Радемахера-Уолша , преобразование Уолша или преобразование Уолша-Фурье ) является примером обобщенного класса преобразований Фурье . Он выполняет ортогональную , симметричную , инволютивную , линейную операцию над 2 m действительными числами (или комплексными , или гиперкомплексными числами , хотя сами матрицы Адамара чисто вещественные).
Преобразование Адамара можно рассматривать как построенное на основе дискретных преобразований Фурье (ДПФ) размера 2 и фактически эквивалентно многомерному ДПФ размера 2 × 2 × ⋯ × 2 × 2 . [2] Он разлагает произвольный входной вектор в суперпозицию функций Уолша .
Преобразование названо в честь французского математика Жака Адамара ( французский: [adamaʁ] ), немецко-американского математика Ганса Радемахера и американского математика Джозефа Л. Уолша .
Преобразование Адамара H m представляет собой матрицу размером 2 м × 2 м , матрицу Адамара (масштабированную с помощью коэффициента нормализации), которая преобразует 2 м действительных чисел x n в 2 м действительных чисел X k . Преобразование Адамара можно определить двумя способами: рекурсивно или с использованием двоичного ( по основанию -2) представления индексов n и k .
Рекурсивно мы определяем преобразование Адамара H 0 1 × 1 тождеством H 0 = 1, а затем определяем H m для m > 0 следующим образом:
Для m > 1 мы также можем определить H m следующим образом:
Эквивалентно, мы можем определить матрицу Адамара по ее ( k , n )-й записи, написав
где k j и n j — битовые элементы (0 или 1) k и n соответственно. Обратите внимание, что для элемента в верхнем левом углу мы определяем: . В этом случае мы имеем:
Это и есть многомерное ДПФ, нормализованное как унитарное , если входные и выходные данные рассматривать как многомерные массивы, индексированные n j и k j соответственно.
Ниже приведены некоторые примеры матриц Адамара.
H 1 — это именно ДПФ размера 2. Его также можно рассматривать как преобразование Фурье на двухэлементной аддитивной группе Z /(2).
Строки матриц Адамара являются функциями Уолша .
Согласно приведенному выше определению матрицы H , здесь мы полагаем H = H [ m , n ]
При преобразовании Уолша в матрице появятся только 1 и -1. Числа 1 и -1 являются действительными числами, поэтому нет необходимости выполнять вычисление комплексных чисел .
ДПФ требует иррационального умножения, а преобразование Адамара — нет. Даже рациональное умножение не требуется, поскольку достаточно просто поменять знак.
В матрице преобразования Уолша все записи в первой строке (и столбце) равны 1.
Дискретное преобразование Фурье:
В дискретном преобразовании Фурье, когда m равно нулю (среднее значение первой строки), результат ДПФ также равен 1. Во второй строке, хотя она и отличается от первой строки, мы можем наблюдать особенность матрицы, заключающуюся в том, что сигнал в первая необработанная матрица является низкочастотной, и она будет увеличивать частоту во второй строке, увеличивая частоту до последней строки.
Если мы вычислим пересечение нуля:
Первая строка = 0 пересечений нуля.Вторая строка = 1 пересечение нуля.Третий ряд = 2 пересечения нуля ⋮Восемь рядов = 7 пересечений нуля.
Преобразование Адамара фактически эквивалентно многомерному ДПФ размером 2 × 2 × ⋯ × 2 × 2 . [2]
Другой подход состоит в том, чтобы рассматривать преобразование Адамара как преобразование Фурье булевой группы . [3] [4] Используя преобразование Фурье на конечных (абелевых) группах , преобразование Фурье функции — это функция, определяемая формулой
Это преобразование Адамара , рассматривающее входные данные как логические строки.
С точки зрения приведенной выше формулировки, где преобразование Адамара умножает вектор комплексных чисел слева на матрицу Адамара, эквивалентность проявляется, если взять в качестве входных данных битовую строку, соответствующую индексу элемента , и вывести соответствующую элемент .
Сравните это с обычным дискретным преобразованием Фурье , которое при применении к вектору комплексных чисел вместо этого использует символы циклической группы .
В классической области преобразование Адамара можно вычислить с помощью операций ( ), используя алгоритм быстрого преобразования Адамара .
В квантовой области преобразование Адамара можно вычислить во времени, поскольку оно представляет собой квантовый логический элемент , который можно распараллелить .
Преобразование Адамара широко используется в квантовых вычислениях . Преобразование Адамара 2 × 2 — это квантовый логический вентиль , известный как вентиль Адамара, и параллельное применение вентиля Адамара к каждому кубиту регистра -кубита эквивалентно преобразованию Адамара .
В квантовых вычислениях вентиль Адамара представляет собой вращение одного кубита , отображающее состояния базиса кубита и в два состояния суперпозиции с равным весом состояний вычислительного базиса и . Обычно фазы выбираются так, чтобы
в обозначениях Дирака . Это соответствует матрице преобразования
Одно применение вентиля Адамара к кубиту 0 или 1 создаст квантовое состояние, которое, если его наблюдать, будет 0 или 1 с равной вероятностью (как видно из первых двух операций). Это в точности похоже на подбрасывание честной монеты в стандартной вероятностной модели вычислений . Однако если вентиль Адамара применяется дважды подряд (что фактически и происходит в последних двух операциях), то конечное состояние всегда будет таким же, как и начальное.
Вычисление квантового преобразования Адамара — это просто применение вентиля Адамара к каждому кубиту индивидуально из-за тензорной структуры произведения преобразования Адамара. Этот простой результат означает, что квантовое преобразование Адамара требует операций по сравнению с классическим случаем операций.
Многие квантовые алгоритмы используют преобразование Адамара в качестве начального шага, поскольку оно отображает m кубитов, инициализированных с, в суперпозицию всех 2 m ортогональных состояний в базисе с одинаковым весом. Например, это используется в алгоритме Дойча-Йожсы , алгоритме Саймона , алгоритме Бернштейна-Вазирани и в алгоритме Гровера . Обратите внимание, что алгоритм Шора использует как исходное преобразование Адамара, так и квантовое преобразование Фурье , которые оба являются типами преобразований Фурье на конечных группах ; первый включен и второй включен .
Преобразование Адамара можно использовать для оценки филогенетических деревьев на основе молекулярных данных. [5] [6] [7] Филогенетика — это раздел эволюционной биологии , направленный на понимание взаимоотношений между организмами. Преобразование Адамара, примененное к вектору (или матрице) частот шаблонов сайтов, полученному в результате выравнивания множественных последовательностей ДНК , может использоваться для создания другого вектора, несущего информацию о топологии дерева. Обратимая природа филогенетического преобразования Адамара также позволяет рассчитывать вероятности сайтов на основе вектора топологии дерева, что позволяет использовать преобразование Адамара для оценки максимального правдоподобия филогенетических деревьев. Однако последнее применение менее полезно, чем преобразование вектора шаблона сайта в вектор дерева, поскольку существуют другие способы расчета вероятности сайта [8] [9] , которые гораздо более эффективны. Однако обратимая природа филогенетического преобразования Адамара действительно предоставляет элегантный инструмент для математической филогенетики. [10] [11]
Механика филогенетического преобразования Адамара включает вычисление вектора , который предоставляет информацию о топологии и длине ветвей дерева с использованием вектора или матрицы шаблона сайта .
Обратимый характер этого уравнения позволяет рассчитать ожидаемый вектор (или матрицу) шаблона сайта следующим образом:
Мы можем использовать модель замены двух состояний Кавендера-Фарриса- Неймана (CFN) для ДНК, кодируя нуклеотиды как бинарные символы ( пурины A и G кодируются как R, а пиримидины C и T кодируются как Y). Это позволяет кодировать множественное выравнивание последовательностей как вектор шаблона сайта , который можно преобразовать в вектор дерева , как показано в следующем примере:
В примере, показанном в этой таблице, используется упрощенная схема из трех уравнений, и это дерево из четырех таксонов, которое можно записать как ((A,B),(C,D)); в формате Ньюика . Шаблоны сайтов записываются в порядке ABCD. Это конкретное дерево имеет две длинные концевые ветви (0,2 трансверсионных замен на сайт), две короткие концевые ветви (0,025 трансверсионных замен на сайт) и короткую внутреннюю ветвь (0,025 трансверсионных замен на сайт); таким образом, это будет записано как ((A:0.025,B:0.2):0.025,(C:0.025,D:0.2)); в формате Ньюика. Это дерево будет демонстрировать привлекательность длинных ветвей , если данные анализируются с использованием критерия максимальной экономии (при условии, что анализируемая последовательность достаточно длинна, чтобы наблюдаемые частоты шаблонов сайтов были близки к ожидаемым частотам, показанным в столбце). Привлекательность длинных ветвей отражает тот факт, что ожидаемое количество шаблонов сайтов с индексом 6 -- которые поддерживают дерево ((A,C),(B,D)); -- превысить ожидаемое количество шаблонов сайтов, поддерживающих истинное дерево (индекс 4). Очевидно, что обратимая природа филогенетического преобразования Адамара означает, что вектор дерева означает, что вектор дерева соответствует правильному дереву. Таким образом, анализ экономии после преобразования является статистически последовательным [13] , как и стандартный анализ максимального правдоподобия с использованием правильной модели (в данном случае модели CFN).
Обратите внимание, что шаблон сайтов с номером 0 соответствует сайтам, которые не изменились (после кодирования нуклеотидов как пурины или пиримидины). Индексы со звездочками (3, 5 и 6) являются «экономно-информативными». Остальные индексы представляют собой закономерности участков, в которых один таксон отличается от трех других таксонов (поэтому они эквивалентны длинам конечных ветвей в стандартном филогенетическом дереве максимального правдоподобия).
Если кто-то желает использовать нуклеотидные данные без перекодировки как R и Y (и, в конечном итоге, как 0 и 1), можно закодировать шаблоны сайтов в виде матрицы. Если мы рассмотрим дерево из четырех таксонов, то всего будет 256 шаблонов сайтов (четыре нуклеотида в 4-й степени). Однако симметрия трехпараметрической модели Кимуры (или K81) позволяет сократить 256 возможных паттернов сайтов ДНК до 64 паттернов, что дает возможность кодировать нуклеотидные данные для четырехтаксонного дерева в виде матрицы 8×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 . В приложениях сжатия видео он обычно используется в виде суммы абсолютных преобразованных разностей . Это также важная часть значительного количества алгоритмов квантовых вычислений. Преобразование Адамара также применяется в экспериментальных методах, таких как ЯМР , масс-спектрометрия и кристаллография . Он дополнительно используется в некоторых версиях локально-зависимого хеширования для получения псевдослучайных поворотов матрицы.
{{cite journal}}
: Требуется цитировать журнал |journal=
( помощь )