Game Engineering 3

Jacobian Inverse Methods for IK

목표로 하는 것은 Jacobian 의 inverse를 계산하기!

SVD intro

• SVD (Singular Value Decomposition)
• matrix의 SVD는 3개의 matrix로 factorization 되는 것을 말한다.

Matrix Factorization

• matrix 계산을 쉽게하기 위해서 lower triangle과 upper triangle로 나누는 방식

Transpose

Partitioned Matrix

• matrix의 column이나 row끼리 나누는 것
  $B = \begin{bmatrix} 1 & 3 & 5 \\ 2 & 4 & 6 \\ \end{bmatrix}$
  column 기준으로 나눈 경우
  $B=\begin{bmatrix} u_1, u_2,u_3\end{bmatrix}$
  $u_1 =\begin{bmatrix}1\\2\end{bmatrix}$
  $u_2 =\begin{bmatrix}3\\4\end{bmatrix}$
  $u_3 =\begin{bmatrix}5\\6\end{bmatrix}$

Eigenvalue & Eigenvector

• vector $u$ , scalar $\lambda$, linear transformation matrix $A$
• $\lambda u$ 는 방향이 같지만, 크기가 다른 벡터
• $A$의 eigen vector는 $u$ ($u$는 0이 아님)
• $Au = \lambda u$ 식에서 $\lambda$는 eigen value $u$는 eigen vector이다.
• eigen vector는 선형변환을 해도 방향이 변하지 않는 벡터를 말한다.

Eigen Decomposition of a Matrix

• $AP = PD$
• matrix $A$ : eigen value $\lambda_1, \lambda_2,..$로 구성
• 위의 eigen value와 상응되는 eigen vector를 $X_1, X_2, ..$
• $P = [X_1, X_2, ...X_k]$ , $D$는 성분이 $\lambda$의 모음인 diagonal 행렬
• 그 결과 AP = PD가 된다.
  • $AP$의 각 성분은 $AX_1, AX_2$, ...이고, $PD$의 각 성분은 $\lambda_1X_1, \lambda_2X_2, ...$ 이므로
• $AP = PD$ -> $A = PDP^{-1}$
  • $A^2 = (PDP^{-1})(PDP^{-1})$
  • $= PD^2P^{-1}$
  • => $A^n = PD^nP^{-1}$
  • => $A^{-1} = PD^{-1}P^{-1}$

Singular Value

• singular value : $A^TA$의 eigen value의 square root
• singular value denote : $\sigma_1, ...\sigma_i$
• $i$는 matrix A 의 rank를 말한다.
• $det(A^TA - \lambda I)=0$이 되는 $\lambda$값의 square root가 singular value

Rank

• 특정 matrix에 있어서 linearly independent 한 column의 수
• linearly independent : matrix의 어떤 column성분을 다른 column들로 나타낼 수 없는 경우
• row reduction을 통해 rank를 구할 수 있다.
  • row reduction 이후 non-zero인 row의 수가 rank 이다.

SVD

• $A = U\Sigma V^*$
  • $U$ : m x m complex unitary matrix
  • $\Sigma$ : m x n rectangular diagonal matrix
  • $V$ : n x n complex unitary matrix
• 실수 공간에서 $A = U\Sigma V^T$ 로 나타낼 수 있다.
  • $AA^T$의 eigen vector로 $U$의 columns 구성
    -> left singular vectors of A
  • $A^TA$의 eigen vector로 $V$의 columns 구성
    -> right singular vectors of A
  • $A^TA$ 혹은 $AA^T$의 singular value 로 구성된 diagonal matrix -> $\Sigma$
• unitary matrix 특성
  • $U^*U = UU^* = UU^{-1} = I$
• SVD의 기하학적 의미
  • eigen value는 공간상에서 얼만큼 땡길지에 대한 값
  • eigen vector는 공간상에서 얼만큼 땡길지에 대한 방향

calculate example

일 때

$det(A^TA-\lambda I) = 0$을 구하면
eigen vector $v_1 = \begin{bmatrix} 0.5\\1 \end{bmatrix}$, $v2 = \begin{bmatrix} -1\\1 \end{bmatrix}$
singular value $\sigma_1 = 2\sqrt{10}$,$\sigma_2 = \sqrt{10}$

...

Moore-Penrose inverse

• pseudo inverse를 구하는 가장 유명한 방법 : $A^\dagger$
• pseudo inverse : for best fit(least squares) solution

Pseudo-Inverse and Least Squares

• Least Squares : overdetermined system 을 풀기 위한 방법
  -> 관측값이 너무 많은 경우 하나의 식으로 수렴하기 어렵다
