재귀 최소 제곱 필터

**재귀 최소 제곱**(, **RLS**)은 입력 신호와 관련된 가중 선형 최소 제곱 비용 함수를 최소화하는 계수를 재귀적으로 찾는 적응 필터 알고리즘이다. 이 접근 방식은 최소 평균 제곱법(LMS)과 같이 평균 제곱 오차를 줄이는 것을 목표로 하는 다른 알고리즘과 대조된다. RLS의 도출에서는 입력 신호가 결정론적으로 간주되는 반면, LMS 및 유사 알고리즘에서는 추계학적으로 간주된다. 대부분의 경쟁자들과 비교했을 때, RLS는 매우 빠른 수렴을 보인다. 그러나 이 이점은 높은 계산 복잡성을 대가로 얻어진다.

## 동기 부여
RLS는 가우스에 의해 발견되었으나 1950년 플래킷이 1821년의 가우스의 원본 작업을 재발견할 때까지 사용되지 않거나 무시되었다. 일반적으로 RLS는 적응 필터로 해결할 수 있는 모든 문제를 해결하는 데 사용될 수 있다. 예를 들어, 신호 d(n)이 울림이 있고 잡음이 많은 채널을 통해 전송되어 다음과 같이 수신된다고 가정해 보자.

:x(n)=\sum_{k=0}^q b_n(k) d(n-k)+v(n)

여기서 v(n)은 가산 잡음을 나타낸다. RLS 필터의 목적은 p+1-탭 FIR 필터 \mathbf{w}를 사용하여 원하는 신호 d(n)을 복구하는 것이다.

:d(n) \approx \sum_{k=0}^{p} w(k)x(n-k)=\mathbf{w}^\mathit{T} \mathbf{x}_n

여기서 \mathbf{x}_n = [x(n)\quad x(n-1)\quad\ldots\quad x(n-p)]^T는 x(n)의 가장 최근 p+1개 샘플을 포함하는 열 벡터이다. 복구된 원하는 신호의 추정치는 다음과 같다.

:\hat{d}(n) = \sum_{k=0}^{p} w_n(k)x(n-k)=\mathbf{w}_n^\mathit{T} \mathbf{x}_n

목표는 필터 \mathbf{w}의 매개변수를 추정하는 것이며, 각 시간 n에서 현재 추정치를 \mathbf{w}_n으로, 적응된 최소 제곱 추정치를 \mathbf{w}_{n+1}로 나타낸다. \mathbf{w}_n은 아래에 표시된 대로 열 벡터이며, 전치 \mathbf{w}_n^\mathit{T}는 행 벡터이다. 행렬 곱셈 \mathbf{w}_n^\mathit{T} \mathbf{x}_n(\mathbf{w}_n과 \mathbf{x}_n의 스칼라곱과 같음)은 스칼라 \hat{d}(n)이다. 추정치는 \hat{d}(n)-d(n)이 어떤 최소제곱법 의미에서 작은 크기를 가질 때 "좋은" 것이다.

시간이 지남에 따라 \mathbf{w}_n의 관점에서 \mathbf{w}_{n+1}에 대한 새로운 추정치를 찾기 위해 최소 제곱 알고리즘을 완전히 다시 수행하는 것을 피하는 것이 바람직하다.

RLS 알고리즘의 이점은 행렬을 역전시킬 필요가 없어 계산 비용을 절감한다는 것이다. 또 다른 장점은 칼만 필터와 같은 결과 뒤에 있는 직관을 제공한다는 것이다.

## 논의
RLS 필터의 아이디어는 새로운 데이터가 도착함에 따라 필터를 업데이트하면서 필터 계수 \mathbf{w}_n를 적절히 선택하여 비용 함수 C를 최소화하는 것이다. 오차 신호 e(n)와 원하는 신호 d(n)은 아래의 음성 되먹임 다이어그램에 정의되어 있다.

500px

오차는 추정치 \hat{d}(n)를 통해 필터 계수에 암묵적으로 의존한다.

:e(n)=d(n)-\hat{d}(n)

최소화하려는 비용 함수인 가중 최소 제곱 오차 함수 C는 e(n)의 함수이므로 필터 계수에도 의존한다.
:C(\mathbf{w}_n)=\sum_{i=0}^n\lambda^{n-i}e^2(i)
여기서 0은 오래된 오차 샘플에 기하급수적으로 적은 가중치를 부여하는 "망각 계수"이다.

