Introduction to Adaptive Filters

 

Estimator or filter

 

좁은 의미의 filter - 입력 신호가 있고 입력 신호에 대해서 각각의 샘플에 대해 weight를 줘서 곱하고 더해서 하나의 값의 출력을 만드는 것

넓은 의미의 Filter - 입력이 있고 출력이 있는 입출력 시스템

 

 

filter를 estimator로

filter란 noisy한 것에서 정보를 추출하기 위해서 디자인된 시스템

 

filter의 쓰임

1. Radar
2. Communications
3. Sonar
4. Navigation
5. Seismology
6. Biomedical engineering
7. Financial engineering (주가 예측_ 과거의 값을 예측하는 것은 의미가 없음)
8. Others

The Filtering Problem (2)

baseband 를 moduelation (주파수를 바꿔서 멀리 보내는 작업)-> demoduelation 필요

 

Two major kinds of impairments

1. Inter symbol interference(1~0 사이 값의 크기 차이가 나기 때문에 날라가게 되면 받는 쪽에서는 smooth 해짐 band가 limited 해지면서 서로의 영역을 침범) 신호 자체가 가지고 있는 
2. Noise

receiver단에서는 demoduel 할 때 estimator가 필요하다

 

1. The function of the receiverReliable estimate of the original message signal
2.  
3. ▫Estimation theoryStatistical in nature because of the unavoidable presence of noise or system errors 

 

Three Basic Kinds of Estimation

 

과거와 현재의 정보를 가지고 이전 t' 정보만 예측할 수 있음  ->  delay가 항상 생길 수 밖에 없음

실시간성이 중요한 경우 예측 불가능

 

최소한의 delay를 가지게 하는 것

 

Linear Optimum Filters (1)

Linear filter

The filtered, smoothed, or predicted quantity at the output of the filter is a linear function of the observations applied to the filter input.

입력데이터의 통계치를 씀

Linear filtering problem

Assumption

The availability of certain statistical parameters (i.e., mean and correlation functions)

 

Requirement

Design a linear filter with the noisy data as input so as tominimize the effects of noise at the filter output according to some statistical criterion

출력의 noise가 최소화되는 linear filter를 디자인

 

Error signal

The difference between some desired response and the actual filter output

차이가 에러가 됨

E|d(n)-y(n)|^2

두 개 사이에 차이가 커지면 커질수록 에러가 커짐

y가 d를 쫓아가야함 -> minimize 함

 

Useful approach to this filter-optimization problem

Minimize the mean-square value of the error signal

Solution for stationary inputs

Wiener filter

Optimum in the mean-square error sense

 

Solution for nonstationary inputs

Kalman filter

Time-varying form

 

Adaptive Filters (1)

 

 

The design of a Wiener filter(처리된 데이터의 통계치의 priori info를 알고있어야함)

Require a priori information(통계치의 실제 값) about the statistics of the data to be processed

Optimum only when the statistical characteristics of the input data match the a priori information

통계치의 데이터와 priori info가 일치해야 최적화됨

mean value라고 하는 것은 우리가 얻게 되는 유한한 데이터를 가지고는 알 수 없음

mean value는 그 데이터에 대한 완벽한 정보를 알고 있을 때만 알 수 있는 값

실제로는 유한한 sample 로 mean을 추정하는 것,  같을 수도 있고 다를 수도 있음 => 중요한 것은 error 가 얼마나 큰지

 

 

“Estimate(추정하는 과정을 얘기 함) and plug”(2stage filter) procedure(priori info 가 없을 때)

priori info에 해당하는 통계적 특성에 해당하는 것을 추정할 수 있어야 함

추정 -> plug(filter paramater를 계산하기 위해)

Two-stage process whereby the filter first estimates the statistical parameters of the relevant signals and then plugs the results so obtained into a nonrecursiveformula for computing the filter parameters

Requires excessively elaborate and costly hardware

한번에 계산(딱 두번만 계산)

우리에게는 기회가 한 번만 있기때문에 통계치도 정확하게 추정 ㅔㅁㄱeh wjdghkrgkrp cnwjd

data를 많이 모아서 통계치를 기반으로 para를 어떻게 바꿀 건지 최대한 완벽하게 해야함

한 번에 할 때 계산량이 엄청나게 큼 => 부담이  큼 => 시간과 비용이 많이 듦

 

달가운 상황은 아니기때문에 아래를 고안

 

Adaptive filter(filter값을 추정하는 알고리즘을 만듦)

Self-designingRely for its operation on a recursive algorithm

