Transformation Hadamard: Dévoilement de la puissance de la transformation Hadamard en vision par ordinateur

Par Fouad Sabry

Qu'est-ce que la transformée d'Hadamard

La transformée d'Hadamard est un exemple d'une classe généralisée de transformées de Fourier. Il effectue une opération orthogonale, symétrique, involutive et linéaire sur 2 millions de nombres réels.

Comment vous en bénéficierez

(I) Informations et validations sur le sujets suivants :

Chapitre 1 : Transformation d'Hadamard

Chapitre 2 : Transformée de Fourier discrète

Chapitre 3 : Transformation de Walsh-Hadamard rapide

Chapitre 4 : Transformée de Fourier quantique

Chapitre 5 : Notation Bra-ket

Chapitre 6 : Matrices de Pauli

Chapitre 7 : Porte logique quantique

Chapitre 8 : Porte NON contrôlée

Chapitre 9 : Généralisations des matrices de Pauli

Chapitre 10 : Base sphérique

(II) Répondre aux principales questions du public sur transformation hadamard.

(III) Exemples concrets d'utilisation de la transformation hadamard dans de nombreux domaines.

À qui s'adresse ce livre

Professionnels, étudiants de premier cycle et des cycles supérieurs, passionnés, amateurs et ceux qui souhaitent aller au-delà des connaissances ou des informations de base pour tout type de transformation Hadamard.

 

 

• Langue: Français
• Éditeur: Un Milliard De Personnes Informées [French]
• Date de sortie: 28 avr. 2024

Aperçu du livre

Transformation d'Hadamard

Dévoilement de la puissance de Hadamard Transform dans la vision par ordinateur

Fouad Sabry est l'ancien responsable régional du développement commercial pour les applications chez Hewlett Packard pour l'Europe du Sud, le Moyen-Orient et l'Afrique. Fouad est titulaire d'un baccalauréat ès sciences des systèmes informatiques et du contrôle automatique, d'une double maîtrise, d'une maîtrise en administration des affaires et d'une maîtrise en gestion des technologies de l'information, de l'Université de Melbourne en Australie. Fouad a plus de 25 ans d'expérience dans les technologies de l'information et de la communication, travaillant dans des entreprises locales, régionales et internationales, telles que Vodafone et des machines professionnelles internationales. Actuellement, Fouad est un entrepreneur, auteur, futuriste, axé sur les technologies émergentes et les solutions industrielles, et fondateur de l'initiative One Billion Knowledge.

Un milliard de connaissances

Transformation d'Hadamard

Dévoilement de la puissance de Hadamard Transform dans la vision par ordinateur

Fouad Sabry

Copyright

Hadamard Transform © 2024 par Fouad Sabry. Tous droits réservés.

Aucune partie de ce livre ne peut être reproduite sous quelque forme que ce soit ou par quelque moyen électronique ou mécanique que ce soit, y compris les systèmes de stockage et de récupération d'informations, sans l'autorisation écrite de l'auteur. La seule exception est celle d'un critique, qui peut citer de courts extraits dans une critique.

Couverture dessinée par Fouad Sabry.

Bien que toutes les précautions aient été prises dans la préparation de ce livre, les auteurs et les éditeurs n'assument aucune responsabilité pour les erreurs ou omissions, ou pour les dommages résultant de l'utilisation des informations contenues dans le présent document.

Table des matières

Chapitre 1 : Transformation de Hadamard

Chapitre 2 : Transformée de Fourier discrète

Chapitre 3 : Transformation rapide de Walsh Hadamard

Chapitre 4 : Transformée de Fourier quantique

Chapitre 5 : Notation Bra ket

Chapitre 6 : Matrices de Pauli

Chapitre 7 : Porte logique quantique

Chapitre 8 : Porte NOT contrôlée

Chapitre 9 : Généralisations des matrices de Pauli

Chapitre 10 : Base sphérique

Appendice

