<jupyter_start><jupyter_text>Linear least squares<jupyter_code>import warnings
warnings.filterwarnings(action="ignore", module="scipy", message="^internal gelsd")
import numpy as np
import scipy.linalg as la<jupyter_output><empty_output><jupyter_text>Sketch of lecture  Normal equations- Suppose $Ax = b$ is inconsistent. In this case, we can look instead for $\widehat{x}$ which minimizes the distance between $Ax$ and $b$. In other words, we need to minimize $\Vert Ax - b \Vert^2$.- The minimum will occur when $\langle Ax-b, Ax \rangle = 0$ - Solving $(Ax)^T(Ax - b) = 0$ gives the normal equations $\widehat{x} = (A^TA)^{-1}A^T b$- The corresponding vector in $C(A)$ is $A\widehat{x} = A(A^TA)^{-1}A^T b$- Note that $P_A = A(A^TA)^{-1}A^T$ is the projection matrix for $C(A)$- This makes sense, since any solution to $Ax = b$ must be in $C(A)$, and the nearest such vector to $b$ must be the projection of $b$ onto $C(A)$.<jupyter_code>m = 100
n = 5
A = np.random.rand(m, n)
b = np.random.rand(m, 1)<jupyter_output><empty_output><jupyter_text>Using least squares function (SVD)<jupyter_code>x, res, rank, s, = la.lstsq(A, b)
x
(A @ x).shape<jupyter_output><empty_output><jupyter_text>Using normal equations (projection) - for illustration only.<jupyter_code>la.inv(A.T @ A) @ A.T @ b<jupyter_output><empty_output><jupyter_text>Projection matrices- Let $P$ be the projection matrix onto $C(A)$- Since it is a projection operator, $P^2$ = $P$ (check)- Check that $I-P$ is also idempotent (it turns out to also be a projection matrix)- Where does $I-P$ project to?- Show $C(I-P) = N(P)$- Show $\rho(P) + \nu(P) = n$- This implies $\mathbb{R}^n = C(P) \oplus C(I-P)$- Trivial example$$P = \begin{bmatrix}1 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 0\end{bmatrix}, (I-P) = \begin{bmatrix}0 & 0 & 0 \\0 & 0 & 0 \\0 & 0 & 1\end{bmatrix}$$- Geometry of $P$ and $I-P$ in linear least squares<jupyter_code>P = A @ la.inv(A.T @ A) @ A.T 
P.shape
x, res, rank, s, = la.lstsq(A, b)
Q = np.eye(m) - P
(P @ b)[:5]
(A @ x)[:5]
la.norm(Q @ b)**2
res<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.17615571776155717, 'fraction_numerical': 0.016058394160583942, 'mean_word_length': 4.424802110817942, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '324351', 'license': 'BSD-3-Clause', 'n_tokens_mistral': 828, 'n_tokens_neox': 789, 'n_words': 253, 'path': 'notebooks/S08D_Least_Squares.ipynb', 'repo_name': 'sakuramomo1005/sta-663-2018', 'size': '2055'}