비용 함수는 계수 벡터 \mathbf{w}_{n}의 모든 항목 k에 대해 편미분을 취하고 그 결과를 0으로 설정하여 최소화된다.
:\frac{\partial C(\mathbf{w}_n)}{\partial w_n(k)}=\sum_{i=0}^n 2\lambda^{n-i}e(i)\cdot \frac{\partial e(i)}{\partial w_n(k)}=-\sum_{i=0}^n 2\lambda^{n-i}e(i)\,x(i-k)=0 \qquad k=0,1,\ldots,p
다음으로, e(n)을 오차 신호의 정의로 대체한다.
:\sum_{i=0}^n\lambda^{n-i}\left[d(i)-\sum_{\ell=0}^p w_n(\ell)x(i-\ell)\right]x(i-k)= 0\qquad k=0,1,\ldots,p
방정식을 재배열하면 다음이 나온다.
:\sum_{\ell=0}^p w_n(\ell)\left[\sum_{i=0}^n \lambda^{n-i}\,x(i-\ell)x(i-k)\right]= \sum_{i=0}^n \lambda^{n-i}d(i)x(i-k) \qquad k=0,1,\ldots,p
이 형식은 행렬로 표현할 수 있다.
:\mathbf{R}_{x}(n)\,\mathbf{w}_{n}=\mathbf{r}_{dx}(n)
여기서 \mathbf{R}_{x}(n)은 x(n)에 대한 가중 표본 공분산 행렬이며, \mathbf{r}_{dx}(n)은 d(n)과 x(n) 사이의 교차 공분산에 대한 등가 추정치이다. 이 표현을 기반으로 비용 함수를 최소화하는 계수를 다음과 같이 찾는다.
:\mathbf{w}_{n}=\mathbf{R}_{x}^{-1}(n)\,\mathbf{r}_{dx}(n)
이것이 논의의 주요 결과이다.

### λ 선택
\lambda가 작을수록 이전 샘플이 공분산 행렬에 기여하는 정도가 작아진다. 이는 필터가 최근 샘플에 더 민감하게 반응하게 하며, 이는 필터 계수의 더 많은 변동을 의미한다. \lambda=1인 경우는 성장 윈도우 RLS 알고리즘이라고 한다. 실제로 \lambda는 일반적으로 0.98에서 1 사이로 선택된다. 유형-II 최대 가능도 추정을 사용하여 데이터 집합에서 최적의 \lambda를 추정할 수 있다.

## 재귀 알고리즘
이 논의는 비용 함수를 최소화하는 계수 벡터를 결정하는 단일 방정식을 산출했다. 이 섹션에서는 다음과 같은 형식의 재귀 해법을 도출하고자 한다.
:\mathbf{w}_{n}=\mathbf{w}_{n-1}+\Delta\mathbf{w}_{n-1}
여기서 \Delta\mathbf{w}_{n-1}는 시간 {n-1}에서의 보정 계수이다. 재귀 알고리즘의 도출은 교차 공분산 \mathbf{r}_{dx}(n)을 \mathbf{r}_{dx}(n-1)로 표현하는 것으로 시작한다.
:
여기서 \mathbf{x}(i)는 {p+1} 차원 데이터 벡터이다.
:\mathbf{x}(i)=[x(i), x(i-1), \dots , x(i-p) ]^{T}
마찬가지로 \mathbf{R}_{x}(n)을 \mathbf{R}_{x}(n-1)로 다음과 같이 표현한다.
:
계수 벡터를 생성하기 위해서는 결정론적 자기 공분산 행렬의 역행렬에 관심이 있다. 이 작업에는 우드버리 행렬 항등식이 유용하다.
:
우드버리 행렬 항등식은 다음과 같다.
:
표준 문헌과 일치시키기 위해 다음을 정의한다.
:
여기서 이득 벡터 g(n)은 다음과 같다.
:
진행하기 전에 \mathbf{g}(n)을 다른 형태로 가져올 필요가 있다.
:
왼쪽의 두 번째 항을 빼면 다음이 나온다.
:
\mathbf{P}(n)의 재귀적 정의를 사용하면 원하는 형식이 따른다.
:\mathbf{g}(n)=\mathbf{P}(n)\mathbf{x}(n)
이제 재귀를 완료할 준비가 되었다. 논의된 바와 같이
:
두 번째 단계는 \mathbf{r}_{dx}(n )의 재귀 정의에서 따른다. 다음으로, \mathbf{P}(n)의 재귀 정의와 \mathbf{g}(n)의 대체 형식을 통합하여 다음을 얻는다.
:
\mathbf{w}_{n-1}=\mathbf{P}(n-1)\mathbf{r}_{dx}(n-1)을 사용하면 업데이트 방정식에 도달한다.
:
여기서 \alpha(n)=d(n)-\mathbf{x}^{T}(n)\mathbf{w}_{n-1}
는 사전(a priori) 오차이다. 필터가 업데이트된 후 계산된 사후(a posteriori) 오차와 비교해 보라.

