orthogonality-least-squares.md (4257B)
1 +++ 2 title = 'Orthogonality & least squares' 3 template = 'page-math.html' 4 +++ 5 6 # Orthogonality & least squares 7 let $u,v \in \Re^n$. orthogonal iff: 8 * $u \cdot v = 0$ 9 * or $\|u\|^2 + \|v\|^2 = \|u+v\|^2$ 10 11 ## Inner (dot) product & uses 12 let $u,v \in \Re^n$. then, $u \cdot v = u^T v \in \Re$. 13 14 in English, to calculate you just multiply the vectors row-wise, and sum all the results. 15 16 Regular algebraic rules apply. 17 18 $u \cdot u \geq 0$, only 0 iff u = 0. 19 20 ### Length of a vector 21 Let $v \in \Re^n$, then the norm (length) of v is $\|v\| = \sqrt{v \cdot v}$. 22 23 Does the norm coincide with length of line segments? Yes: 24 25 $x = \begin{bmatrix}a\\\\b\end{bmatrix}, \quad \|v\| = \sqrt{v \cdot v} = \sqrt{a^2 + b^2} = \text{Pythagoras}$ 26 27 ### Distance between vectors 28 Let $u,v \in \Re^n$. then, $\text{dist}(u,v) = \|u-v\|$. 29 30 ## Orthogonal complement 31 Let $W \subset \Re^n$ a subspace, then orthogonal complement of W is $W^\perp = \{x \in \Re^n | x \cdot v = 0 \forall u \in W \}$ 32 33 properties: 34 * $(colA)^\perp = (NulA)^T$ 35 * $(NulA)^\perp = (colA)^T$ 36 37 ## Orthogonal sets 38 a set $\{v_1 \dots v_p\}$ is orthogonal if $v_i \cdot v_j = 0 \forall i,j$. then $\{v_1 \dots v_p\}$ is a basis for $\text{Span}\{v_1 \dots v_p\}$ 39 40 An orthogonal basis is a basis that is also an orthogonal set 41 42 Why orthogonal basis? Let $W \in \Re^n$ be subspace with orthogonal basis $\{u_1 \dots u_p\}$, then $W \ni y = c_1 u_1 + \ldots + c_p u_p$, with $c_i = \frac{y \cdot u_i}{u_i \cdot u_i}$ for i = 1...p. 43 44 An orthonormal set/basis is an orthogonal set/basis consisting of unit vectors (like $\{e_1, \ldots, e_n\}\text{ for }\Re^n$). 45 46 An m × matrix A has orthonormal columns iff $A^T A = I_n$ 47 * $(Ax) \cdot (Ay) = x \cdot y$ 48 * $\| Ax \| = \| x \|$ 49 50 ## Orthogonal projections 51 ### Orthogonal decomposition 52 Let W be a subspace of $\Re^n$. Each y in $R^n$ can be written uniquely in $y = \hat{y}+z$ ($\hat{y} \in W,\\; z \in W^\perp$) 53 54 If $\{u_1, \ldots, u_p\}$ in orthogonal basis of W, then $\hat{y} = \frac{y \cdot u_1}{u_1 \cdot u_1} u_1 + \ldots + \frac{y \cdot u_p}{u_p \cdot u_p}u_p$ 55 56 ŷ is an orthogonal projection of y onto W ($proj_w y$) 57 58 ### Best approximation 59 Let W be subspace of $\Re^n$, y a vector in $\Re^n$, ŷ an orthogonal projection of y onto W. 60 61 Then $\|y-\hat{y}\| < \|y-v\|$ 62 63 ### When basis for W is an orthonormal set 64 If $\{u_1 \ldots u_p\}$ is orthonormal basis for subspace W of $\Re^n$, then $\text{proj}_w y = (y \cdot u_1)u_1 + \dots + (y \cdot u_p) u_p$ 65 66 If U = $\begin{bmatrix} u_1 & u_2 & \dots & u_p \end{bmatrix}$, then $\text{proj}_w y = UU^T y \quad \forall y \in \Re^n$ 67 68 ## Gram-Schmidt process 69 An algorithm for producing orthogonal or orthonormal basis for any nonzero subspace of $\Re^n$. 70 71 Given basis $\{ x_1 \dots x_p \}$ for nonzero subspace W of $\Re^n$, define: 72 73 $ 74 \begin{aligned} 75 v_1 &= x_1\\\\ 76 v_2 &= x_2 - \frac{x_2 \cdot v_1}{v_1 \cdot v_1} v_1\\\\ 77 v_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\\\\ 78 \vdots \\\\ 79 v_p &= x_p - \frac{x_p \cdot v_1}{v_1 \cdot v_1} v_1 - \dots - \frac{x_p \cdot v_{p-1}}{v_{p-1} \cdot v_{p-1} v_{p-1}} 80 \end{aligned} 81 $ 82 83 Then $\{v_1 \dots v_p\}$ is an orthogonal basis for W. 84 85 $\text{Span}\{v_1 \dots v_k\} = \text{Span}\{x_1 \dots x+k\}$ for 1 ≤ k ≤ p. 86 87 ### QR factorization 88 If A is an m × n matrix, with linearly independent columns, then A can be factored as $A = QR$, where Q is he m×n matrix whose columns form an orthonormal basis for Col A, and R is n×n upper triangular invertible matrix with diagonal positive entries. 89 90 ## Least-squares problems 91 If a solution for $Ax = b$ does not exist and one is needed, try to find the best approximation x for $Ax = b$. 92 93 General least-squares problem is to find x that makes $\| b - Ax\|$ as small as possible. 94 95 If A is m×n and $b \in \Re^m$, a least-squares solution of $Ax = b$ is $\hat{x} \in \Re^n$ such that $\| b - A\hat{x} \| \leq \| b - Ax \|, \qquad \forall x \in \Re^n$. 96 97 Least-square solution set of $Ax = b$ is the same as the solution set for $A^T Ax = A^T b$. 98 99 Therefore, $\hat{x} = (A^T A)^{-1} A^T b$. 100 101 Given an m×n matrix A with linearly independent columns, let $A = QR$ be a QR factorization of A. Then, for each $b \in \Re^m$, $Ax = b$ has unique least-squares solution: 102 103 $\hat{x} = R^{-1} Q^T b$ 104