À propos de l'auteur

Chapitre 1 : Transformation de Hadamard

La transformée de Hadamard (également appelée transformée de Walsh-Hadamard), transformée de Hadamard, transformée de Rademacher-Walsh et transformée de Walsh, transformée de Walsh ou transformée de Walsh-Fourier) est un type de transformée de Fourier qui appartient à une catégorie plus large.

Il résout une équation orthogonale, symétrique, involutive, linéaire sur 2m nombres réels (ou nombres complexes, très compliqués, même si les matrices de Hadamard sont entièrement non imaginaires).

Il est possible de penser que la transformée de Hadamard est construite à partir de transformées de Fourier discrètes de taille 2. (DFT), et est en fait équivalent à une DFT multidimensionnelle de taille 2 × 2 × ⋯ × 2 × 2.

Il prend n'importe quel vecteur d'entrée et le décompose en une superposition de fonctions de Walsh.

La transformée est nommée d'après le mathématicien français Jacques Hadamard (français : [adamaʁ]), mathématicien d'ascendance allemande et américaine Hans Rademacher, Joseph L. Weisstein Jr. des États-Unis.

Walsh.

La transformée de Hadamard Hm est une matrice de 2m × 2m, matrice de Hadamard (mise à l'échelle par un facteur de normalisation), qui transforme 2m nombres réels xn en 2m nombres réels Xk.

Il existe deux approches différentes pour définir la transformée de Hadamard, alternativement, en écrivant n et k sous forme binaire (base 2).

Récursivement, on définit la transformée de Hadamard 1 × 1 H0 par l'identité H0 = 1, puis on définit Hm pour m > 0 par :

{\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}}

où le 1/√2 est une normalisation qui est parfois omise.

Pour m > 1, on peut aussi définir Hm par :

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

où \otimes représente le produit de Kronecker.

Ainsi, en plus de ce paramètre de normalisation, les matrices de Hadamard sont toutes des uns et des zéros.

Alternativement, la matrice de Hadamard peut être définie par son (k, n)-ième élément, comme indiqué ci-dessous

{\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}}}

où kj et nj sont les éléments binaires (0 ou 1) de k et n, respectivement.

Attention, c'est-à-dire pour l'élément en haut à gauche, nous définissons : k=n=0 .

Ici, cependant, nous avons :

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

Il s'agit exactement de la {\textstyle 2\times 2\times \cdots \times 2\times 2} DFT multidimensionnelle, conforme à une norme unique, si les entrées et les sorties sont considérées comme des tableaux multidimensionnels indexés respectivement par nj et kj.

Voici quelques exemples spécifiques de matrices de Hadamard.

{\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}}}

où i\cdot j est le produit scalaire binaire des représentations binaires des nombres i et j.

Par exemple, si {\textstyle n\;\geq \;2} , alors

{\displaystyle (H_{n})_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1}

en confirmant ce qui précède (en ignorant la constante globale).

Gardez à l'esprit que le premier élément de la première ligne, première colonne de la matrice est désigné par {\textstyle (H_{n})_{0,0}} .

H1 est précisément le DFT de taille 2.

Le groupe additif de deux éléments, Z/, peut être considéré comme subissant une transformation de Fourier (2).

Les matrices de Hadamard ont des fonctions de Walsh dans leurs lignes.

Soit H = Hm,n] une matrice H satisfaisant à la définition précédente.

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

La transformée de Walsh produit une matrice avec uniquement les entrées 1 et 1. En raison de la nature de 1 et 1, qui ne sont ni l'un ni l'autre des nombres complexes, un calcul de nombres complexes n'est pas nécessaire.

La multiplication irrationnelle est requise pour la DFT mais pas pour la transformée de Hadamard. En fait, les changements de signe sont suffisants, donc la multiplication rationnelle n'est pas nécessaire.

Toutes les entrées de la première ligne (et colonne) de la matrice de transformation de Walsh sont égales à 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)}

