HOMEWORK
expore $m>>n$
Solutions using QR decomp
Definition. A permutation matrix is a square matrix s.t. each col. has one 1 and each row has one 1
Definition. A matrix $Q$ is orthogonal if $Q'Q=QQ'=I$
Definition. A matrix $\R$ is upper triangular if $R_{ij}=0$ whenever $i>j$
HOMEWORK
1. Suppose upper-tri $R\in\R^{m\times m}$ s.t. $R_{ij}\neq0$
is $R$ invertible?
2. When $R$ is invertible, how do you solve $Rx=b$?
Let $A\in\R\nm$ and let $r=\rank(A)$. Then, there exists
- $m\times m$ permutation matrix $\Pi$
= $n\times n$ orthogonal matrix $Q$
- $r\times r$ upper tri matrix $R$ (nonzero diag)
- $r\times(m-r)$ matrix $S$ (unless $m=r$)
s.t. $A=Q\mat{R&S\\0&0}\Pi'$
Consistent linear system $Ax=b$, $\rank(A)=m$
\begin{align*}
A\mat{R\\0}\Pi'x&=b\\\mat{R\\0}\Pi'x&=Q'b=c~~~~~~~\text{*(HWK)*}\\&=\mat{c_1\\0}
\end{align*}
\begin{align*}
R\Pi'x&=c_1\\\Pi'x&=R\inv c_1\\x&=\Pi R\inv c_1
\end{align*} $$~$$
Least squares, $\rank(A)=m$
$$\min\norm{Q\mat{R\\0}\Pi'x-b}{2}$$
HOMEWORK
: Prove $\norm{x}2=\norm{Qx}2$
$$=~\min\Bigg|\Bigg|\mat{R\\0}\Pi'x-\underbrace{Q'b}_{\mat{c_1\\c_2}}\Bigg|\Bigg|_2~=~\min\norm{\mat{R\Pi'x-c_1\\-c_2}}{2}$$ $$=~\min\sqrt{\norm{R\Pi'x-c_1}{}_2^2+\norm{c_2}{}_2^2}$$
\begin{align*}
\hat{x}&=(A'A)\inv A'b\\
&=\INV{\pr{\Pi\mat{R\\0}'\underbrace{Q'Q}_{I}\mat{R\\0}\Pi'}}\!\Pi\;\mat{R\\0}'Q'b\\
&=\INV{\Pi R'R\Pi'}\Pi\,\mat{R'&0'}\mat{c_1\\c_2}\\
&=\Pi R\inv(R)\inv\cancel{\Pi'\Pi}\,\mat{R'c_1+0}\\
&=\Pi R\inv c_1
\end{align*}
HOMEWORK
: Implement linear regression solver, inputs $A,b$, outputs $\hat{x},\norm{c_2}2$ $$~$$
Undetermined linear system $\min\br{\norm y2:Ay=b}$
\begin{align*}
Q\mat{R&S\\0&0}\Pi'y&=b\\
\mat{R&S\\0&0}\underbrace{\Pi'y}_{\mat{z_1\\z_2}}&=\mat{c\\0}~~~~~~~~~\implies~~~~~\begin{matrix}Rz_1+Sz_2=C
\\z_1=-R\inv Sz_2+R\inv C\end{matrix}
\end{align*} $$\min\Big\lbrace\norm z2:z_1=R\inv C-R\inv Sz_2\Big\rbrace~=~\min\sqrt{\vphantom{\Big|\Big|\,R\inv C-R\inv Sz_2\Big|\Big|_2^2+\norm{z_2}{}_2^2}\smash{\Big|\Big|\,\underbrace{R\inv C}_d-\underbrace{R\inv S}_Pz_2\Big|\Big|_2^2+\norm{z_2}{}_2^2}}$$
HOMEWORK
$~$ Let $f$ be a vector-valued function over $\R^d$, when is $\min_x\norm{f(x)}2=$ $\min_x\norm{f(x)}{}_2^2$
continuing, we solve for $$\min\bigg\lbrace~\norm{d-Pz_2}{}_2^2+\norm{z_2}{}_2^2~\bigg\rbrace~\implies~0=-P'd+(P'P+I)z_2$$ $$\implies~z_2=(P'P+I)\inv P'd$$
HOMEWORK
$~$ Prove $P'P+I$ is invertible $$~$$
Underdetermined linear regression
\begin{align*}
&\,\min\bigg\lbrace~\norm z2:z\in\argmin_y\norm{Ay-b}2\bigg\rbrace\\
=&\,\min\bigg\lbrace~\norm z2:z\in\argmin_y\norm{\mat{R&S\\0&0}\Pi'y-Q'b}2\bigg\rbrace\\
=&\,\min\bigg\lbrace~\norm w2:w\in\argmin_y\norm{\mat{R&S\\0&0}y-Q'b}2\bigg\rbrace~~~\text{where }w=\mat{R\inv(c_1-Sy_2)\\y_2}
\end{align*}
Constrained least squares
HOMEWORK
$~$ Solve problem $5$, and also consider what if $p\geq m$, then implement solution
HOMEWORK
$~$ Let $A\in\R\nm$, $~\rank(A)=m$, $~b\in\R^n$, $~C=\mat{A&B}$
$$~$$
Theorem. (Gram-Schmidt) $~$ Let $r\in\N$. Given a set of linearly independent $\br{a_1,..,a_r}$, there exists a set of orthonormal vectors $\br{q_1,..,q_r}$ that span the same space as the original.
Proof. $~$ By induction. For $r=1$, $$q_1=\frac1{R_{11}}a_1~~~~~\text{where }R_{11}=\norm{a_1}2$$ For $r=2$, we want orthonormal $q_2$ such that $$a_2=R_{12}q_1+R_{22}q_2$$ Multiplying by $q_1'$ and using orthonormality implies $q_1'a_2=R_{12}$ Then, let ${\def\tq{\tilde{q}}}\tq_2=a_2-R_{12}q_1$ and let $R_{22}=\norm{\tq_2}2$. Then, $q_2=\frac1{R_{22}}\tq_2~$ is the desired vector.
Induction step: suppose $q_1,..,q_{r-1}$ are orthonormal vectors that span $q_1,..,a_{r-1}$. Then, let
\begin{align*}
R_{ir}&=q_i'a_r\\
\tq_r&=a_r-\sum_{i=1}^{r-1}R_{ir}q_i\\
R_{rr}&=\norm{\tq_r}2\\
q_{r}&=\frac1{R_{rr}}\tq_r
\end{align*}
We can check that
\begin{align*}
q_i'\tq_r&=q_i'a_r-\sum_{j=1}^{r-1}R_{jr}q_j'q_i\\
&=q_i'a_r-R_{ir}\\
&=0
\end{align*} and that
\begin{align*}
\sum_{i=1}^rR_{ir}q_i&=\sum_{i=1}^{r-1}R_{ir}q_i+R_{rr}q_r\\
&=\sum_{i=1}^{r-1}R_{ir}q_i+R_{rr}\pr{\frac1{R_{rr}}}\pr{a_r-\sum_{i=1}^{r-1}R_{ir}q_i}\\
&=a_r
\end{align*}
Thus, we have $$\mat{\vphantom{\Big|}a_1&a_2&\cdots&a_r}~=~\mat{q_1&q_2&\cdots&q_r\vphantom{\Big|}}\mat{R_{11}&R_{12}&\cdots&R_{1r}\\0&R_{22}&\cdots&R_{2r}\\0&0&\ddots&\vdots\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&R_{rr}}$$
$$~$$
$\Pi$ is such that first $r$ columns of $A\Pi$ are linearly independent, i.e. $$\bigg[~\vphantom{\Big|}\underbrace{\begin{matrix}a_1&a_2&\cdots&a_r\end{matrix}}_\text{lin. indep.}~~~~\begin{matrix}a_{r+1}&\cdots&a_m\end{matrix}~\bigg]$$ Then by Gram-Schmidt, we can have $\big[a_1\;\cdots\;a_r\big]=\tilde{Q}R~$ for some $\tilde{Q}\in\R\nr$, $R\in\R\rr$
The vectors $\big[a_{r+1}\;\cdots\;a_m\big]$ can be expressed as some linear combination of the previous $a_1,..,a_r$ vectors, so we have $$A\,\Pi\,=\,\tilde{Q}\mat{\vphantom{\Big|}R&S}$$
HOMEWORK $~$ Modified Gram-Schmidt
Implement modified Gram-Schmidt with column pivoting and find examples where it succeeded but would have failed without pivoting.