minimal filtering algorithm, Shmuel Winograd

Shmuel Winograd. Arithmetic complexity of computations, volume 33. Siam, 1980 page.39

에 컨볼루션 연산을 줄일수있는 minimal filtering algorithm이 정리되어있다.?!

FIR filter: 출력이 다시 입력으로 들어가지 않는 필터, 반대는 IIR 필터로 출력이 다시 입력으로 들어감.

r-tap FIR filter: r차원 벡터로 쉽게 생각하자.

r-tap FIR filter를 가지고 m개의 output을 출력하는 Winograd FFTs는 

F(m,r)로 표현되며 사용되는 곱연산은 뮤기호를 사용 로 표현된다.

즉, F( # of output, filter dim)으로 볼 수 있다.

Winograd FFTs의 핵심은 연산량을 줄이는 것인데 아래와 같은 법칙을 통해연산량을 줄여준다.

이 것을 2차원에 적용해보면 아래와 같은 곱 연산량을 사용함을 알수 있다.

@ 예제를 통해 어떻게 돌아가는지 살펴보자!!

그냥 컨볼루션을 해보면 아래와 같다.(Dot Product Approach)

위 콘볼루션 연산은 2개 아웃풋 필터크기가 3이다. 

총 연산량은 x: 6, +: 4 이다.

minimal filtering algorithm 을 이용해 보자. 일단 공식은 아래와 같다.

실제로 맞는지 첫번째 아웃풋만 계산해보면 아래와 같이 맞다. 맞어.

총 연산량은 x: 6 +: 11 으로 그냥 컨볼루션보다 +가 7이나 증가했다.

(데이터 +:4 , 필터 x: 2 +:3, 아웃풋 x:4 +:4)

그러나 필터 g의 값을 미리 계산해놓구 데이터 d값만이 계속해서 바뀐다고 볼수 있다.

그럼 연산량은 총 x: 4 +: 8 으로 그냥 컨볼루션에 비해 곱이 2 줄어들었고 +가 2 늘어났다. 개이득이다.

ㅇㄹㅇ러ㅏ미ㅓㅏㄹ