Orthogonal Projection Perspective
-To solve the Least Squares problem mathematically, we look at it from an Orthogonal Projection Perspective
-For an invertible matrix $C = A^TA$, the orthogonal projection of vector $b$ onto the column space of $A$ is defined as $\hat{b} = f(b) = A\hat{x} = A(A^TA)^{-1}A^Tb$
-The computation becomes significantly simpler if we use orthogonal or orthonormal sets
- If we project a vector $y$ onto a one-dimensional subspace $L = \text{Span}\{u\}$, the projection is calculated as: $$\hat{y} = \text{proj}_{L}y = \frac{y \cdot u}{u \cdot u}u$$
- For a two-dimensional subspace, the projection is done independently on each orthogonal basis vector: $$\hat{y} = \text{proj}_{L}y = \frac{y \cdot u_1}{u_1 \cdot u_1}u_1 + \frac{y \cdot u_2}{u_2 \cdot u_2}u_2$$
-Furthermore, if matrix $A$ consists of orthonormal columns (let's call it $U$), then $C = U^TU = I$
-Thus, the linear transformation simplifies beautifully to $\hat{b} = UU^Tb$
최소제곱법을 풀기 위해 기하학적인 정사영(Orthogonal Projection) 개념 도입
-역행렬이 존재하는 $A^TA$에 대해 투영 벡터를 구하는 공식은 복잡해 보이지만, 기저 벡터들이 직교(Orthogonal)할 경우 계산이 간단해짐!-1차원 선(Line)이나 2차원 평면(Plane)에 투영할 때, 기저가 직교하면 각 벡터에 대해 독립적으로 투영값을 구해서 더하기만 하면 된다
-특히 행렬의 열들이 크기가 1인 정규직교(Orthonormal)라면 역행렬 계산이 완전히 사라져 $\hat{b} = UU^Tb$라는 아주 심플한 공식만 남음
Gram-Schmidt Orthogonalization (그람-슈미트 직교화)
-Given the mathematical convenience of orthogonal bases, we need a method to convert an ordinary basis into an orthogonal one
-This is achieved through the Gram-Schmidt Orthogonalization process
-If we have a linearly independent basis $\{x_1, x_2, x_3\}$ for a subspace $W$, we iteratively construct an orthogonal basis $\{v_1, v_2, v_3\}$:
- Step 1: Let $v_1 = x_1$ and define the subspace $W_1 = \text{Span}\{v_1\}$
- Step 2: Subtract the projection of $x_2$ onto $W_1$ from $x_2$ → That is, $v_2 = x_2 - \text{proj}_{W_1}x_2 = x_2 - \frac{x_2 \cdot v_1}{v_1 \cdot v_1}v_1$ → $v_2$ is now the component of $x_2$ orthogonal to $x_1$ (As an optional step, we can scale $v_2$ to avoid fractions and simplify later computations)
- Step 3: Subtract the projection of $x_3$ onto the new subspace $W_2$ from $x_3$: By repeating this subtraction of projected components, we isolate pure orthogonal vectors at each step $$v_3 = x_3 - \text{proj}_{W_2}x_3 = x_3 - \frac{x_3 \cdot v_1}{v_1 \cdot v_1}v_1 - \frac{x_3 \cdot v_2'}{v_2' \cdot v_2'}v_2'$$
그람-슈미트 직교화 : 일반 기저를 다루기 쉬운 직교 기저로 바꾸는 과정
원리 :
첫 번째 vector는 기준점($v_1$)으로 둠
두 번째 vector부터는, 기존에 만들어둔 평면에 투영된 성분(=그림자)을 원본 벡터에서 빼줌
이떄, 빼고 남은 성분은 자연스럽게 기존 평면과 완벽히 수직이 됨
+$v_2$ 계산 시 분수가 나오면 정수로 스케일링을 해줘야 Step 3 계산이 꼬이지 않음!
Computing QR Factorization (QR 분해 연산)
-The Gram-Schmidt process naturally builds the foundation for QR Factorization
-If matrix $A$ is an $m \times n$ matrix with linearly independent columns, it can be factored into $A = QR$
- Step 1 (Construction of Q): We construct the orthonormal basis $\{u_1, \dots, u_n\}$ using the Gram-Schmidt process described above and normalize them → These vectors form the columns of the $m \times n$ matrix $Q$
- Step 2 (Construction of R): For each column $k$, $x_k$ is in $\text{Span}\{u_1, \dots, u_k\}$. Therefore, there exist constants such that $x_k = r_{1k}u_1 + \dots + r_{kk}u_k$ → These coefficients form $r_k$, the $k$-th column of the $n \times n$ upper triangular matrix $R$
-Since $R$ is invertible and upper triangular, its diagonal entries $r_{kk}$ must be nonzero
→ We can always make $r_{kk} \ge 0$, which means $r_{kk}$ must be strictly positive
QR 분해 = 그람-슈미트 과정의 최종 목적
-$Q$ 행렬 : 직교화 과정에서 얻은 벡터들의 크기를 1로 정규화(normalize)해서 묶어둔 것
-$R$ 행렬 : 원래의 $x$ 벡터를 $Q$의 벡터들의 조합으로 표현하기 위해 쓰인 계수들을 모아둔 것
-$R$ 행렬은 무조건 대각성분이 양수인 상삼각행렬(Upper Triangular Matrix) 형태를 띠게 되며, 이를 통해 복잡한 선형 시스템을 훨씬 효율적으로 계산할 수 있게 해줌
실습II : 강의 수강 완료
