Schur Complement (슈어 보상행렬)

Schur Complement (슈어 보상행렬)

2024, Aug 01    


선형대수학 글 목차


  • 참조 : http://ranking.uos.ac.kr/blog_page/post_src/schur-comp.pdf
  • 참조 : https://gaussian37.github.io/math-la-positive_definite_matrix/
  • 참조 : https://gaussian37.github.io/math-la-block_matrix_multiplication/


  • 이번 글에서는 행렬 연산의 효율성을 향상시키는 방법인 Schur Complement (슈어 보상행렬)에 대하여 알아보도록 하겠습니다.
  • Schur Complement (슈어 보상행렬)은 행렬 AA 가 4개의 블록 행렬의 2×22×2 형태 조합으로 구성되었을 때, 행렬 AA 의 역행렬을 분할된 블록 행렬들을 이용하여 구할 때 사용됩니다. 분할된 행렬을 이용하므로 효율적인 연산에 장점이 있습니다. 추가적으로 이 행렬이 Positive Definite Matrix 또는 Positive Semi-Definite Matrix 일 때, 가지는 성질들을 이용하는 방법까지 다루어 보도록 하겠습니다.


목차



Schur Complements


  • 다음과 같이 n×nn×n 크기의 행렬을 2×22×2 블록 행렬 MM 으로 표현해 보도록 하겠습니다.


  • M=[ABCD]M=[ABCD](1)
  • A : p×p matrixA : p×p matrix
  • D : q×q matrixD : q×q matrix
  • n=p+qn=p+q
  • B : p×q matrixB : p×q matrix
  • C : q×p matrixC : q×p matrix


  • 블록 행렬 MM 을 이용하여 선형연립방정식을 구성하면 다음과 같습니다.


  • [ABCD][xy]=[cd][ABCD][xy]=[cd](2)
  • ⇒{Ax+By=cCx+Dy=d⇒{Ax+By=cCx+Dy=d(3)


  • 만약 D−1D−1 가 존재한다면 식 (3)에 가우스 소거법을 적용하면 다음과 같이 식을 변경할 수 있습니다.


  • y=D−1(d−Cx)y=D−1(d−Cx)(4)
  • Ax+By=Ax+B(D−1(d−Cx))=cAx+By=Ax+B(D−1(d−Cx))=c(5)
  • (A−BD−1C)x=c−BD−1d(A−BD−1C)x=c−BD−1d(6)


  • 만약 행렬 (A−BD−1C)(A−BD−1C) 가 역행렬이 있다면 x,yx,y 의 해는 다음과 같습니다.


  • {x=(A−BD−1C)−1(c−BD−1d)y=D−1((d−C(A−BD−1C)−1)(c−BD−1d)){x=(A−BD−1C)−1(c−BD−1d)y=D−1((d−C(A−BD−1C)−1)(c−BD−1d))(7)


  • 이 때, (A−BD−1C)(A−BD−1C) 을 행렬 MM 의 블록 행렬 DD 의 Schur Complement (슈어 보상행렬)이라고 합니다. 보상행렬의 뜻은 더 큰 행렬 내의 부분 행렬이라는 의미입니다.
  • 식 (4)에서는 yy 를 먼저 정리한 다음 식 (5)에서 대입하는 방식을 이용하였습니다. 만약 xx 에 대하여 먼저 정리한 다음 대입하는 방식을 적용하면 같은 방식으로 Schur Complement를 구할 수 있으며 행렬 MM 의 블록 행렬 AA 의 Schur Compement인 (D−CA−1B)(D−CA−1B) 를 얻을 수 있습니다.
  • 이번 글에서는 식 (4)에서 yy 를 먼저 정리한 방식으로 계속 식을 전개해 보도록 하겠습니다.


  • 그 다음으로 식 (7)의 우변을 c,dc,d 로 묶어서 표현해 보도록 하겠습니다.


  • {x=(A−BD−1C)−1c−(A−BD−1C)−1BD−1dy=−D−1C(A−BD−1C)−1c+(D−1+D−1C(A−BD−1C)−1BD−1)d{x=(A−BD−1C)−1c−(A−BD−1C)−1BD−1dy=−D−1C(A−BD−1C)−1c+(D−1+D−1C(A−BD−1C)−1BD−1)d(8)


  • 앞에서 식 (2)에서 행렬 MM 의 역행렬을 이용하여 표현하면 다음과 같습니다.


  • [xy]=[ABCD]−1[cd][xy]=[ABCD]−1[cd](9)


  • 식 (9) 에서 M−1M−1 의 성분만 추출하기 위하여 식 (8)을 다음과 같이 정리할 수 있습니다.


  • [xy]=[ABCD]−1[cd]=[(A−BD−1C)−1−(A−BD−1C)−1BD−1−D−1C(A−BD−1C)−1(D−1+D−1C(A−BD−1C)−1BD−1)][cd][xy]=[ABCD]−1[cd]=[(A−BD−1C)−1−(A−BD−1C)−1BD−1−D−1C(A−BD−1C)−1(D−1+D−1C(A−BD−1C)−1BD−1)][cd](10)
  • [ABCD]−1=[(A−BD−1C)−1−(A−BD−1C)−1BD−1−D−1C(A−BD−1C)−1(D−1+D−1C(A−BD−1C)−1BD−1)][ABCD]−1=[(A−BD−1C)−1−(A−BD−1C)−1BD−1−D−1C(A−BD−1C)−1(D−1+D−1C(A−BD−1C)−1BD−1)](11)


  • 식 (11)의 행렬을 식 (12), 식 (13) 순서로 분해할 수 있습니다.


  • [ABCD]−1=[(A−BD−1C)−10−D−1C(A−BD−1C)−1D−1][I−BD−10I]
  • [ABCD]−1=[I0−D−1CI][(A−BD−1C)−100D−1][I−BD−10I]


  • 식 (13)을 이용하여 행렬 M 을 구해보면 다음과 같습니다.


  • [ABCD]=([I0−D−1CI][(A−BD−1C)−100D−1][I−BD−10I])−1=[I−BD−10I]−1[(A−BD−1C)−100D−1]−1[I0−D−1CI]−1
  • [I−BD−10I]−1=(I⋅I−(−BD−1)⋅0)−1[IBD−10I]=[IBD−10I]∵ inverse matrix of 2 by 2 matrix.
  • [(A−BD−1C)−100D−1]−1=[(A−BD−1C)00D]∵inverse matrix of diagonal matrix.
  • [I0−D−1CI]−1=(I⋅I−0⋅(−D−1C))−1[I0D−1CI]=[I0D−1CI]∵ inverse matrix of 2 by 2 matrix.


  • 식 (15), 식 (17)에서는 2×2 행렬의 역행렬을 구하는 방식에 따라 각 행렬의 역행렬을 구한 내용입니다. 식 (16)에서는 대각 행렬의 역행렬을 구한 것으로 대각 성분 각각에 역수 (역행렬)을 적용한 결과로 이해할 수 있습니다.
  • 이와 같은 방식을 통해 행렬 M 은 식 (14)와 같이 블록 행렬 표현 방식을 통해 표현할 수 있습니다. 식 (14)의 식과 같이 표현하기 위해서는 행렬 D−1 의 존재 여부 확인만을 필요로 합니다.


  • 반면 식 (4) 대신에 x 에 대하여 먼저 정리한 다음 대입하는 방식을 적용하면 같은 방식으로 Schur Complement를 구한다면 행렬 M 과 M−1 는 다음과 같이 구할 수 있습니다.


  • [ABCD]=[I0CA−1I][A00D−CA−1B][IA−1B0I]
  • [ABCD]−1=[A−1+A−1B(D−CA−1B)−1CA−1−A−1B(D−CA−1B)−1−(D−CA−1B)−1CA−1(D−CA−1B)−1]


  • 이 경우에는 식 (19)에서 확인할 수 있는 것과 같이 행렬 A−1 의 존재 여부 확인만을 필요로 합니다.


  • 만약 A−1,D−1 가 모두 존재하여 각 Schur Complement인 A−BD−1C 와 D−CA−1B 의 역행렬이 존재한다면 식 (11)과 식 (19) 의 값을 통해 다음 관계식을 확인할 수 있습니다.


  • (A−BD−1C)−1=A−1+A−1B(D−CA−1B)−1CA−1
  • (D−CA−1B)−1=D−1+D−1C(A−BD−1C)−1BD−1


  • 따라서 Schur Complement인 A−BD−1C 와 D−CA−1B 만으로 행렬을 정리하면 다음과 같이 정리할 수 있습니다.


  • [ABCD]−1=[(A−BD−1C)−1−A−1B(D−CA−1B)−1−(D−CA−1B)−1CA−1(D−CA−1B)−1]


행렬 M−1 정리


  • 지금까지 살펴본 내용을 한번 정리하고 넘어가겠습니다.


  • M=[ABCD]
  • A : p×p matrix
  • D : q×q matrix
  • n=p+q
  • B : p×q matrix
  • C : q×p matrix


  • Case 1 : D is invertible.


  • [ABCD]−1=[(A−BD−1C)−1−(A−BD−1C)−1BD−1−D−1C(A−BD−1C)−1(D−1+D−1C(A−BD−1C)−1BD−1)]=[I0−D−1CI][(A−BD−1C)−100D−1][I−BD−10I]


  • Case 2 : A is invertible.


  • [ABCD]−1=[A−1+A−1B(D−CA−1B)−1CA−1−A−1B(D−CA−1B)−1−(D−CA−1B)−1CA−1(D−CA−1B)−1]=[I−A−1B0I][A−100(D−CA−1B)−1][I0−CA−1I]


  • Case 3 : A,D are invertible.


  • [ABCD]−1=[(A−BD−1C)−1−A−1B(D−CA−1B)−1−(D−CA−1B)−1CA−1(D−CA−1B)−1]=[S−11−A−1BS−12−S−12CA−1S−12]
  • S1=A−BD−1C : (Schur Complement).
  • S2=D−CA−1B : (Schur Complement).


A Characterization of Symmetric Positive Definite Matrices Using Schur Complements


  • 행렬 M 이 대칭 행렬 (Symmetric)이라면 A,D 블록 행렬 각각이 대칭 행렬이고 C=BT 가 성립하니다. 따라서 M 을 다음과 같이 표현할 수 있습니다.


  • M=[ABCD]=[ABBTD]=[IBD−10I][A−BD−1BT00D][IBD−10I]


  • 식 (28) 에서 행렬 M 은 block-diagonal matrix가 됩니다. A−BD−1BT 가 Schur Complement이고 대칭 행렬의 성질을 가집니다.
  • 추가적으로 행렬 M 이 Positive Definite Matrix의 성질을 가지기 위한 몇가지 조건들에 대하여 알아보도록 하겠습니다.


  • 작성중…


Pseudo-Inverses



A Characterization of Symmetric Positive Semidefinite Matrices Using Schur Complements




선형대수학 글 목차


Twitter Facebook Google+
# Schur Complement # 슈어 보상행렬