Chapter-1-Regression

1.Linear regression

1.1 Preliminaries: linear algebra & matrix calculate

• Vectors: a=$\left(\begin{array}{c}{a}_1\\ a_2\\ ⋮\\ a_n\end{array}\right)\in R^n$ (Vector space)
• Inner product: $a,b\in R^n,a^{\prime }b={\sum }_{i=1}^n{a}_i{b}_i$ (Euclidean space)
• Norm:$\Vert a{\Vert }_2=(a^{\prime }a{)}^{1/2}=({\sum }_{i=1}^n{a}_i^2{)}^{1/2}$

$$\begin{array}{rl}& 1.\Vert a{\Vert }_2\ge 0{,}^{\prime }{=}^{\prime }ifandonlyifa=\vec{0}\\ & 2.\Vert a+b{\Vert }_2\le \Vert a{\Vert }_2+\Vert b{\Vert }_2,a,b\in R^n\\ & 3.\Vert \lambda a{\Vert }_2=|\lambda |\Vert a{\Vert }_2,\lambda \in R^n,a\in R^n\end{array}$$

$\to Cauchy-Schwarzinequality:|a^{\prime }b|\le \Vert a{\Vert }_2\Vert b{\Vert }_2$

$$\begin{array}{rl}& \\ Proof:& letf(x)=\sum _{i=1}^n(a_{i}x-b_i{)}^2=(\sum _{i=1}^n{a}_i^2)x^2-2(\sum _{i=1}^n{a}_i{b}_i)+(\sum _{i=1}^n{b}_i^2)\\ & forf(x)\ge 0forallx\in Ritfollowthatthediscriminant\\ & \Delta =4(\sum _{i=1}^n{a}_i{b}_i{)}^2-4(\sum _{i=1}^n{a}_i^2)(\sum _{i=1}^n{b}_i^2)\le 0\\ & |a^{\prime }b|\le \Vert a{\Vert }_2\Vert b{\Vert }_2\end{array}$$

• Distance: $d(a,b)=\Vert a-b{\Vert }_2$

$$\begin{array}{rl}& 1.d(a,b)\ge 0{,}^{\prime }{=}^{\prime }ifandonlyifa=b\\ & 2.d(a,b)+d(b,c)\ge d(a,c)\\ & 3.d(a,b)=d(b,a)fora,b\in R^n\end{array}$$

---

• Matrix: $A=(a_{ij})\in R^{n\times m},B=(b_{ij})\in R^{n\times m}$ $\Rightarrow A+B=(a_{ij}+b_{ij})$ If $B\in R^{m\times p}$,we can define AB $A^{\prime }=(a_{ji})$ $\Rightarrow (AB{)}^{\prime }=B^{\prime }{A}^{\prime }$

• Square Matrix (n=m)$\to A^{-1},(AB{)}^{-1}=B^{-1}{A}^{-1}$ $(A^{\prime }{)}^{-1}=(A^{-1}{)}^{\prime }$ → det(A),det(AB)=det(A)det(B) → tr(A), tr(AB) = tr(BA)

• Symmetric matrix $(A=A^{\prime })$: there exists a matrix $U\in R^{n\times n}$ satisfying $U^{\prime }U=I$ such that $A=U^{\prime }\left(\begin{array}{cccc}{\lambda }_1& & & \\ & {\lambda }_2& & \\ & & \ddots & \\ & & & {\lambda }_n\end{array}\right)U.$ [spectral decomposition]

  (i) The ${\lambda }_i$ are called eigenvalues of A.

  (ii) → A is called positive definite (p.d.) if ${\lambda }_i$ are all positive $\iff a^{\prime }Aa>0$ for all nonzero a ∈ ℝⁿ.

  → A is called positive semi-definite (p.s.d.) if ${\lambda }_i\ge 0,fori=1,...,n$ . $\iff a^{\prime }Aa\ge 0$ for all a ∈ ℝⁿ.

• Inverse of a partitioned matrix.

  • Let M =$\left(\begin{array}{cc}E& F\\ G& H\end{array}\right)$. Suppose that H is invertible. Then

$M^{-1}=\left(\begin{array}{cc}{S}^{-1}& -S^{-1}F{H}^{-1}\\ -H^{-1}G{S}^{-1}& H^{-1}+H^{-1}G{S}^{-1}F{H}^{-1}\end{array}\right)$

