Geometry & Recognition

Forward fft: 

$$ {\tt fft}(x+iy)=X + i Y = \sum(x +i y) (W_r + i W_i)\\=\sum  (x W_r - y W_i ) + i (x W_i + y W_r)$$

Inverse fft:

$$ {\tt ifft}(X+iY)= \frac{1}{N}\sum(X +i Y) (W_r - i W_i)\\= \frac{1}{N} \sum  (X W_r + Y W_i ) + i (-X W_i + Y W_r)\\ =\frac{1}{N}\sum \left(XW_r - (-Y) W_i\right) +(-i) \left(XW_i + (-Y)W_r\right) \\ = \frac{1}{N}\left[{\tt fft}(X-iY) \right]^* = \frac{1}{N}\left[{\tt fft}((X+iY)^*)\right]^*$$

또는 

$$ \frac{1}{N} {\tt fft}(Y+iX)= \frac{1}{N} \sum(Y +i X) (W_r + i W_i)\\=\frac{1}{N} \sum  (Y W_r - X W_i ) + i (Y W_i + X W_r)\\= y + i x$$

$$X_m = \sum_{n=0}^{N/2-1} x_{2n} W_N^{mn} +W_N^m \sum _{n=0}^{N/2-1} x_{2n+1} W_N^{mn}$$

$$X_{m+N/2} = \sum_{n=0}^{N/2-1} x_{2n} W_N^{mn} -W_N^m \sum _{n=0}^{N/2-1} x_{2n+1} W_N^{mn}$$

$$m=0,1,...,N/2-1$$

Butterfly Structure:

FFT for N=8:

/* sin(), cos() 함수를 $\log_2(N/4)$번만 호출하면 된다. 이마저도 2배각 공식을 쓰면 sqrt() 호출로 대체할 수 있다 */

#define PI	3.1415926535897932384
#define SWAP(a, b) {double temp = (a); (a) = (b); (b)=temp;}
int fft(int n, double x[], double y[]) {
    if ((n !=0) && ((n & (n-1)) != 0) ) return 0;
    // bit-reversal;
    for (int i = 0, j = 0; i < n-1; i++) {
        if (i < j) {
            SWAP(x[i], x[j]); SWAP(y[i], y[j]);
        }
        int k = n >> 1;
        while (k <= j) {
            j -= k; k >>= 1;
        }
        j += k;
    }
    // Danileson-Lanczos section;
    double rotwr = -1, rotwi = 0;
    for (int loop = 1; loop < n; loop <<= 1) {	
        int block = loop << 1;				// block-size;2->4->8->...
        if (loop > 2) {
            // rotation factor of twiddle factor;
            double theta = PI / loop;
            rotwr = cos(theta);
            rotwi = -sin(theta);
        } else if (loop == 2) {
            rotwr = 0;
            rotwi = -1;
        }	
        // starting twiddle factor;
        double wr = 1;
        double wi = 0;
        for (int j = 0; j < loop; ++j) { 
            // 각 block의 같은 위치에서 동일한 twiddle factor가 곱해진다는 
            // 사실을 이용함;
            for (int i = j; i < n; i += block) {
                int ip = i + loop;
                // step-1; X[ip]*W
                double xwre = x[ip] * wr - y[ip] * wi;
                double xwim = x[ip] * wi + y[ip] * wr;
                // step-2; X[ip] = X[i] - X[ip]*W;
                x[ip] = x[i] - xwre;
                y[ip] = y[i] - xwim;
                // step-3; X[i] = X[i] + X[ip]*W;
                x[i] += xwre;
                y[i] += xwim;
            };
            // 각 block의 다음 차례에 곱해지는 twiddle factor 계산; T = W * rotW;
            double tre = wr * rotwr - wi * rotwi;
            double tim = wi * rotwr + wr * rotwi;
            wr = tre;
            wi = tim;
        }
    }
    return 1;
    // 역변환: (1/N)*conjugate[FFT[conjugate(X)]] 
}