Initial conditions(초기값을 어떻게 줄 것인가, 적절-> 수렴 빨라짐/ 엉뚱-> 느려지거나 수렴 불가능)

In a stationary environment,

Converge to the optimum Wiener solution in some statistical sense(알고리즘을 잘 디자인하면)

In a nonstationary environment,Track time variations in the statistics of the input data

시간에 따라 통계치가 계속 바뀌면 미래를 예측할 수 없음

현재까지만 추정 = > 얼마나 빨리 따라갈 수 있냐가 중요

 

Update from one iteration to the next

Nonlinear systemIn the sense that it does not obey the principle of superposition

Linear –whenever its parameters are held fixed(입력이 들어올 때 출력이 구해져있음)

입력이 주어졌을 때, 출력을 구하는 과정은 linear system인데,

거기에서 error를 이용해서 다시 filter의 coefficient를 바꿔줌 ->  adapted => non-linear가 됨

전체 system 을 따지면 non linear=>superposition만족하지 않음

 

 

 

Factors for the choice of one algorithm over another (1)

여러가지 알고리즘을 선택하는 기준이 뭐냐

아래 특징들을 이용

Rate of convergence(수렴 척도/얼마나 빨리 수렴하느냐) 반복횟수

The number of iterations to converge close enough to the optimum Wiener solution in the mean-square error sense

 

Misadjustment

(adapted 를 위해 아주 완벽한 알고리즘을 써도 data하나에 대해 mean에 영향을 주므로 값이 지속적으로 바뀜 => 값에 따라가길 원하지만 이 필터를 쓰면 값이 계속 바뀜)

약간의 차이가 나길 원하지만 값이 계속 over남

Quantitative measure of deviation from the minimum mean-square error produced by the Wiener filter

Wiener filter를 이용해서 filter의 값을 찾았을 때,

ideal으로부터 차이가 있으므로, mean-square error가 있음

(충분히 따라갔다 쳐도)

계속 영향을 받으므로 주변(언저리)을 멤도는 추정치를 찾음

계속 왔다갔다 하므로 에러가 커짐

이건 이해가 잘...

 

Tracking(얼마나 빨리 따라가느냐)

빨리 따라가는 것은 step 을 크게 하는 것 => 수렴이 되면서 error가 크게남

step을 줄이면 수렴이 느려짐

Track statistical variations in a nonstationary environment

Influenced by two contradictory features

Rate of convergence

Steady-state fluctuation

초기 => 빠르게, 어느정도 되었으면 step을 줄여줌

 

Robustness

param을 추정했을 때, 어떤 요인에 의해 갑자기 커지거나 작아졌을 때,

다시 ideal한 value로 잘 찾아올 수 있냐의 성질

 

Adaptive Filters (4)

 

Factors for the choice of one algorithm over another (2)

Computational requirements

얼마나 계산이 많이 필요하나

The number of operations and the size of memory locations

 

Structure

정보가 어떻게 흘러가지는 구조를 어떻게 만들 것인가

The structure of information flow

Determine the manner where it is implemented in hardware form

하드웨어 구현 방법론 까지

Modularity, parallelism, or concurrency

 

Numerical properties

고유한 특성을 이야기함

실제 필터에 대해 adaptive하므로 ㄱㅖ속 누적이 되어 에러가 커짐 => 발산 해버림

이런 문제가 생기지 않아야 함

Numerical stability

An inherent characteristic of an adaptive filtering algorithm

Numerical accuracy

Determined by the number of bits

 

The operation of a linear adaptive filtering algorithm

2단계가 필요함

1. 

A filtering process

Produce an output in response to a sequence of input data

2.

An adaptive process

메카니즘에 대한 process

Provide a mechanism for the adaptive control of an adjustable set of parameters used in the filtering process

 

Linear Filter Structures

 

The impulse response of a linear filter

Determine the filter’s memory

Finite-duration impulse response (FIR) filter

Finite memory

 

Infinite-duration impulse response (IIR) filter

Infinitely long, but fading, memory

간접적으로 구현

 

Linear Filters with Finite Memory (1)

입력에 delay를 주고

weight를 주고 다 더해줘서 출력을 만들어냄

y(n)= sum(n=1~N) w_n^* w(n-m)

현재로부터 과거까지 sum해서 출력을 만드는 과정

과거의 데이터를 저장하고 있어야 함

M-1개의 메모리를 저장하고 있어야 함

 

 

Transversal filter (tapped-delay line filter or FIR filter)

Three basic elements

A unit-delay element, a multiplier, and an adder

 

Filter order

The number of delay elements(M-1 차 filter order)

 

 

위의 문제는