• 선형 방정식
  • 관측된 모션은 실제로는 곡선이지만, dt라는 짧은 시간동안 직선운동을 한다고 가정하여 $y = dx + c$의 식으로 표현할 수 있다.
    • 세가지 점을 관측했다고 했을 때 -> $c+dx_1 = y_1, c+dx_2 = y_2, c+dx_3 = y_3$
      1) 관측된 세개의 점이 error값이 없다면 그냥 방정식의 값을 풀 수 있다.
      2) 관측된 점 중 error값이 있다면, 방정식을 못풀게 된다. -> SSE로 풀기
  • SSE : 각 방정식에 error 값을 더해주고 error 값을 최소화 하는 방식
    -> $c+dx_1+e_1 = y_1, c+dx_2+e_2 = y_2, c+dx_3+e_3 = y_3$
    -> $SSE = (c+dx_1-y_1)^2+(c+dx_2-y_2)^2+(c+dx_3-y_3)^2$
    -> SSE를 0에 가깝도록 만드는 방식으로 풀기
• matrix
  • 위에서 언급한 내용을 matrix 형태로 바꾸면 $y=Ax+e$ 형태로 바꿀 수 있고, 목표는 $e^Te$를 최소화 (0에 가깝게) 하는 것이다.
  • $min_xe^Te = (y-Ax)^T(y-Ax)$
    -> $min_xe^Te = y^Ty-2x^TA^Ty-x^TA^TAx$
    -> $\frac{\partial}{\partial x}e^Te = -2A^Ty+2A^TAx=0$ 로 표현된다. ($\frac{\partial}{\partial b}b^TX^TXb=2XTXb$ 에 의해서)
    => 결론적으로 $A^TAx=A^Ty$ -> $x=(A^TA)^{-1}A^Ty$ -> $x = A^{-1}y$
  • 결론
    • A의 pseudoinverse 를 $A^\dagger = (A^TA)^{-1}A^T$ 로 표현할 수 있다

Pseudo-Inverse and SVD

• 쉬운 상황 : $\Sigma$ 가 m x m diagonal matrix 인 경우
  • $A = U\Sigma V^T$ -> $A^{-1}=V\Sigma^{-1} U^T$
  • $\Sigma$의 inverse는 각 singular value로 이루어진 값들을 역수를 취해주면 되기 때문에 계산하기 쉽다.
• 어려운 상황 -> Pseudo-Inverse 사용 : $\Sigma$가 m x n 인 경우
  • 이 경우 $\Sigma$의 inverse에서 분모에 0이 들어가버린다.
    -> Destroy (차원 이동에 있어서 손실이 생긴다)
    -> 0이 곱해지기 때문에
    -> inverse를 구할 수 없다
  • 그럼 손실이 되지 않게 할 수 있지 않을까? -> pseudo inverse!!
    -> $A^\dagger = V\Sigma^ \dagger U^T$

Jacobian Pseudo-inverse

• 이 방식을 사용할 때는 matrix가 square가 아니거나 invertible 한 경우
• $J\Delta \theta = \vec{e}$ 의 least square의 값을 구할 때 가장 좋은 해결책이다.
  • $J^{-1}\vec{e}=\Delta \theta$ 의 $J^{-1}$를 구하는 것이 목표!
  • 하지만 $J^{-1}$은 없는 경우도 있다. 그 경우 $J^\dagger$로 계산하기!!
• Jacobian 을 푸는 여러가지 경우..
  1) $m\ge n$이고, $J$가 full column rank인 경우 $J^TJ$ 계산 => moore-penrose
  ex) $J\Delta \theta = \vec{e}$ -> $J^TJ\Delta=J^T\vec{e}$ -> $\Delta\theta = (J^TJ)^{-1}J^T\vec{e}$
  -> $(J^TJ)^{-1}J^T$ 는 $J^\dagger$
  2) $m<n$이고 $J$가 full row rank인 경우 $JJ^T$ 계산 => moore-penrose
  3) $J$가 full rank가 아닌 경우 SVD를 통해 $J^\dagger$ 계산

Damped Least Squares (DLS)

• least square의 경우 singularity가 0에 가까이 가게 되면 오류가 생긴다는 문제가 생긴다!!
• 이 문제를 해결하기 위해서 $\frac{1}{\sigma}$ 대신에 $\frac{1}{\sigma + \lambda}$로 계산해준다. 이 $\lambda$ 는 사람이 정해주어야 하는 값이다.
• $\lVert J\Delta\theta - \vec{e} \rVert ^{2}+\lambda^2\lVert \Delta \theta \rVert^2$ -> damping을 적용한 식

Pseudo-Inverse Damped Least Squares

• $J^T(JJ^T+\lambda ^2 I)^{-1} = \sum_{i=1}^r\frac{\sigma_i}{\sigma_i^2+\lambda^2}v_iu_i^T$
  -> $J^\dagger=\sum_{i=1}^r\sigma_i^{-1}v_iu_i^T$
  -> 원래 pseudo inverse 식에서 $\lambda^2I$를 damping하는 값으로 억지로 끼워넣어서 구한 식
  
• 그림에서 보는 것 처럼 least square는 0에 가까워질수록 해가 발산해버리기 때문에 문제가 발생한다.
• damped least square는 $\lambda$라는 값을 통해 0에 가까운 값들을 억지로 변형시켜서 안정된 해를 구하는 것