Incremental Least Square Method

m개의 x와 y가 있을때 W를 구하는 문제이다.

문제를 수식으로 풀어써보면 아래와 같다.

원래 m개있던 샘플이 r개가 늘어났다. r개가 늘어남에 따라 X^tX와 X^tY의 변화를 살펴보면 아래와 같다.

추가된 r부분만 gram matrix을 만들어서 더해주면 된다.

이제 X^tX의 역함수 구하는 부분을 자세히 살펴보면 아래와 같다.

woodbury formula을 사용하면 추가되기전 m개의 샘플로 이미 구해진 V(m)을 그대로 사용 할 수 있다.

샘플이 추가되어 업데이트 할 때는 U을 계산할때만 역행렬을 구하야 한다.

그리고 최종 목표인 W(m+r)의 계산도 정리를 해보면 W(m)이 중복되서 나오는 것을 알 수 있다.

정리를 해보면 기존 V(m)과 W(m)을 이용해서 r개의 추가 샘플에 대해서 V(m+r)과 W(m+r)을 계산 할 수 있다.

특별히 r = 1 인 경우는 아래와 같다.