[Math] EVD 및 SVD로 $\textbf{x}^\top A^\top A\textbf{x}$의 최소값 및 해 구하기: Total Least Squares

Vector $\mathbf{x}$ 와 Matrix $A$가 주어졌을 때,
$\mathbf{x}^\top A^\top A \mathbf{x}$의 minimum (or lower bound)를 구하는 방법에 대해
Singular Value Decomposition(SVD)와 Eigenvalue Decomposition(EVD)을 이용하는 방법.

 

$\underset{\mathbf{x}}{\text{argmin }}\mathbf{x}^\top A^\top A\mathbf{x}$는
Total Least Squares 등에서 많이 애용되는 형태의 최소화 문제임.

---

SVD를 이용한 lower bound 계산 방법

SVD는 matrix을 세 개의 행렬로 분해하는 방법임.

행렬 $A$의 SVD는 다음과 같이 표현됨:
$$A = U \Sigma V^\top$$

여기서

• $U$는 $m \times m$ orthogonal matrix,
• $\Sigma$ 는 $m \times n$ diagonal matrix로 대각 성분은 $A$의 singular values,
• $V$ 는 $n \times n$ orthogonal matrix임.

행렬 $A$ 에 대해 $A^\top A$를 계산하면:
$$A^\top A = (U \Sigma V^\top)^\top (U \Sigma V^\top) = V \Sigma^\top U^\top U \Sigma V^\top = V \Sigma^\top \Sigma V^\top$$

여기서 $\Sigma_A = \Sigma^\top \Sigma$ 라고 정의함:
$$A^\top A = V \Sigma_A V^\top$$

이제 $\mathbf{x}^\top A^\top A \mathbf{x}$를 고려함:
$$\mathbf{x}^\top A^\top A \mathbf{x} = \mathbf{x}^\top V \Sigma_A V^\top \mathbf{x}$$

여기서 $\mathbf{y} = V^\top \mathbf{x}$라고 정의하면,

• $V$ 는 orthogonal matrix이므로
• $|| \mathbf{y} || = || \mathbf{x} ||$가 성립함.

2022.11.17 - [.../Math] - [LA] Orthogonal matrix (직교행렬)

[LA] Orthogonal matrix (직교행렬)

2022.11.17 - [.../Linear Algebra] - [LA] Diagonalization, Orthogonal Diagonalization, and Symmetric Matrix

[LA] Diagonalization, Orthogonal Diagonalization, and Symmetric Matrix

2024.02.15 - [.../Math] - [LA] Singular Value (특이값)

[LA] Singular Value (특이값)

 

 

따라서:
$$\mathbf{x}^\top A^\top A \mathbf{x} = \mathbf{y}^\top \Sigma_A \mathbf{y}$$

$\Sigma_A$ 는 $A$의 singular values의 제곱을 대각선으로 갖는 diagonal matrix임.

따라서:
$$\mathbf{y}^\top \Sigma_A \mathbf{y} = \sum_{i=1}^n \sigma_i^2 y_i^2$$

이제 lower bound를 구하기 위해 $A$의 최소 singular value $\sigma_{\min}$ 을 고려함.

이 경우 최소값은 $\mathbf{y}$가 최소 singular value에 해당하는 고유벡터와 정렬될 때 발생함.

따라서:
$$\mathbf{x}^\top A^\top A \mathbf{x} \geq \sigma_{\min}^2 || \mathbf{x} ||^2$$

최소값을 갖는 벡터 $\mathbf{x}$ 는

• $\mathbf{x} = V \mathbf{y}$에서
• $\mathbf{y}$ 가 최소 singular value에 해당하는 $\Sigma_A$의 eigenvector(고유벡터)일 때 얻어짐.

즉, $\mathbf{y}$ 가 $\mathbf{e}_{\min}$ (최소 singular value에 해당하는 eigenvector)일 때
$\mathbf{x} = V \mathbf{e}_{\min}$임.

---

EVD를 이용한 lower bound 계산 방법

EVD는 대칭 행렬을 orthogonal matrix와 diagonal matrix로 분해하는 방법임.

$A^\top A$는 대칭 행렬이므로, EVD를 통해 다음과 같이 표현됨:
$$A^\top A = V \Lambda V^\top$$

여기서

• $V$ 는 $A^\top A$ 의 eigenvectors들로 이루어진 $n \times n$ orthogonal matrix,
• $\Lambda$ 는 $A^\top A$ 의 eigenvalues들을 대각선으로 갖는 $n \times n$ diagonal matrix임.

이제 $\mathbf{x}^\top A^\top A \mathbf{x}$를 고려함:
$$\mathbf{x}^\top A^\top A \mathbf{x} = \mathbf{x}^\top (V \Lambda V^\top) \mathbf{x}$$

여기서 $\mathbf{y} = V^\top \mathbf{x}$라고 정의하면,
$V$ 는 orthogonal matrix이므로 $| \mathbf{y} | = | \mathbf{x} |$가 성립함.

