|
선형대수학 Linear Algebra |
|||
|
{{{#!wiki style="margin:0 -10px -5px" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin:-6px -1px -11px" |
<colbgcolor=#006ab8> 기본 대상 | 일차함수 · 벡터 · 행렬 · 선형 변환 | |
| 대수적 구조 | 가군(모듈) · 벡터 공간 · 내적 공간 | ||
| 선형 연산자 | <colbgcolor=#006ab8> 기본 개념 | 연립방정식 · 행렬곱 · 단위행렬 · 역행렬과 크라메르 공식 · 가역행렬 · 전치행렬 · 행렬식( 라플라스 전개) · 주대각합 | |
| 선형 시스템 | 기본행연산과 기본행렬 · 가우스-조르당 소거법 · 행사다리꼴 · 행렬표현 · 라그랑주 보간법 | ||
| 주요 정리 | 차원 정리 · 가역행렬의 기본정리 · 선형대수학의 기본정리 · 스펙트럼 정리 | ||
| 기타 | 제곱근행렬 · 멱등행렬 · 멱영행렬 · 에르미트 행렬 · 야코비 행렬 · 방데르몽드 행렬 · 아다마르 행렬 변환 | ||
| 벡터공간의 분해 | 상사 · 고유치 문제 · 케일리-해밀턴 정리 · 대각화( 대각행렬) · 삼각화 · 조르당 분해 | ||
| 벡터의 연산 | 내적 · 외적( 신발끈 공식) · 다중선형형식 · [math(boldsymbolnabla)] · 크로네커 델타 | ||
| 내적공간 | 그람-슈미트 과정 · 수반 연산자( 에르미트 내적) | ||
| 다중선형대수 | 텐서 · 텐서곱 · 레비치비타 기호 | }}}}}}}}} | |
| 한국어 | 아다마르 변환 |
| 영어 | Hadamard transform |
[clearfix]
1. 개요
아다마르 변환(Hadamard transform)은 이진 범위에서 실수를 연산할때 선형적으로 수행하는 푸리에 변환을 일반화시킨 연산법이다. 즉 임의의 벡터값을 분해하는 특징이 있기 때문에 이진 연산 범위에서의 DFT를 행렬로 정의할수 있다.프랑스 수학자 자크 아다마르와 독일 수학자 한스 라데마허, 미국 수학자 조세프 웰시가 아다마르 변환을 정립했다.
2. 정의
이진 행렬 [math(2^N \times 2^N)]을 가정할때, [math(2^N)]의 실수 [math(x_n)]을 또 다른 행렬 원소 [math(2^N)]의 실수 [math(X_k)]로 변환하는 방법을 아다마르 변환 [math(H_N)]을 아다마르 변환이라고 하고 아래와 같은 공식으로 쓴다.[math(\displaystyle X_k = \dfrac{1}{\sqrt{2^N}}\sum_{n=0}^{N}|x_n\rangle)]
아다마르 변환은 재귀적으로 풀어가는 방법과, n과 k에 binary을 적용하는 크게 2가지 방법으로 정의된다.
재귀적으로 풀때, 아다마르 변환 [math(H_0)]은 [math(1 \times 1)] 행렬로 정의되므로 [math(H_0)]이 항등원임을 알수 있다. 그러므로 N>0이라는 가정하에, [math(H_N)]이 다음과 같은 행렬로 나타나게 된다.
[math(\displaystyle H_{N+1} = \frac{1}{\sqrt{2}} \begin{pmatrix} & H_{N} & H_{N} & \\ & H_{N} & -H_{N} & \end{pmatrix} )]
그러므로 N>1일때, [math(H_N)]이 아래와 같은 크로네커 곱[1]으로 표현됨을 알수 있다.
[math(H_{N+1} = H_1 \otimes H_{N})]
또 다른 방법인 이진법을 이용하면, n과 k는 다음과 같이 정의된다.
[math(\displaystyle k=\sum_{i=0}^{N}k_i 2^i = k_{N}2^{N} + k_{N-1}2^{N-1} + \cdots + k_1 2 + k_0 )]
[math(\displaystyle n=\sum_{i=0}^{N}n_i 2^i = n_{N}2^{N} + n_{N-1}2^{N-1} + \cdots + n_1 2 + n_0 )]
그러므로,
[math((H_{N+1})_{n,k} = \dfrac{1}{2^{\frac{N}{2}}}(-1)^{\sum_j k_j i_j})][2]
혹은,
따라서, 대입값과 산출값이 [math(n_j)]와 [math(k_j)]의 다중차원 배열일때, 아다마르 변환은 [math(2^n)]의 다중차원 DFT임을 알수 있다.
3. 푸리에 변환과의 관계
초등 아벨군, [math((\mathbb Z/2\mathbb Z)^n)]의 푸리에 변환은 아다마르 변환을 설명하는 방법들중 하나이다. 유한군에서의 푸리에 변환을 상기하면, [math(f:((\mathbb Z/2\mathbb Z)^n) → \mathbb C)]라는 함수의 푸리에 변환 [math(\hat f)]은 다음과 같이 정리된다.[math(\displaystyle \hat f(x) = \sum_{a\in(\mathbb Z/2\mathbb Z)^n} f(a) \overline x(a))]
여기서 x는 [math((\mathbb Z/2\mathbb Z)^n)]의 지표이다. 곱연산이 초등 아벨군의 내적일때, 한 [math(r\in(\mathbb Z/2\mathbb Z)^n)]에 대해, 각 지표는 [math(x_r(a)=(-1)^{ar})]로 정리될수 있다. 그러므로 지표의 특성을 고려하여 식을 다시 정리하면,
[math(\displaystyle \hat f(x) = \sum_{a\in(\mathbb Z/2\mathbb Z)^n} f(a)(-1)^{ar})]
즉, f(a)에 대한 아다마르 변환이 나옴을 알수있다. 위의 정의 문단에서 아다마르 변환이 아다마르 행렬 왼쪽에 있는 식 복소수 v를 [math(2^n)]이라는 벡터의 곱연산임을 상기하면, f에 v의 원소의 지표와 일치하는 비트 끈을 대입함으로써 동일함이 성립됨을 알 수 있다.
4. 양자 정보학
양자 컴퓨팅에서 가장 중요한 변환중 하나이다.아다마르 변환은 양자 알고리즘의 기본적인 초기 연산 방법으로 많이 사용된다. [math(|0\rangle)]과 함께 초기화된 큐비트 [math(2^N)]이 직교화 상태로 중첩되도록해서 [math(|0\rangle )]혹은 [math(|1\rangle)]기저를 가지도록 한다. 즉, 데이터화된 임의의 정보를 알고리즘에 대입하면 알고리즘 내에서 그 정보를 양자 중첩 상태로 만드는 매우 중요한 역할을 한다.
이런 특성으로 고전 컴퓨팅에서의 아다마르 변환은 [math({\mathcal O}(n\log n))]이라는 지수적인 시간 복잡도를 가지나 양자 컴퓨팅에서는 [math({\mathcal O}(1))]의 시간 복잡도를 가진다.
특히, 여러 아다마르 변환중에서 [math(2 \times 2)]의 아다마르 변환 [math(H_1)]이 양자 논리 회로에서 아다마르 게이트라는 이름으로 활용된다.
4.1. 아다마르 게이트
아다마르 게이트는 양자 컴퓨팅에서 1 큐비트 회전을 의미한다. 계산적인 기저 상태인 [math(|0\rangle )]와 [math(|1\rangle )]로 큐비트 기저 상태, [math(|0\rangle )]와 [math(|1\rangle )]를 중첩한 상태의 사상을 디랙 규약으로 나타내면[math(H=\dfrac{|0 \rangle + |1 \rangle}{\sqrt{2}}\langle 0| + \dfrac{|0 \rangle - |1 \rangle}{\sqrt{2}}\langle 1|)]
위 식은 아다마르 변환 [math(H_1)]과 일치한다. 참고로 [math(\frac{|0 \rangle + |1 \rangle}{\sqrt{2}}\langle 0|)]과 [math(\frac{|0 \rangle - |1 \rangle}{\sqrt{2}}\langle 1|)]는 각각 [math(|+\rangle)]과 [math(|-\rangle)]에 일치함으로써, 양자 컴퓨팅의 극점 기저로 활용된다.
4.1.1. 연산
아다마르 게이트의 연산은 다음과 같다.[math(H(|0\rangle)=\frac{|0 \rangle + |1 \rangle}{\sqrt{2}}\langle 0|:=|+\rangle)]
[math(H(|1\rangle)=\frac{|0 \rangle - |1 \rangle}{\sqrt{2}}\langle 1|:=|-\rangle)]
[math(H(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle)=\frac{1}{2}(|0\rangle +|1\rangle)+\frac{1}{2}(|0\rangle - |1\rangle)=|0\rangle)]
[math(H(\frac{1}{\sqrt{2}}|0\rangle - \frac{1}{\sqrt{2}}|1\rangle)=\frac{1}{2}(|0\rangle +|1\rangle)-\frac{1}{2}(|0\rangle - |1\rangle)=|1\rangle)]
위 연산에서는 0,1이 양자 상태를 결정하고, 양자 상태가 관측되면, 0,1으로 나타내질 확률이 1/2가 된다.
5. 계통 유전학
아다마르 변환은 유기체를 이루는 분자들의 상호작용을 측정할 수 있기 때문에 계통 유전 트리에도 사용된다. 계통 유전 트리에 아다마르 변환을 이용하면 유전체 염기서열의 위치 패턴 빈도들의 벡터 값에 계통 위상의 유전적인 정보를 다루는 다른 벡터 값을 도출할 수 있게 된다. 또한 아다마르 변환의 변환적 특징(invertible nature)을 사용해서 유전 계통에서의 유전적 정보내 원소의 특정 위치를 확률적으로 계산할 수 있다.유전 계통의 아다마르 변환이 적용되는 역학적 원리는 다음과 같다.
[math(\displaystyle \gamma(T)=H^{-1}(\ln(Hs(T)))]
벡터 연산 [math(\gamma(T))]과 아다마르 행렬 H를 적용한 위 식을 활용하면 위치 패턴 벡터 s(T)를 정의해서 유전 계통 트리의 가지 길이 T와 위상에 관한 정보를 알수있다.
그러므로 위식을 변환(invertible nature)하여 위치 백터를 도출하는 식은 위식의 역연산과 동치이다.
[math(\displaystyle s(T)=H^{-1}(e^{H\gamma(T)}))]
한편, 유전체의 아미노산 합성 정보에 관여하는 A,T,G,C의 위치 패턴을 아다마르 변환을 활용하여 이진 모델인 CFN-이종 상태 대체 모델로 깔끔하게 나타내기 위해서는 퓨린기의 A과 G을 R, 피리미딘기의 C과 T은 Y로 치환하고 위 식을 아래와 같이 치환해야 한다.
[math(\displaystyle r=Hs(T))]
[math(\displaystyle ρ=\ln\,r)]
[math(\displaystyle \gamma(T)=H^{-1}ρ)]
그러므로, invertible한 식, 치환한 식과 유전체 이진 부호를 모두 적용하면, 트리 벡터 [math(\gamma(T))]와 위치 패턴 벡터 [math(s(T))]을 CFN-이종 상태 대체 모델의 표로 깔끔하게 계산할 수 있다.
| index | 이진패턴 | 배열패턴 | [math(\gamma(T))] | [math(ρ=H^{-1}\gamma(T))] | [math(r=e^ρ)] | [math(H^{-1}ρ=s(T))] |
| 0 | 0000 | RRRR | -0.475 | 0 | 1 | 0.6479 |
| 1 | 0001 | RRRY | 0.2 | -0.5 | 0.6065 | 0.1283 |
| 2 | 0010 | RRYR | 0.025 | -0.15 | 0.8607 | 0.02 |
| 3* | 0011 | RRYY | 0.025 | -0.45 | 0.6376 | 0.0226 |
| 4 | 0100 | RYRR | 0.2 | -0.45 | 0.6376 | 0.1823 |
| 5* | 0101 | RYRY | 0 | -0.85 | 0.4274 | 0.0258 |
| 6* | 0110 | RYYR | 0 | -0.5 | 0.6065 | 0.0070 |
| 7 | 0111 | RYYY | 0.025 | -0.9 | 0.4066 | 0.02 |