parell하는 과정이 쉽지 않음(순차적으로 밀어야 하므로)

보완) cell의 형태로 빠르게 계산하는 방식을 택함

그런 게 있다는 정도만 알고 넘어감

 

 

unit으로 구현(이런 게 있음)

 

Linear Filters with Infinite Memory (1)

 

 

IIR filter

The inclusion of feedback paths

 

The presence of feedback

Make the duration of the impulse response of an IIR filter infinitely long

Potential instability =>  치명적인 약점!!

coeff를 잘못 주면 발산하게 됨

발산하지 않게 잘 조절해줘야함

branch가 없다면 기존과 똑같지만

공통으로 쓰는 부분을 공유하므로 두 가지로 자를 수 있음

왼쪽은 feedback filter - IIR filter를 만드는 key

오른쪽은 transpose filter

 

feedback이 되면 M-1에 대한 출력이 다시 되돌아 옴으로 무한한 출력이 가능하게 됨 

 

 

 

unit delay가 아니므로 분모가 있는 filter를 쓰므로

실제로는

이것이 feedback역할을 해서 IIR

 

Stochastic Gradient Approach

Tapped-delay line or transversal filter

The cost function (the index of performance)

Mean-square error

 

The optimum Wiener solution

The tap weights corresponding to the minimum point of the error-performance surface

 

To develop a recursive algorithm(나중에 자세하게 나옴)

Use an iterative procedure to solve the Wiener-Hopfequations based on the method of steepest descent 

 

 

The Least-Mean-Square (LMS) Algorithm

 

The method of steepest descent (batch process)

데이터가 충분히 누적이 된 다음 통계치를 계산하는 방식

입력이 나올 때 출력이 나오길 원하므로 LMS 알고리즘 사용

Require the use of a gradient vector, the value of which depends on two parameters: the correlation matrix of the tap inputs and the cross-correlation vector between the desired response and the same tap inputs

수식을 통해서 얻어보는 게 중요

mean 벡터의 추정치를 이용

 

The LMS algorithm (sample마다 gradient추정) on-line 방식

가장 기본적인 알고리즘

Use instantaneous values(대략적으로 추정하는 알고리즘) for these correlations to derive an estimate for the gradient vector => 하나씩 업데이팅 해나감

Simple and yet capable of achieving satisfactory performance under the right conditions

Major limitations 기본적 한계

A relative slow rate of convergence

A sensitivity to variations in the condition number of the correlation matrix of tap inputs

condition number공간이 얼마나 왜곡돼있느냐(찌그러져 있느냐)=> 여기에 직접적인 영향을 받음

cost를 등고선으로 만들고 원형에 가깝다하면 처음에 gradient방향이 minimum과 비슷하게 쫓아갈 수 있지만,

등고선이 찌그러져 있을 때, 출발선에 따라 수렴하기 위한 노력이 달라짐

step을 적게 줄 수 밖에 없는데, 아주 여러번 반복해야 minimum에 수렴

 

Least-Squares Estimation

매번 추정하니 느리다 => sample을 약간씩 모아서 mini batch하듯이 data량을 가지고 한 번씩 업데이트

Method of least squares

Minimize a cost function or an index of performance that is defined as the sum of weighted error squares

Formulated with block estimation or recursive estimation

Recursive least-squares (RLS) estimation 계산을 더 빠르게 할 수 있지만 Least-Squares효과를 낼 수 있음 =>  앞으로 배울 것

Kalman filter 을 써서 업데이트해나가면서 추정

May be viewed as a special case of Kalman filtering

 

RLS Family

이런게 있다 정도만 알고 넘어감

The standard RLS algorithmBased on the matrix inversion lemma

Limitations

The lack of numerical robustness

Excessive computational complexity

 

Square-root RLS algorithms

Based on QR-decomposition of the incoming data matrix

Decomposed by the Householder transformation or the Givens rotation–numerically stable and robust

 

Fast RLS algorithms: O(M^2) -> O(M)

Exploit the inherent redundancy in the Toeplitz structure of the input data matrix through the use oflinear least-squares prediction in both the forward and backward directions

 

Tracking and Choosing

Tracking behavior

 

Stochastic gradient algorithm

Model independent

 

RLS algorithms

Model dependent

Their tracking behavior may be inferior to that of a member of the stochastic gradient family, unless care is taken to minimize the mismatch between the mathematical model on which they are based and the underlying physical process responsible for generating the input data.

 

How to choose an adaptive filter

Three important issues that require attention

Computational cost, performance, and robustness

이걸 보고 어떤 것을 쓸지 골라야 함