재귀 최소 제곱 필터

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

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

여기서 은 가산 잡음을 나타낸다. RLS 필터의 목적은 -탭 FIR 필터 를 사용하여 원하는 신호 을 복구하는 것이다.

여기서 는 의 가장 최근 개 샘플을 포함하는 열 벡터이다. 복구된 원하는 신호의 추정치는 다음과 같다.

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

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

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

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

500px

오차는 추정치 를 통해 필터 계수에 암묵적으로 의존한다.

최소화하려는 비용 함수인 가중 최소 제곱 오차 함수 는 의 함수이므로 필터 계수에도 의존한다.

여기서 은 오래된 오차 샘플에 기하급수적으로 적은 가중치를 부여하는 "망각 계수"이다.

비용 함수는 계수 벡터 의 모든 항목 에 대해 편미분을 취하고 그 결과를 0으로 설정하여 최소화된다.

다음으로, 을 오차 신호의 정의로 대체한다.

방정식을 재배열하면 다음이 나온다.

이 형식은 행렬로 표현할 수 있다.

여기서 은 에 대한 가중 표본 공분산 행렬이며, 은 과  사이의 교차 공분산에 대한 등가 추정치이다. 이 표현을 기반으로 비용 함수를 최소화하는 계수를 다음과 같이 찾는다.

이것이 논의의 주요 결과이다.

 λ 선택 
가 작을수록 이전 샘플이 공분산 행렬에 기여하는 정도가 작아진다. 이는 필터가 최근 샘플에 더 민감하게 반응하게 하며, 이는 필터 계수의 더 많은 변동을 의미한다. 인 경우는 성장 윈도우 RLS 알고리즘이라고 한다. 실제로 는 일반적으로 0.98에서 1 사이로 선택된다.Emannual C. Ifeacor, Barrie W. Jervis. Digital signal processing: a practical approach, second edition. Indianapolis: Pearson Education Limited, 2002, p. 718 유형-II 최대 가능도 추정을 사용하여 데이터 집합에서 최적의 를 추정할 수 있다.Steven Van Vaerenbergh, Ignacio Santamaría, Miguel Lázaro-Gredilla "Estimation of the forgetting factor in kernel recursive least squares", 2012 IEEE International Workshop on Machine Learning for Signal Processing, 2012, accessed June 23, 2016.

 재귀 알고리즘 
이 논의는 비용 함수를 최소화하는 계수 벡터를 결정하는 단일 방정식을 산출했다. 이 섹션에서는 다음과 같은 형식의 재귀 해법을 도출하고자 한다.

여기서 는 시간 에서의 보정 계수이다. 재귀 알고리즘의 도출은 교차 공분산 을 로 표현하는 것으로 시작한다.
{|
|-
|
|
|-
|
|
|-
|
|
|}
여기서 는  차원 데이터 벡터이다.

마찬가지로 을 로 다음과 같이 표현한다.
{|
|-
|
|
|-
|
|
|}
계수 벡터를 생성하기 위해서는 결정론적 자기 공분산 행렬의 역행렬에 관심이 있다. 이 작업에는 우드버리 행렬 항등식이 유용하다.
{|
|-
|
|은 -by-
|-
|
|은 -by-1 (열 벡터)
|-
|
|은 1-by- (행 벡터)
|-
|
|은 1-by-1 단위 행렬
|}
우드버리 행렬 항등식은 다음과 같다.
{|
|-
|
|
|
|-
|
|
|
|-
|
|
|

|}
표준 문헌과 일치시키기 위해 다음을 정의한다.
{|
|-
|
|
|-
|
|
|}
여기서 이득 벡터 은 다음과 같다.
{|
|-
|
|
|-
|
|
|}
진행하기 전에 을 다른 형태로 가져올 필요가 있다.
{|
|-
|
|
|-
|
|
|}
왼쪽의 두 번째 항을 빼면 다음이 나온다.
{|
|-
|
|
|-
|
|
|}
의 재귀적 정의를 사용하면 원하는 형식이 따른다.

이제 재귀를 완료할 준비가 되었다. 논의된 바와 같이
{|
|-
|
|
|-
|
|
|}
두 번째 단계는 의 재귀 정의에서 따른다. 다음으로, 의 재귀 정의와 의 대체 형식을 통합하여 다음을 얻는다.
{|
|-
|
|
|-
|
|
|-
|
|
|}
을 사용하면 업데이트 방정식에 도달한다.
{|
|-
|
|
|-
|
|
|}
여기서 
는 사전(a priori) 오차이다. 필터가 업데이트된 후 계산된 사후(a posteriori) 오차와 비교해 보라.

이는 보정 계수를 찾았음을 의미한다.

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

 RLS 알고리즘 요약 
p차 RLS 필터에 대한 RLS 알고리즘은 다음과 같이 요약할 수 있다.
 매개변수:   필터 차수    망각 계수    를 초기화하는 값초기화:  , ,   여기서 는 랭크 의 단위 행렬계산:  에 대해.

에 대한 재귀는 대수 리카티 방정식을 따르므로 칼만 필터와 유사하다.Welch, Greg and Bishop, Gary "An Introduction to the Kalman Filter", Department of Computer Science, University of North Carolina at Chapel Hill, September 17, 1997, accessed July 19, 2011.

 격자 재귀 최소 제곱 필터(LRLS) 
격자 재귀 최소 제곱 적응 필터는 표준 RLS와 관련이 있지만 더 적은 산술 연산(N차)을 필요로 한다.Diniz, Paulo S.R., "Adaptive Filtering: Algorithms  and Practical Implementation", Springer Nature Switzerland AG 2020, Chapter 7: Adaptive Lattice-Based RLS Algorithms. https://doi.org/10.1007/978-3-030-29057-3_7 이는 더 빠른 수렴 속도, 모듈형 구조, 입력 상관 행렬의 고유값 확산 변화에 대한 비민감성 등 기존 LMS 알고리즘에 비해 추가적인 이점을 제공한다. 설명된 LRLS 알고리즘은 사후(a posteriori) 오차를 기반으로 하며 정규화된 형태를 포함한다. 유도는 표준 RLS 알고리즘과 유사하며 의 정의를 기반으로 한다. 전방 예측의 경우, 을 가장 최신 샘플로 하여 이다. 역방향 예측의 경우는 이며, 여기서 i는 예측하려는 과거 샘플의 인덱스이고, 입력 신호 는 가장 최근 샘플이다.Albu, Kadlec, Softley, Matousek, Hermanek, Coleman, Fagan "Implementation of (Normalised) RLS Lattice on Virtex" , Digital Signal Processing, 2001, accessed December 24, 2011.

 매개변수 요약 
는 전방 반사 계수
는 후방 반사 계수
는 순간 사후 전방 예측 오차를 나타냄
는 순간 사후 후방 예측 오차를 나타냄
는 최소 제곱 후방 예측 오차
는 최소 제곱 전방 예측 오차
는 사전 및 사후 오차 간의 변환 계수
는 피드포워드 승수 계수
는 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

 내용주 

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