アダマールは変容させる

アダマール変換（ウォルシュ・アダマール変換、アダマール・ラデマッハー・ウォルシュ変換、ウォルシュ変換、またはウォルシュ・フーリエ変換とも呼ばれる）は、フーリエ変換の一般化されたクラスの一例です。これは、 2 ^{m 個}の数値のタプルに対して、直交、対称、対合、線形演算を実行します。

アダマール変換は、サイズ2の離散フーリエ変換（DFT）から構築されていると見なすことができ、実際にはサイズ2×2×⋯×2×2の多次元DFTと同等である。^{[ 2 ]}これは任意の入力ベクトルをウォルシュ関数 の重ね合わせに分解する。

この変換は、フランスの数学者ジャック・アダマール（フランス語: [ adamaʁ ]）、ドイツ系アメリカ人の数学者ハンス・ラデマッハー、アメリカの数学者ジョセフ・L・ウォルシュにちなんで名付けられました。

アダマール変換H _mは、2 ^m  ×  2 ^m行列、つまり正規化係数でスケーリングされたアダマール行列であり、2 ^{m 個の}実数x _{n を}2 ^{m 個}の実数X _kに変換します。アダマール変換は、再帰的に定義するか、インデックスnとkのバイナリ(基数-2) 表現を使用するかの 2 つの方法で定義できます。

 再帰的に、1 ×  1 アダマール変換H _0を恒等式H ₀ = 1で定義し、次にm > 0 に対してH _{m を次のように定義します。}  $${\displaystyle H_{m}={\frac {1}{2^{m/2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}}$$ここで、 2m ^/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}+\dots +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}+\dots +n_{1}2+n_{0}\end{aligned}}}$$

ここで、k _jとn _jはそれぞれkとnのビット要素 (0 または 1) です。左上隅の要素については、次のように定義します。${\displaystyle k=n=0}$この場合、以下のようになります。 $${\displaystyle (H_{m})_{k,n}={\frac {1}{2^{m/2}}}(-1)^{\sum _{j}k_{j}n_{j}}}$$

これはまさに多次元${\textstyle 2\times 2\times \cdots \times 2\times 2}$入力と出力がそれぞれn _jとk _jでインデックス付けされた多次元配列とみなされる場合、ユニタリに正規化された DFT 。

以下に、アダマール行列の例をいくつか示す。 $${\displaystyle {\begin{aligned}H_{0}&=+{\begin{pmatrix}1\end{pmatrix}}\\[5pt]H_{1}&={\frac {1}{\sqrt {2}}}\left({\begin{array}{rr}1&1\\1&-1\end{array}}\right)\\[5pt]H_{2}&={\frac {1}{2}}\left({\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{array}}\right)\\[5pt]H_{3}&={\frac {1}{2^{3/2}}}\left({\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}}\right)\\[5pt](H_{n})_{i,j}&={\frac {1}{2^{n/2}}}(-1)^{i\cdot j}\end{aligned}}}$$ どこ${\displaystyle i\cdot j}$は、数値 i と j のバイナリ表現のビットごとのドット積です。たとえば、${\textstyle n\;\geq \;2}$、 それから$${\displaystyle (H_{n})_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1}$$上記に同意する（全体の定数は無視する）。行列の最初の行、最初の列の要素は、で表されます。${\textstyle (H_{n})_{0,0}}$。

H ₁はまさにサイズ 2 の DFT です。これはZ /(2)の2 要素加法群に対するフーリエ変換とみなすこともできます。

アダマール行列の行はウォルシュ関数である。

アダマール変換は、2 × 2 × ⋯ × 2 × 2サイズの多次元 DFT と同等である。^{[ 2 ]}

正式には、アダマール変換はブール群上のフーリエ変換である。${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$[ ^{3 ] [ 4 ]}有限（アーベル）群に対するフーリエ変換を用いると^、 関数のフーリエ変換は${\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} }$したがって、DFTはアダマール変換よりもはるかに複雑な演算を必要とします。DFTとは異なり、アダマール変換は純粋に実数であり、実際には乗算は必要なく、符号反転のみが必要です。

古典領域では、アダマール変換は次のように計算できます。${\displaystyle n\log n}$操作（${\displaystyle n=2^{m}}$)高速アダマール変換アルゴリズムを使用する。

量子領域では、アダマール変換は次のように計算できます。${\displaystyle O(1)}$時間、これは並列化可能な量子論理ゲートであるためです。

アダマール変換は量子コンピューティングで広く用いられている。2  ×  2アダマール変換${\displaystyle H_{1}}$は、アダマールゲートとして知られる量子論理ゲートであり、各量子ビットにアダマールゲートを適用すると、${\displaystyle n}$並列の量子ビットレジスタはアダマール変換に相当する${\displaystyle H_{n}}$。

アダマール変換は、分子データから系統樹を推定するために使用できます。^{[ 8 ] [ 9 ] [ 10 ]}原理的には、アダマール変換はさまざまな配列進化モデル に適用できますが、最も興味深いケースは核酸（NA）のデータを使用するケースです。^{[ 8 ] [ 11 ]}