where $S=E-F{H}^{T}G$ is called the Schur complement of $M$ with respect to (w.r.t.) $H$.

$$\text{Proof:}\left(\begin{array}{cc}I& -F{H}^{\prime }\\ 0& I\end{array}\right)\left(\begin{array}{cc}E& F\\ G& H\end{array}\right)\left(\begin{array}{cc}I& 0\\ -H^{-1}G& I\end{array}\right)=\left(\begin{array}{cc}E-F{H}^{-1}G& 0\\ 0& H\end{array}\right)$$

Taking inverse on both sides, we obtain that

$${\left(\begin{array}{cc}I& 0\\ -H^{-1}G& I\end{array}\right)}^{-1}{\left(\begin{array}{cc}E& F\\ G& H\end{array}\right)}^{-1}\left(\begin{array}{cc}I& -F{H}^{-1}\\ 0& I\end{array}\right)=\left(\begin{array}{cc}{S}^{-1}& 0\\ 0& H^{-1}\end{array}\right)$$ $$\Rightarrow {\left(\begin{array}{cc}E& F\\ G& H\end{array}\right)}^{-1}=\left(\begin{array}{cc}I& 0\\ -H^{-1}G& I\end{array}\right)\left(\begin{array}{cc}{S}^{-1}& 0\\ 0& H^{-1}\end{array}\right)\left(\begin{array}{cc}I& -F{H}^{-1}\\ 0& I\end{array}\right)$$ $$=\left(\begin{array}{cc}{S}^{-1}& -S^{-1}F{H}^{-1}\\ -H^{-1}G{S}^{-1}& H^{-1}+H^{-1}G{S}^{-1}F{H}^{-1}\end{array}\right)$$

• Similarly, if $E$ is invertible, then

$${\left(\begin{array}{cc}E& F\\ G& H\end{array}\right)}^{-1}=\left(\begin{array}{cc}{E}^{-1}+E^{-1}F{R}^{-1}G{E}^{-1}& -E^{-1}F{R}^{-1}\\ -R^{-1}G{E}^{-1}& R^{-1}\end{array}\right)$$

where $R=H-GEF$ is the Schur complement of $M$ w.r.t. $E$.

If both $E$ & $H$ are invertible, then we have

$$S^{-1}=E^{-1}+E^{-1}F{R}^{-1}G{E}^{-1}\iff (E-F{H}^{-1}G{)}^{-1}=E^{-1}+E^{-1}F(H-G{E}^{-1}F{)}^{-1}G{E}^{-1}.$$

In particular, let $F=u$, $H=-I$, $G=v^T$. Then

$$(E+u{v}^{\prime }{)}^{-1}=E^{-1}-\frac{E^{-1}u{v}^{\prime }{E}^{-1}}{1+v^{\prime }{E}^{-1}u}.$$

(rank-one update of an inverse matrix)

---

• Let $f:{\mathbb{R}}^n\to \mathbb{R}$. Then

$$\frac{\partial f(x)}{\partial x}=\left(\begin{array}{c}\frac{\partial f(x)}{\partial x_1}\\ ⋮\\ \frac{\partial f(x)}{\partial x_n}\end{array}\right)$$

We have that

$$\{\begin{array}{l}\frac{\partial (b^{\prime }a)}{\partial a}=b\\ \frac{\partial (a^{\prime }Aa)}{\partial a}=(A+A^{\prime })a\stackrel{\text{if }A=A^{\prime }}{=}2Aa.\end{array}$$

1.2 Linear models and least squares estimators}

• Regression: goal is to predict $y\in \mathbb{R}$ based on the input/feature $x=(x_1,\dots ,x_p{)}^{\top }\in {\mathbb{R}}^p$.

• A linear model assumes that

$$y=w_0+w_1{x}_1+\cdots +w_p{x}_p+\epsilon ,$$

where $w_0,w_1,\dots ,w_p$ are unknown parameters, and $\epsilon$ is an error term.

• Let $w=(w_0,w_1,\dots ,w_p{)}^{\top }$, and $x=(1,x_1,\dots ,x_p{)}^{\top }$. Then model (1) can be written as

$$y=x^{\top }w+\epsilon .$$