Transformée de Fourier discrète :

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

Lorsque m est égal à zéros (la moyenne de la première ligne), la transformée de Fourier discrète (DFT) donne également 1. Malgré ses différences par rapport à la première ligne, la deuxième ligne révèle une caractéristique importante de la matrice : le signal dans la matrice brute initiale est basse fréquence, mais cela change au fur et à mesure que les lignes progressent.

Si nous utilisons le calcul du passage à zéro :

Première ligne = 0 passage à zéro

Deuxième ligne = 1 passage à zéro

Troisième rangée = 2 passages à zéro

⋮

Huit rangées = 7 passages à zéro

La transformée de Hadamard est en fait équivalente à une DFT multidimensionnelle de taille 2 × 2 × ⋯ × 2 × 2.

Une autre approche consiste à considérer la transformée de Hadamard comme une transformée de Fourier sur le groupe booléen {\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}} .

En appliquant la transformée de Fourier à des groupes finis (abéliens), la transformée de Fourier d'une fonction {\displaystyle f\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} } est la fonction {\widehat {f}} définie par

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

où \chi est un caractère de (\Z/2\Z)^n .

Chaque caractère a la forme {\displaystyle \chi _{r}(a)=(-1)^{a\cdot r}} pour certains {\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}} , où une chaîne de bits est multipliée par elle-même à l'aide du produit scalaire booléen, de sorte que nous pouvons identifier l'entrée à {\widehat {f}} avec {\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}} (dualité de Pontryagin) et définir {\displaystyle {\widehat {f}}\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} } par

{\displaystyle {\widehat {f}}(r)=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a)(-1)^{r\cdot a}}

Il s'agit de la transformée de Hadamard de f , en considérant l'entrée de f et {\widehat {f}} en tant que chaînes booléennes.

En ce qui concerne la formulation ci-dessus, où la transformée de Hadamard multiplie un vecteur de nombres 2^{n} complexes v à gauche par la matrice de Hadamard H_{n} , l'équivalence est vue en prenant f en entrée la chaîne de bits correspondant à l'indice d'un élément de v , et en ayant f pour sortie l'élément correspondant de v .

Comparez cela à la transformée de Fourier discrète habituelle qui, lorsqu'elle est appliquée à un vecteur v de 2^{n} nombres complexes, utilise plutôt les caractères du groupe cyclique {\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} } .

Alors que le domaine classique, la transformée de Hadamard peut être calculée en n\log n opérations ( n=2^{m} ), à l'aide d'une méthode de transformée de Hadamard rapide.

En mécanique quantique, la transformée de Hadamard peut être calculée dans le O(1) temps, puisqu'il s'agit d'une porte logique quantique parallélisable.

L'informatique quantique repose fortement sur la transformée de Hadamard.

Les transformées de Hadamard 2 × 2 H_{1} sont la porte logique quantique connue sous le nom de porte de Hadamard, et l'application d'une porte de Hadamard à chaque qubit d'un registre de n qubits en parallèle est équivalente à la transformée de Hadamard H_{n} .

Calculant au niveau quantique, la porte de Hadamard effectue une rotation d'un seul qubit, en mappant les états de base du qubit |0\rangle et |1\rangle à deux états de superposition avec un poids égal des états de base de calcul |0\rangle et |1\rangle .

Les phases sont généralement sélectionnées pour s'assurer que

{\displaystyle H={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}\langle 0|+{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\langle 1|}

dans la notation de Dirac. C'est la matrice qui se transforme, soit dit en passant.

{\displaystyle H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}

dans la |0\rangle ,|1\rangle base, équivalent à la base de calcul.

Les états {\textstyle {\frac {\left|0\right\rangle +\left|1\right\rangle }{\sqrt {2}}}} et {\textstyle {\frac {\left|0\right\rangle -\left|1\right\rangle }{\sqrt {2}}}} sont connus sous le nom