:e(n)=d(n)-\mathbf{x}^{T}(n)\mathbf{w}_n

이는 보정 계수를 찾았음을 의미한다.
:\Delta\mathbf{w}_{n-1}=\mathbf{g}(n)\alpha(n)

이 직관적으로 만족스러운 결과는 보정 계수가 오차와 이득 벡터에 모두 비례하며, 이득 벡터는 가중 계수 \lambda를 통해 원하는 민감도를 제어함을 나타낸다.

## RLS 알고리즘 요약
p차 RLS 필터에 대한 RLS 알고리즘은 다음과 같이 요약할 수 있다.

P에 대한 재귀는 대수 리카티 방정식을 따르므로 칼만 필터와 유사하다.

## 격자 재귀 최소 제곱 필터(LRLS)
**격자 재귀 최소 제곱** 적응 필터는 표준 RLS와 관련이 있지만 더 적은 산술 연산(N차)을 필요로 한다. 이는 더 빠른 수렴 속도, 모듈형 구조, 입력 상관 행렬의 고유값 확산 변화에 대한 비민감성 등 기존 LMS 알고리즘에 비해 추가적인 이점을 제공한다. 설명된 LRLS 알고리즘은 사후(a posteriori) 오차를 기반으로 하며 정규화된 형태를 포함한다. 유도는 표준 RLS 알고리즘과 유사하며 d(k)\,\!의 정의를 기반으로 한다. 전방 예측의 경우, x(k-1)\,\!을 가장 최신 샘플로 하여 d(k) = x(k)\,\!이다. 역방향 예측의 경우는 d(k) = x(k-i-1)\,\!이며, 여기서 i는 예측하려는 과거 샘플의 인덱스이고, 입력 신호 x(k)\,\!는 가장 최근 샘플이다.

### 매개변수 요약
:\kappa_f(k,i)\,\!는 전방 반사 계수
:\kappa_b(k,i)\,\!는 후방 반사 계수
:e_f(k,i)\,\!는 순간 사후 전방 예측 오차를 나타냄
:e_b(k,i)\,\!는 순간 사후 후방 예측 오차를 나타냄
:\xi^d_{b_{\min}}(k,i)\,\!는 최소 제곱 후방 예측 오차
:\xi^d_{f_{\min}}(k,i)\,\!는 최소 제곱 전방 예측 오차
:\gamma(k,i)\,\!는 사전 및 사후 오차 간의 변환 계수
:v_i(k)\,\!는 피드포워드 승수 계수
:\varepsilon\,\!는 0.01이 될 수 있는 작은 양의 상수

### LRLS 알고리즘 요약
LRLS 필터의 알고리즘은 다음과 같이 요약할 수 있다.

## 정규화된 격자 재귀 최소 제곱 필터(NLRLS)
NLRLS의 정규화된 형태는 재귀와 변수의 수가 더 적다. 이는 알고리즘 내부 변수에 정규화를 적용하여 그 크기가 1로 제한되도록 함으로써 계산할 수 있다. 이는 일반적으로 높은 계산 부하를 수반하는 나눗셈 및 제곱근 연산의 수 때문에 실시간 응용 프로그램에서는 사용되지 않는다.

### NLRLS 알고리즘 요약
NLRLS 필터의 알고리즘은 다음과 같이 요약할 수 있다.

## 같이 보기
* 적응 필터
* 커널 적응 필터
* 최소 평균 제곱 필터
* 제로 포싱 이퀄라이저

## 각주
* 
* Simon Haykin, Adaptive Filter Theory, Prentice Hall, 2002, 
* M.H.A Davis, R.B. Vinter, Stochastic Modelling and Control, Springer, 1985, 
* Weifeng Liu, Jose Principe and Simon Haykin, Kernel Adaptive Filtering: A Comprehensive Introduction, John Wiley, 2010, 
* R.L.Plackett, Some Theorems in Least Squares, Biometrika, 1950, 37, 149–157, 
* C.F.Gauss, Theoria combinationis observationum erroribus minimis obnoxiae, 1821, Werke, 4. Gottinge

## 내용주

분류:디지털 신호 처리
분류:필터 이론
분류:통계학적 신호 처리