形式的には、4 つの可能な鎖核酸塩基を、それ自身に作用するクライン 4 グループV の要素とみなします。一方のC ₂軸は遷移に対応し、もう一方は転位に対応します。長さkの NA 配列はV ^kの要素であり、これらの長さk の配列への特定のインデックスはサイトと呼ばれます。系統樹Tは、あるrを根とする木であり、各点が NA 配列と識別されています。^{[ 12 ]}

生物学的応用では、 Tの各エッジの突然変異率を指定し、その結果としてTを観測する確率を計算したい。理想的には、このプロセスは容易に可逆であるべきであり、最適化アルゴリズムによって、観測された DNA 配列を最大尤度で生成する (木、突然変異率) のペアを見つけることができる。実際、これは次のようにアダマール変換を使用して行うことができる。^{[ 12 ] [ 13 ]}

I をT \{ r }の冪集合とし、次のI ²インデックス付きベクトルxを考える。各サイトjはσ ₁ ∈ Iを決定する。σ 1 ∈ I は、サイトjにおいてrに対して遷移を持つ点の集合である。同様に、転位は各サイトに対して別のσ ₂ ∈ Iを決定する。すると、x _{( σ 1 , σ 2 )}は( σ ₁ , σ ₂ )を決定するサイトの割合 ( {1,..., k }のうち) となる。^{[ 12 ]}

線形演算子H :ℝ ^{I 2} → ℝ ^{I 2}は、 ( σ , τ )番目の係数( − 1) ^{| σ ₁ ∩ τ ₁ |+| σ ₂ ∩ τ ₂ |}を持つアダマール行列です。実際、 I がある順序で列挙されている場合 、アダマール変換を定義します。 ^{[ 9 ]}

γ = H ^{− 1} log ^{⊗ I 2} ( Hx )

ここで、⊗ I ^{2 は}、対数がベクトルの各成分に作用することを示しています。すると、γは、観測された確率分布x を生成するために必要な突然変異率mとほぼ同じになります。^{[ 12 ] [ 14 ]}

4種類の核酸すべてを区別した完全な木村モデルでは、各エッジに3つの自由パラメータがあります。これらの値をγの対応するエントリに変換するには、 3 × 3行列で別の対数を共役する必要があります。^{[ 12 ]}

配列がRYコード化されている場合、関係ははるかに単純になります。この場合、xとγはI （ I ²ではなく）でインデックス付けされ、mも同様です。偶数サイズのσ ∈ Iの場合、E（σ）= σとします。奇数サイズのσ ∈ Iの場合、E（σ）= σ ⊔ {r}とします。そして、m _σをσをTの残りの部分から切り離すエッジ上の突然変異率とします。（mは、復帰突然変異の確率を含むため、厳密には測定量ではありません。これは、観察された形質変化の確率と関連しています。

m _σ = − ⁠ 1 / 2 ⁠ log(1-2 p _σ )

ここでpは観測された確率である。）するとγ = mとなる。^{[ 9 ]}

この手法は、異なる部位が異なる速度で変異する場合にも一般化できる。^{[ 15 ]}

いずれの場合も、ツリーを決定する時間計算量はアダマール変換によって支配され、 O(| T |2 ^{| T |} )のステップを要します。^{[ 16 ]}ただし、アルゴリズムは、 T のサブセットから構築されたより小さなツリーを組み合わせることによってツリーを再構築できます。^{[ 17 ]}

アダマール変換は、データ暗号化だけでなく、JPEG XRやMPEG-4 AVCなどの多くの信号処理およびデータ圧縮アルゴリズムにも使用されています。ビデオ圧縮アプリケーションでは、通常、変換された差分の絶対値の和の形で使用されます。また、量子コンピューティングにおける多数のアルゴリズムの重要な部分でもあります。アダマール変換は、NMR、質量分析、結晶学などの実験技術にも応用されています。さらに、擬似乱数行列回転を得るために、局所性敏感ハッシュのいくつかのバージョンでも使用されています。

• 高速ウォルシュ・アダマール変換
• 擬似アダマール変換
• ハール変換
• 一般化された分配法則

• リッター、テリー（1996年8月）。「ウォルシュ＝アダマール変換：文献調査」。
• Akansu, Ali N. ; Poluri, R. (2007年7月) 「直接シーケンスCDMA通信のためのウォルシュ型非線形位相直交符号」(PDF) . IEEE Transactions on Signal Processing . 55 (7): 3800–6 . Bibcode : 2007ITSP...55.3800A . doi : 10.1109/TSP.2007.894229 . S2CID 6830633 . 
• Pan, Jeng-shyang離散フラクショナル アダマール変換を使用したデータ暗号化手法(2009 年 5 月 28 日)
• ラホヴィッツ博士、パヴェル。「ウォルシュ・アダマール変換と金融収益系列のランダム性検定」（2015年4月7日）
• Beddard, Godfrey; Yorke, Briony A. (2011年1月) 「アダマール変換を用いたポンププローブ分光法」(PDF) 。 2014年10月18日にオリジナル(PDF)からアーカイブ済み。 2012年4月28日取得。
• Yorke, Briony A.; Beddard, Godfrey; Owen, Robin L.; Pearson, Arwen R. (2014年9月) 「アダマール変換を用いた時間分解結晶学」 Nature Methods . 11 ( 11): 1131– 1134. doi : 10.1038/nmeth.3139 . PMC 4216935. PMID 25282611 .