728x90

13강. 일반최소제곱법과 QR 분할

Orthogonal Basis & Gram-Schmitt

$q_{1}, q_{2}, \dots, q_{n}$ are orthogonal
$q_{i}^{T} q_{j} = 0 (i \neq j)$
$q_{i}^{T} q_{j} = 1 (i = j)$
$Q = [q_{1}, q_{2}, \dots, q_{n}]$
$Q^{T} Q = I$ => Left-inverse
=> $Q^{- 1} = Q^{T}$
Rotation matrix
$\begin{matrix} \end{matrix}$
Permutation matrix
$\begin{matrix} \end{matrix}$
-> $P^{- 1} = P^{T}$
Geometrically, an orthogonal $Q$ is the product of a rotation and a reflection
Projection reduces the length of a vector, But orthonormal matrix preserves angles and lengths
$| | Q x | |^{2} = x^{T} Q^{T} Q x = | | x | |^{2}$ -> length conservation
$^{}$
$(Q x)^{T} (Q y) = x^{T} Q^{T} Q y = x^{T} y$ -> inner product or angle conservation
For any vector $b$
$b = x_{1} q_{1} + x_{2} q_{2} + \dots + x_{n} q_{n}$ => $Q x = b$
$q_{i}^{T} b = x_{i}$
$b = (q_{i}^{T} b) q_{1} + \dots + (q_{n}^{T} b) q_{n}$
$b = Q x$ <=> $x = Q^{T} b = Q^{- 1} b$
1-D projection onto a line $a$
= $\frac{a^{T} b}{a^{T} a} a$
for $q_{i}, \frac{q_{i}^{T} b}{q_{i}^{T} q_{i}} q_{i} = (q_{i}^{T} b) q_{i} = x_{i} q_{i}$
-> $x_{i}$ : projection of $q_{i}$ of $b$
$Q^{T} = Q^{- 1}$ => $Q Q^{T} = I$ , for square cases The rows are also orthonormal

Rectangular matrix with Orthonormal columns

for m < n ; least square cases
$Q x = b$
$Q^{T} Q \hat{x} = Q^{T} b$ : normal equation for least squares
$\hat{x} = Q^{T} b$ : ( $Q^{T} Q = I$ )
$p = Q \hat{x}$
$p = Q (Q^{T} Q)^{- 1} Q^{T} b = Q Q^{T} b$
$Q^{T}$ 는 Left-inverse이다.
m>n일 때는 $Q Q^{T}$ 가 $I$ 로 나오지 않음.

Gram-Schmitt Orthogonalization

-> find the orthonormal basis given independent vectors

$q_{1} = \frac{a}{| | a | |}$
$\frac{q_{1}^{T} b}{q_{1}^{T} q_{1}} q_{1}$
$B = b - (q_{1}^{T} b) q_{1} ⊥ q_{1}$
이는 다음과 같다.
$\frac{b - (q_{1}^{T} b) q_{1}}{| | b - (q_{1}^{T} b) q_{1} | |} = q_{2}$
$b = (q_{1}^{T} b) q_{1} + (q_{2}^{T} b) q_{2}$

$C = c - [(q_{1}^{T} b) q_{1} + (q_{2}^{T} b) q_{2}] = (q_{3}^{T} c) q_{3}$
$C = \sum_{i = 1}^{3} (q_{i}^{T} c) q_{i}$
아래는 공식화 한 것이다.
$a_{j} = \sum_{i = 1}^{j} (q_{i}^{T} a_{j}) q_{i}$

Factorization $A = Q R$

$\begin{matrix} _{} & _{} & _{} \end{matrix} \begin{matrix} _{}^{}_{}_{} & _{}^{}_{}_{} & _{}^{}_{}_{} \\ _{}^{}_{}_{} & _{}^{}_{}_{} \\ _{}^{}_{}_{} & _{}^{}_{}^{}_{}_{} \end{matrix}$
linear combination of each column vector
$\begin{matrix} _{} & _{} & _{} \end{matrix} \begin{matrix} _{}^{}_{} & _{}^{}_{} & _{}^{}_{} & _{}^{}_{} \\ _{}^{}_{} & _{}^{}_{} \\ _{}^{}_{} \\ _{}^{}_{} \end{matrix}$
Upper triangular matrix 모양이다
이를 $A = Q R$ 이라고 해서 QR분해라고한다.

728x90

티스토리툴바