따라서:
$$\mathbf{x}^\top A^\top A \mathbf{x} = \mathbf{y}^\top \Lambda \mathbf{y}$$

$\Lambda$ 는 $A^\top A$의 eigenvalues들을 대각선으로 갖는 diagonal matrix임.

따라서:
$$\mathbf{y}^\top \Lambda \mathbf{y} = \sum_{i=1}^n \lambda_i y_i^2$$

이제 lower bound를 구하기 위해 $A^\top A$의 최소 eigenvalue $\lambda_{\min}$을 고려함.

이 경우 최소값은 $\mathbf{y}$ 가 최소 eigenvalue에 해당하는 고유벡터와 정렬될 때 발생함.

따라서:
$$\mathbf{x}^\top A^\top A \mathbf{x} \geq \lambda_{\min} | \mathbf{x} |^2$$

최소값을 갖는 벡터 $\mathbf{x}$ 는

• $\mathbf{x} = V \mathbf{y}$에서
• $\mathbf{y}$가 최소 eigenvalue에 해당하는 $\Lambda$ 의 고유벡터일 때 얻어짐.

즉, $\mathbf{y}$ 가 $\mathbf{e}_{\min}$ (최소 eigenvalue에 해당하는 표준 기저 벡터)일 때 $\mathbf{x} = V \mathbf{e}_{\min}$임.

---

결론

벡터 $\mathbf{x}$와 행렬 $A$ 가 주어졌을 때,
$\mathbf{x}^\top A^\top A \mathbf{x}$ 의 lower bound는 두 가지 방법으로 구할 수 있음.

SVD를 이용하면

• $\mathbf{x}^\top A^\top A \mathbf{x} \geq \sigma_{\min}^2 || \mathbf{x} ||^2$이 성립하고,
• 여기서 $\sigma_{\min}$ 은 $A$ 의 최소 singular value임.
• 최소값을 갖는 벡터 $\mathbf{x}$ 는 $V \mathbf{e}_{\min}$임.

EVD를 이용하면

• $\mathbf{x}^\top A^\top A \mathbf{x} \geq \lambda_{\min} || \mathbf{x} ||^2$이 성립하고,
• 여기서 $\lambda_{\min}$은 $A^\top A$ 의 최소 eigenvalue임.
• 최소값을 갖는 벡터 $\mathbf{x}$ 는 $V \mathbf{e}_{\min}$임.

따라서, $\mathbf{x}^\top A^\top A \mathbf{x}$ 의 lower bound를 구할 때 SVD와 EVD 모두 유용한 도구임.

다만, EVD는 수치적으로 불안정할 수 있으므로 주의가 필요함.

---

Python 예제 코드

다음은 Python의 numpy 라이브러리를 사용하여 $\mathbf{x}^\top A^\top A \mathbf{x}$의 lower bound를 SVD와 EVD를 통해 구하는 예제 코드임.

import numpy as np
 
# 임의의 행렬 A와 벡터 x
 
A = np.array([[1, 2], [3, 4], [5, 6]])  
x = np.array([1, 0])
 
# SVD를 이용한 lower bound 계산
 
U, Sigma, VT = np.linalg.svd(A)  
sigma_min = np.min(Sigma)  
lower_bound_svd = sigma_min**2 * np.linalg.norm(x)**2
 
print(f"SVD를 이용한 lower bound: {lower_bound_svd}")
 
# 최소값을 갖는 벡터 x 계산
 
e_min_svd = np.zeros_like(x)  
e_min_svd[np.argmin(Sigma)] = 1  
x_min_svd = VT.T @ e_min_svd
 
print(f"최소값을 갖는 벡터 x (SVD): {x_min_svd}")
 
# EVD를 이용한 lower bound 계산
 
ATA = np.dot(A.T, A)  
eigenvalues, V = np.linalg.eigh(ATA)  
lambda_min = np.min(eigenvalues)  
lower_bound_evd = lambda_min * np.linalg.norm(x)**2
 
print(f"EVD를 이용한 lower bound: {lower_bound_evd}")
 
# 최소값을 갖는 벡터 x 계산
 
e_min_evd = np.zeros_like(x)  
e_min_evd[np.argmin(eigenvalues)] = 1  
x_min_evd = V @ e_min_evd
 
print(f"최소값을 갖는 벡터 x (EVD): {x_min_evd}")

위 코드에서는

• numpy의 svd 함수와 eigh 함수를 사용하여 각각 SVD와 EVD를 수행하고,
• 이를 통해 $\mathbf{x}^\top A^\top A \mathbf{x}$ 의 lower bound를 계산함.

SVD를 이용한 lower bound는 최소 singular value를 사용하고,
EVD를 이용한 lower bound는 최소 eigenvalue를 사용함.
또한, 최소값을 갖는 벡터 $\mathbf{x}$를 각각의 방법을 통해 구함.

---

같이 읽어보면 좋은 자료들

2024.06.22 - [Programming/ML] - [Fitting] Total Least Square Regression

[Fitting] Total Least Square Regression