Euclidean 공간에서 Cauchy-Schwartz inequality는 두 벡터 내적의 크기는 두 벡터 크기의 곱보다 작음을 보여준다. 그러나 Minkowski 공간에서는 부등호 방향이 반대가 된다. 이를 잘 알려진 특수상대성 이론에서의 쌍둥이 역설(역설이라 표현되어 있지만 실제로 역설은 아니다) 예를 이용해서 보이자. 두 쌍둥이 중 A는 지구에서 남아 있고  B는 일정한 속도로 우주여행을 한 후에 다시 지구로 돌아왔을 때 여행을 한 쌍둥이 B가 더 젊다는 것은 특수상대성 이론이 보여준 자연의 법칙의 한 단면이다. 사람이 정지해 있거나 일정한 속도로 움직이는 경우 시공간에서 경로는 직선(시공간 벡터)으로 표현이 된다. 그리고 이 직선의 길이는(*Minkowski space 임에 주의) 시공간에서 이 두 지점(event)을 연결하는 직선을 따라 움직이는 사람의 끝 위치에서 나이가 시작에서 보다 얼마나 더 들었는가를 나타낸다. 여행을 떠난 쌍둥이 B의 목적지까지 시공간 벡터를 $\mathbf{a}$, 목적지에서 다시 지구까지 시공간 벡터를 $\mathbf{b}$라고 하면  다시 지구에서 두 쌍둥이가 재회하므로 두 벡터의 합은 지구에 남아 있는 쌍둥이 A의 시공간 벡터 $\mathbf{c}$와 같다.

$$ \mathbf{c}= \mathbf{a}+\mathbf{b}$$

여행을 시작해서 끝날 때까지 지구에 남아 있는 쌍둥이 A가 먹은 나이는 $|\mathbf{c}|$, 여행을 한 쌍둥이 B의 나이는 $|\mathbf{a}| + |\mathbf{b}|$ (목적지에서 방향을 바꾸는과정이 필요하므로 이보다 약간 더 먹는다). 두 쌍둥이가 다시 만났을 때 지구에 남아 있는 쌍둥이가 더 나이가 들어 있으므로

$$ |\mathbf{c}|  \ge |\mathbf{a}| + |\mathbf{b}|$$

이다. 양변을 제곱을 하면 다음과 같은 역 Cauchy-Schwartz 부등식을 얻을 수 있다(Mikowski metric의 signature에 선택에 무관하게 만들기 위해서 다시 제곱을 하였다)

$$ (\mathbf{a} \cdot \mathbf{b})^2 \ge |\mathbf{a}|^2|\mathbf{b}|^2$$ 

열용량이 $C_i$이고 절대온도가 $T_i$인 $N$개의 물체를 열접촉을 시키자. 물체들 사이의 열교환에 의해서 시간이 충분히 지나면 모든 물체는 같은 온도 $\overline{T}$를 가지는 평형상태에 도달한다. 이때 열역학 1법칙에 의해서 각 물체가 방출하거나 흡수한 열량의 총합은 0이 되어야 한다는 사실에서 평형상태의 온도를 알아낼 수 있다.

$$  \sum C_i (T_i - \overline{T}) = 0\quad \to \quad  \overline{T} = \frac{\sum C_i T_i}{\sum C_k}$$

열전도 과정은 비가역과정이므로 열역학 2법칙에 의해서 엔트로피가 증가해야 한다. 평형상태에 이르는 과정에서 증가한 엔트로피는 다음과 같이 계산이 된다. 

$$ \Delta S = \sum \int _{T_i}^{\overline{T}} \frac{C_i dT }{T} = \sum C_i \ln\frac {\overline{T}}{T_i} \ge 0 \\ \text{or} \qquad \qquad \sum C_ i \ln \overline{T} \ge \sum C_i \ln T_i$$

양변을 열용량의 합 $\sum C_k$로 나누면 

$$ \sum p_i T_i  \ge \prod T_i^{p_i}, \qquad  0 \le p_i=\frac{C_i}{ \sum C_k} \le 1,~~\sum p_i =1$$

이어서 가중치를 가지는 AM-GM inequality가 증명된다. 등호는 처음 모든 물체의 온도가 같은 경우에 성립하는데 이때는 열교환이 없으므로 엔트로피의 변화가 없기 때문이다. 이 증명은 같은 온도, 같은 압력을 가지는 서로 다른 이상기체를 섞는 과정에서 entropy 변화를 이용해서도 보일 수 있다.

Communicating vessels 시스템을 이용하면 수학적으로 매우 중요한 여러 가지 부등식을 간단히 물리법칙을 이용해서 증명할 수 있는데 여기서는 Jessen 부등식을 보이자. Jensen 부등식은 convex 함수 $F(x)$가 있을 때 주어진 값들의 convex combination에서의 함숫값은 각각의 점에서 함숫값의 convex conbination보다 클 수 없다는 것을 나타낸다.

