アダマール変換: コンピューター ビジョンにおけるアダマール変換の力を明らかにする

By Fouad Sabry

アダマール変換とは

アダマール変換は、フーリエ変換の一般化されたクラスの一例です。 2m の実数に対して、直交、対称、包含、線形演算を実行します。

メリット

(I) に関する洞察と検証 次のトピック:

第 1 章: アダマール変換

第 2 章: 離散フーリエ変換

第 3 章: 高速ウォルシュ?アダマール変換

第 4 章: 量子フーリエ変換

第 5 章: 括弧表記

第 6 章: パウリ行列

第 7 章: 量子論理ゲート

第 8 章: 制御された NOT ゲート

第 9 章: パウリ行列の一般化

第 10 章: 球面基底

(II) 以下に関する一般のよくある質問に答える ハダマール変換。

(III) さまざまな分野でのアダマール変換の使用例の実例。

この本の対象者

専門家、学部生、大学院生、愛好家、趣味人、そしてあらゆる種類のアダマール変換に関する基本的な知識や情報を超えたいと考えている人。

 

 

• Language: 日本語
• Publisher: 10億人の知識があります [Japanese]
• Release date: Apr 28, 2024

Book preview

第1章:アダマール変換

アダマール変換(ウォルシュ・アダマール変換とも呼ばれる)、アダマール変換、ラーデマッハー・ウォルシュ変換、ウォルシュ変換、ウォルシュ変換、またはウォルシュ・フーリエ変換)は、より広いカテゴリに属するフーリエ変換の一種です。

これは、2mの実数(またはアダマール行列が完全に非虚数であるにもかかわらず、複素数、非常に複雑な数)に対する直交方程式、対称、インボリューティブ、線形演算を解きます。

アダマール変換は、サイズ 2 の離散フーリエ変換から構成されると考えることができます。(DFTs)であり、実際にはサイズ 2 × 2 × ⋯ × 2 × 2 の多次元 DFT と等価です。

任意の入力ベクトルを受け取り、ウォルシュ関数の重ね合わせに分解します。

この変換は、フランスの数学者ジャック・アダマール(フランス語: [adamaʁ])、ドイツとアメリカの祖先を持つ数学者ハンス・ラーデマッハー、アメリカ合衆国のジョセフ・L・ワイススタイン・ジュニアにちなんで名付けられました。

ウォルシュ。

アダマール変換 Hm は、2m × 2m の行列、アダマールの行列 (正規化係数でスケーリング) であり、2m の実数 xn を 2m の実数 Xk に変換します。

アダマール変換を定義するには、n と k を 2 進数 (基数 2) で記述する方法の 2 つがあります。

再帰的に、1 × 1 アダマール変換 H0 を恒等式 H0 = 1 で定義し、m > 0 の Hm を次のように定義します。

{\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 の場合、Hm  は次のように定義することもできます。

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

ここで \otimes 、はクロネッカー積を表します。

したがって、この標準化パラメータに加えて、アダマール行列はすべて1と0です。

あるいは、アダマール行列は、次に示すように、(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}}}

ここで、kj と nj は、それぞれ k と n のビット要素 (0 または 1) です。

注意してください、それは左上の項目についてです、私たちは定義します: k=n=0 。

ただし、ここには次のものがあります。

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

これは、入力と出力がそれぞれ nj {\textstyle 2\times 2\times \cdots \times 2\times 2} と kj でインデックス付けされた多次元配列と見なされる場合、単一の標準に準拠した多次元 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}}}

ここで i\cdot j 、 は数値 i と j の 2 進数表現のビット単位の内積です。

たとえば、 の場合、 {\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}} 。

H1 は正確にはサイズ 2 の DFT です。

2 つの要素の加法群 Z/ は、フーリエ変換を受けていると考えることができます (2)。

アダマール行列の行にはウォルシュ関数があります。

H = Hm,n] を、前述の定義を満たす行列 H とします。

{\displaystyle H[m,n]={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}

ウォルシュ変換は、エントリ 1 と 1 のみを含む行列を生成します。1と1はどちらも複素数ではない性質上、複素数の計算は不要です。

無理乗算は DFT には必要ですが、アダマール変換には必要ありません。実際、符号の変更で十分であるため、有理乗算は必要ありません。

ウォルシュ変換行列の最初の行 (および列) のすべてのエントリは 1 です。

{\displaystyle H[m,n]=\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)}

離散フーリエ変換:

{\displaystyle e^{-j2\pi mn/N}}

m が 0 (最初の行の平均) に等しい場合、離散フーリエ変換 (DFT) も 1 を生成します。1行目との違いにもかかわらず、2行目は行列の重要な特徴を明らかにしています:最初の生の行列の信号は低周波ですが、これは行が進むにつれて変化します。

ゼロクロッシング計算を使用すると、次のようになります。

最初の行 = 0 ゼロ交差

2 行目 = 1 つのゼロクロッシング

3 行目 = 2 つのゼロクロッシング

⋮

8 行 = 7 つのゼロクロッシング

アダマール変換は、実際にはサイズ 2 × 2 × ⋯ × 2 × 2 の多次元 DFT と等価です。

別のアプローチは、アダマール変換をブール群 のフーリエ変換として見ることです {\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}} 。

フーリエ変換を有限(アベル的)な群に適用すると、関数のフーリエ変換は {\displaystyle f\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} } 次式で定義される {\widehat {f}} 関数になります。

{\displaystyle {\widehat {f}}(\chi )=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a){\bar {\chi }}(a)}

ここで \chi 、 は の文字です (\Z/2\Z)^n 。

各文字は {\displaystyle \chi _{r}(a)=(-1)^{a\cdot r}} 、 {\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}} ブールドット積を使用してビット文字列がそれ自体で乗算されるいくつかの形式を持っているため、 への入力を {\widehat {f}} ( {\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}} Pontryagin 双対性)  で識別し、次のように定義できます {\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}}

これは、 への入力 f を f ブール文字列と見なす {\widehat {f}} のアダマール変換です。

アダマール変換が左側の複素数のベクトルに 2^{n} アダマール行列を v 乗算する上記の定式化では H_{n} 、 の要素のインデックスに対応するビット列を入力として取り、 f の対応する要素を出力 v することで f 等価性がわかります v 。

これを通常の離散フーリエ変換と比較すると、複素数のベクトルに適用すると v