• Given $w$, our prediction $\hat{y}$ for $y$ at $x$ is

$$\hat{y}=x^{\top }w.$$

• We can define a loss function $\ell (y,\hat{y})$ which measures the penalty paid for predicting $\hat{y}$ when the true value is $y$. e.g.,

$$\ell (y,\hat{y})=(y-\hat{y}{)}^2\text{squared loss}.$$

• Idea: find an estimator $w$ such that the expected loss

$$R(w)={\mathbb{E}}_{(x,y)\sim p(x,y)}\left[\ell (y,\hat{y})\right].$$

• Now suppose we are given a labeled training set $(x_i,y_i)$ $(i=1,\dots ,N)$ which are iid sampled from $p(x,y)$.

• By law of large numbers (LLN), $R(w)$ can be approximated by

$$L(w)=\frac{1}{N}\sum _{i=1}^N\ell (y_i,{\hat{y}}_i)=\frac{1}{N}\sum _{i=1}^N{\left(y_i-{\hat{y}}_i\right)}^2.$$

• Let $Y=(y_1,\dots ,y_N{)}^{\top }$ and

$$X=\left(\begin{array}{ccccc}1& x_{11}& x_{12}& \cdots & x_{1p}\\ 1& x_{21}& x_{22}& \cdots & x_{2p}\\ ⋮& ⋮& ⋮& & ⋮\\ 1& x_{N1}& x_{N2}& \cdots & x_{Np}\end{array}\right).$$

Then

$$L(w)=\frac{1}{N}\cdot \Vert Y-Xw{\Vert }_2^2.$$

• In other words, our estimator $\hat{w}$ should be such that $X\hat{w}$ is closest to $Y$. That is,

$$\Vert Y-X\hat{w}{\Vert }_2^2\le \Vert Y-Xw{\Vert }_2^2\text{ for any }w\in {\mathbb{R}}^m.$$

• Obviously, such a $\hat{w}$ best explains the data and is called a least squares estimator.

Theorem 1.

(i) A $\hat{w}$ is an LSE iff $(X^{\top }X)\hat{w}=X^{\top }Y$.

(ii) If $X^{\top }X$ has full rank, then the LSE is unique and is given by $\hat{w}=(X^{\top }X{)}^{-1}{X}^{\top }Y$.

$\text{Proof.}$ Obviously, part (ii) follows directly from part (i).

The 1st pf for part (i):

$$\begin{array}{rl}L(w)& =\frac{1}{N}\Vert Y-Xw{\Vert }_2^2=\frac{1}{N}(Y-Xw{)}^{\top }(Y-Xw)\\ & =\frac{1}{N}\left[Y^{\top }Y-2Y^{\top }Xw+w^{\top }{X}^{\top }Xw\right].\end{array}$$ $$\Rightarrow \frac{\partial L(w)}{\partial w}=\frac{1}{N}\left[-2X^{\top }Y+2X^{\top }Xw\right]=0\iff X^{\top }Xw=X^{\top }Y.$$

---

The 2nd pf for part (ii):

(Sufficiency $\Leftarrow$). Let $\hat{w}$ satisfy $(X^{\top }X)\hat{w}=X^{\top }Y$.

$$\Vert Y-X\hat{w}{\Vert }_2^2=\Vert Y-X\hat{w}+X\hat{w}-X\hat{w}{\Vert }_2^2=\Vert Y-X\hat{w}{\Vert }_2^2+\Vert X\hat{w}-X\hat{w}{\Vert }_2^2,$$

as $(X\hat{w}-X\hat{w}{)}^{\top }(Y-X\hat{w})=(\hat{w}-\hat{w}{)}^{\top }(X^{\top }Y-X^{\top }X\hat{w})=0$.

$$\Rightarrow \Vert Y-Xw{\Vert }_2^2\ge \Vert Y-X\hat{w}{\Vert }_2^2.$$

(Necessity $\Rightarrow$) Let $\tilde{w}$ be another LSE, that is,it minimize$\Vert Y-Xw{\Vert }_2^2$ Then we must have that$\Vert X\hat{w}-X\tilde{w}{\Vert }_2^2=0$ implying that $\Vert X\hat{w}=X\tilde{w}{\Vert }_2^2$ and thus

$$X^{\top }X\tilde{w}=X^{\top }X\hat{w}=XY.$$