$$ F \left( \sum p_i x_i\right) \le  \sum p_ i F(x_i),  \qquad  \sum p_i = 1, ~~ 0 \le p_i \le 1$$

물론 함수가 concave면 부등식은 반대로 적용된다. 

이를 물리법칙을 이용해서 증명하기 전에 먼저 높이에 따라 단면적이 달라지는 한 물기둥(기준 물기둥)을 고려하자. 높이 $y$일 때 물기둥에 담긴 물의 총량을 $m(y)$라고 하면 이는 높이 $y$의 증가함수이다: $dm/dy > 0$. 이제 이 기준 물기둥의 단면적을 각각 $w_i$배만큼 늘려진 모양을 갖는 물기둥 $N$개를 준비한 후, 각 기둥의 맨 아래 부분이 서로 연결할 수 있게 밸브를 설치해서 그림과 같은 communicating vessels 시스템을 만든다.

밸브가 열리기 전 $i-$번째 물기둥의 높이를 $y_i$라면 담긴 물의 양은 $M_i (y_i) =w_i m(y_i) \equiv w_i m_i $가 된다. 그리고 물의 총량은 $M_\text{tot} = \sum M_i(y_i) = \sum w_i m_i$이다.

밸브를 열면 물기둥 사이의 수압의 차이에 의해서 물이 이동하게 되고 이 과정에서 에너지의 감쇄로 인해 모든 물기둥의 높이가 같아지는 평형상태에 도달한다.  물의 총량은 보존되어야 하므로 평형상태의 물기둥의 높이를 $\overline{y}$라면 

$$ \sum M_i (y_i) = \sum M_i (\overline{y})\quad \to \quad m(\overline{y}) = \frac{\sum w_i m_i }{\sum w_k}$$

밸브를 열기 전 물기둥 속 물의 총 중력위치에너지는 

$$ PE_\text{initial} = \sum w_i g \int_0^{y_i} y dm = \sum w_i U (y_i)$$

여기서 높이 $y$일 때 기준 물기둥의 단면적를 $A(y)$라면 기준 물기둥 속 물의 위치에너지와 물의 질량은 각각

$$U(y) \equiv g \int_0^y y' dm '=g \int_0^{y} \rho y'A(y') dy'   \\ m(y) = \int_0^y \rho A(y') dy'$$

밸브를 열어 평형상태에 도달한 이후 물의 총 중력위치에너지는

$$ PE_\text{final} = \sum w_i U(\overline{y})$$

평형상태에 이르는 과정에서의 에너지 손실을 고려하면 $PE_\text{final} \le PE_\text{initial}$이므로

$$     U( \overline{y}) \le \frac{\sum w_i U(y_i) }{\sum w_k} $$

임을 알 수 있다.

물기둥에 담긴 물의 양이 높이의 증가함수이므로 $U$는 물의 양 $m$의 함수로 생각할 수 있다. 또한 단면적을 선택할 수 있는 자유도가 있으므로 $U$에 대해서 사전에 특별한 제약조건이 주어지지는 않았다. 그렇지만

$$\frac{dU}{dm} = \frac{dU/dy}{dm/dy} = gy \\ \frac{d^2 U}{dm^2 }= \frac{g}{dm/dy} >0$$

이어서 $U$가 $m$에 대해서 convex 함수임을 볼 수 있다. 이제 높이 대신 $m$으로 표현하면

$$ U(\overline{m}) \le \sum p_i U(m_i),\qquad 0\le p_i = \frac{w_i }{ \sum w_k} \le1$$

또는

$$ U \left( \sum p_i m_i \right) \le \sum p_i U(m_i),\qquad \left(\sum p_i=1,~~0\le p_i \le1 \right)$$

을 얻는다. 등호는 모든 물기둥의 처음 높이가 같아서 처음부터 평형상태에 있는 경우에 해당한다. 다시 언급하지만 수학적인 방법을 동원하지 않고, 질량 보존법칙과 물리계가 평형상태에 이루는 과정에서 에너지적으로 가장 낮은 상태로 향한다는 자명한 물리법칙을 이용해서 증명하였다.

Convex 함수로 $U(x) = -\log(x)$를 선택하면(note: $d^2 U/dx^2 = 1/x^2 >0$) Jensen의 부등식에서 아래처럼 산술평균-기하평균에 관한 부등식을 얻을 수 있다.

$$ - \log ( \sum p_i m_i ) \le -\sum p_i \log (m_i) \\ \to \sum p_i m_i \ge \prod m_i^{p_i}~~:\text{AM-GM Inequality}$$