positive definiteness of a matrix

Semi-positive definiteness

행렬이 semi-positive definite라는 것은 그 행렬이 실수 대칭 행렬 (또는 적어도 그와 같은 특성을 갖는 행렬)이면서, 모든 eigenvalue가 0 이상이라는 것을 의미합니다.

구체적으로, 행렬 $A$가 semi-positive definite라면, 그 행렬의 모든 고유값 (eigenvalue) $\lambda_i$에 대해서 $\lambda_i \geq 0$ 입니다.

즉, semi-positive definite 행렬의 모든 eigenvalue는 0 이상이 되며, 이는 모든 선형 독립적인 벡터 $x$에 대하여 $x^T A x \geq 0$이 성립함을 의미합니다.

부동소수점 오차

컴퓨터의 부동 소수점 연산은 항상 미세한 오차를 동반합니다. 이러한 오차는 행렬 연산에서도 나타날 수 있으며, 특히나 eigenvalue와 같은 연산에서는 이런 미세한 오차가 종종 나타납니다. 이러한 미세한 오차로 인해, 이론적으로는 semi-positive definite 행렬이지만 컴퓨터 상에서는 미세한 음수의 eigenvalue (e.g. -8.10E-15)를 가지게 될 수 있습니다.

이러한 상황에서 $x^T A x$의 값이 음수로 계산되는 경우가 발생하면, 이는 컴퓨터의 계산 오차 때문입니다. 실제로는 $x^T A x \geq 0$이 성립해야 하지만, 컴퓨터의 미세한 오차 때문에 음수가 나올 수 있습니다.

이차 형식

임의의 벡터 $x$에 대해서, $x^T A x$는 행렬 $A$의 이차 형식(quadratic form)입니다.

이차 형식 $x^T A x$를 eigenvalue decomposition을 이용해서 분석하면, 행렬 $A$가 semi-positive definite이므로 $A$의 모든 eigenvalue들은 non-negative입니다.

$\lambda$를 $A$의 가장 작은 eigenvalue라고 하겠습니다.
이제, $A$의 eigenvalue와 eigenvector를 $\lambda_i$와 $v_i$라고 할 때, 임의의 벡터 $x$는 $A$의 eigenvectors로 나타낼 수 있습니다:

$$
x = \sum_i c_i v_i
$$

이를 $x^T A x$에 대입하면:

$$
x^T A x = \sum_i \sum_j c_i c_j v_i^T A v_j
$$

$$
= \sum_i \sum_j c_i c_j v_i^T \lambda_j v_j
$$

$$
= \sum_i \sum_j c_i c_j \lambda_j (v_i^T v_j)
$$

$$
= \sum_i c_i^2 \lambda_i
$$

이때 $v_i^T v_j$는 eigenvectors의 직교성을 사용하여 계산하였습니다. 이 결과에서 볼 수 있듯이, 각 항의 기여는 $c_i^2 \lambda_i$이며, 각 $\lambda_i$는 $\lambda$ 이상입니다.

따라서 $x^T A x$는 $\lambda \sum_i c_i^2 = \lambda ||x||^2$ 이 됩니다.

수치적 계산을 위한 정규화

앞서 설명했듯 이론적으로 semi-positive definite가 증명된 행렬을 계산할 때, 수치적인 이유로 음의 eigenvalue가 나타나기도 합니다. 이를 강제로 수정하려면 몇 가지 접근 방법을 사용할 수 있습니다.

1. Eigenvalue Decomposition 방법:
   • 행렬 $A$의 eigenvalue 및 eigenvector를 계산합니다.
   • 얻은 eigenvalue 중 음수인 것들을 0으로 설정합니다.
   • 수정된 eigenvalue와 원래의 eigenvector를 사용하여 행렬 $A$를 재구성합니다.

import numpy as np

# Eigenvalue decomposition
eigenvalues, eigenvectors = np.linalg.eigh(A)

# Set negative eigenvalues to 0
eigenvalues[eigenvalues < 0] = 0

# Reconstruct the matrix
A_new = eigenvectors @ np.diag(eigenvalues) @ eigenvectors.T

2. Regularization 방법:
   일반적으로 행렬 $A$에 작은 값을 가진 identity 행렬을 더해 semi-positive definite를 강제로 만드는 방법이 있습니다.

epsilon = 1e-10
I = np.identity(A.shape[0])
A_new = A + epsilon * I

이러한 방법들은 실제로 행렬 $A$의 속성을 변경하므로, 결과를 해석할 때 주의가 필요합니다. 기본적으로 원래의 문제와 수치적인 표현 사이에 항상 trade-off가 있으며, 수정된 행렬이 원래의 문제 의도를 여전히 잘 반영하는지 확인해야 합니다.