Linear Algebra Test

  • Ordinary Least Squares (OLS)
    • Least Squares Criterion
    • For \(\beta = (\beta_1, \beta_2, ... , \beta_p)^T\), define
      • Matrix Notation

        \begin{equation}
          y = \begin{pmatrix}y_1 \\ y_2 \\ \vdots \\ y_n \end{pmatrix}
          X = \begin{bmatrix}
            x_{1,1} & x_{1,2} & \cdots & x_{1,p} \\
            x_{2,1} & x_{2,2} & \cdots & x_{2,p} \\ 
            \vdots & \vdots & \ddots & \vdots \\ 
            x_{n,1} & x_{n,2} & \cdots & x_{n,p}
          \end{bmatrix} \beta =
          \begin{pmatrix}\beta_1 \\ \beta_2 \\ \vdots \\ \beta_n
          \end{pmatrix}
        \end{equation}
        

        tex7435ay0.png

    • Solving for OLS Estimate \(\hat{\beta}\) \(\hat{y} = \begin{pmatrix}\hat{y_1} \\ \hat{y_2} \\ \vdots \\ \hat{y_n}\end{pmatrix} = X\beta\) and \(Q(\beta) = \sum_{i=1}^{n}(y_i - \hat{y_i})^2 = (y-\hat{y})^T(y-\hat{y})\) OLS \(\hat{\beta}\) solves \(\frac{\partial Q(\beta)}{\partial\beta_j} = 0, j = 1, 2, 3, ..., p\)

      \begin{equation}
        \begin{align*}
          \frac{\partial Q(\beta)}{\partial\beta_j} &=  \frac{\partial}{\partial\beta_j}(\sum_{i=1}^{n} [y_i - (x_{i,1}\beta_1 + x_{i,2}\beta_2 + ... + x_{i,p}\beta_p)]^2) \\
          &= \sum_{i=1}^n2(-x_{i,j})[y_i - (x_{i,1}\beta_1 + x_{i,2}\beta_2 + ... + x_{i,p}\beta_p)] \\
          &= -2(X_{[j]})^T(y - X\beta)
        \end{align*}
      \end{equation}
      

      tex21330aJQ.png

      where \(X_{[j]}\) is the \(j_{th}\) column of \(X\)

      \begin{equation}
        \frac{\partial Q}{\partial\beta} =
        \begin{bmatrix}
          \frac{\partial Q}{\partial\beta_1} \\
          \frac{\partial Q}{\partial\beta_2} \\
          \vdots \\
          \frac{\partial Q}{\partial\beta_p}
        \end{bmatrix} = -2 \begin{bmatrix}
          X_{[1]}^T(y0 X\beta) \\
          X_{[2]}^T(y0 X\beta) \\
          \vdots \\
          X_{[p]}^T(y0 X\beta) \\
        \end{bmatrix} = -2X^T(y - X\beta)
      
      \end{equation}
      

      tex7435Y3a.png

    • So the OLS Estimates \(\hat{\beta}\) solves the "Normal Equations" \(X^T(y-X\beta) = 0\)

      \begin{equation}
        \begin{align*}
          X^T(y-X\beta) &= 0 \Longleftrightarrow \\
          X^TX\hat{\beta} &= X^Ty \Longleftrightarrow \\
          \hat{\beta} &= (X^TX)^{-1}X^Ty
        \end{align*}
      \end{equation}
      
      

      tex7435lPJ.png

      N.B For \(\hat{\beta}\) to exist (uniquely) \((X^TX)\) must be invertible and \(X\) must have Full Column Rank

      OLS Estimate:

      \begin{equation} \tag{1}
        \begin{align*}
          \hat{\beta} =
          \begin{pmatrix}
            \hat{\beta_1} \\ \hat{\beta_2} \\ \vdots \\ \hat{\beta_p}
          \end{pmatrix} = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y} && \text{\bf Fitted Values}
        \end{align*}
      \end{equation}
      
      

      tex16303xWp.png

      \begin{equation} \tag{2}
        \begin{align*}
          \hat{\mathbf{y}} &=
          \begin{pmatrix}
            \hat{y_1} \\ \hat{y_2} \\ \vdots \\ \hat{y_n}
          \end{pmatrix} = \begin{pmatrix}
            x_{1,1}\hat{\beta_1} + \cdots + x_{1,p}\hat{\beta_p} \\
            x_{2,1}\hat{\beta_1} + \cdots + x_{2,p}\hat{\beta_p} \\
            \vdots \\
            x_{n,1}\hat{\beta_1} + \cdots + x_{n,p}\hat{\beta_p} \\
          \end{pmatrix} = \\
          \mathbf{X}\hat{\beta} &= \mathbf{X(X^TX)^{-1}X^Ty = Hy}
        \end{align*}
      \end{equation} \\
      \text{Where} &&H = X(X^TX)^{-1}X^T && \text{is the n x n "Hat Matrix" or orthogonal projection matrix} 
      
      
      
      

      tex16303aaO.png

      The Hat Matrix H projects \(R^n\) onto the column-space of X Residuals:

      \begin{equation} \tag{3}
        \begin{align*}
        \hat{\epsilon} = \begin{pmatrix}
          \hat{\epsilon_1} \\ \hat{\epsilon_2} \\ \vdots \\ \hat{\epsilon_n}
        \end{pmatrix} = \mathbf{y} - \mathbf{\hat{y}} = (\mathbf{I_n} - \mathbf{H})\mathbf{y}
        \end{align*}
      \end{equation}
      
      \begin{equation} \tag{4}
        \begin{align*}
          \text{Normal Equations:} && \mathbf{X^T}(\mathbf{y} - \mathbf{X}\mathbf{\hat{\beta}}) = \mathbf{X}^T\hat{\epsilon} = \matbf{0_p} =
          \begin{pmatrix} 0 \\ \vdots \\ 0\end{pmatrix}
        \end{align*}
      \end{equation}
      

      tex16303cqE.png

      N.B. The Least-Squares Residuals vectors \(\hat{\epsilon}\) is orthogonal to the column space of X

Part 0: Preparing the PXE Server on Arch Linux

In this series I am going to demonstrate how to set up a Linux environment for power users on Arch Linux and utilize literate DevOps, using Spacemacs and Org-Babel.

Note: This step is an optional one, you can always just boot from USB stick and continue from Part 1 of the Arch Install Series

Let's configure a PXE server following the official arch linux guide.

ssh durden

Next download the latest iso file from an official repo and verify signature.

mkdir ~/archstore; cd ~/archstore
repo="http://mirror.rackspace.com/archlinux/iso/latest/"

latest_rel=$(curl -s $repo | perl \
              -ne 'print $1 . "\n" if ($_ =~ /.*href="(.*)\.iso"/)')

printf "Latest Arch release: %s\n" $latest_rel

iso=${latest_rel}.iso
sig=${latest_rel}.iso.sig
sha1="sha1sums.txt"

wget --quiet ${repo}${iso}
wget --quiet ${repo}${sig}
wget --quiet ${repo}${sha1}

printf "Files:\n"
du -sh *

shasum ${sha1}
if [[ $? -eq 0 ]]; then echo "SHA1 Sums: Correct"; fi

sudo pacman-key -v ${sig}
if [[ $? -eq 0 ]]; then echo "SIG: Verified"; fi

Show Output

Latest Arch release: archlinux-2017.04.01-x86_64

Files:
479M    archlinux-2017.04.01-x86_64.iso
8.0K    archlinux-2017.04.01-x86_64.iso.sig
8.0K    sha1sums.txt

bec7a89b9f4d76f1f9fb56285fc1e164429db773  sha1sums.txt
SHA1 Sums: Correct

==> Checking archlinux-2017.04.01-x86_64.iso.sig...
gpg: assuming signed data in 'archlinux-2017.04.01-x86_64.iso'
gpg: Signature made Sat 01 Apr 2017 02:34:21 PM EEST
gpg:                using RSA key 4AA4767BBC9C4B1D18AE28B77F2D434B9741E8AC
" [full]
SIG: Verified

Please feel free to visit Arch Master Signing Keys and make sure the signature/iso you downloaded is not compromised. There is always the possibility that you got served Malicious Image.

Information regarding the signature can be extracted with gpg --list-packets

gpg --list-packets < ${sig}

Show Output


off=0 ctb=89 tag=2 hlen=3 plen=307
:signature packet: algo 1, keyid 7F2D434B9741E8AC
    version 4, created 1491046461, md5len 0, sigclass 0x00
    digest algo 8, begin of digest 54 88
    hashed subpkt 33 len 21 (issuer fpr v4 4AA4767BBC9C4B1D18AE28B77F2D434B9741E8AC)
    hashed subpkt 2 len 4 (sig created 2017-04-01)
    subpkt 16 len 8 (issuer key ID 7F2D434B9741E8AC)
    data: [2045 bits]

Now let's mount the image and prepare the files for the PXE server

dt=$(date "+%Y%m%d")
sudo mkdir /srv/pxe
sudo mount -o loop,ro ${iso} /mnt
sudo rsync -aAXv /mnt/ /srv/pxe > rsync.log.${dt}
tail -3 rsync.log.${dt}
du -sm /srv/pxe

Show Output

sent 500,489,449 bytes  received 1,908 bytes  11,246,996.79 bytes/sec
total size is 500,361,240  speedup is 1.00

478 /srv/pxe

1 Setting up the all servers needed for PXE

We are going to use dnsmasq package to supply DHCP and TFTP functionality to your PXE server.

  • Install and configure dnsmasq
sudo pacman --quiet --noconfirm -S dnsmasq
sudo cp -rp /etc/dnsmasq.conf /etc/dnsmasq.conf_$(date "+%Y%m%d")
sudo sh -c "cat > /etc/dnsmasq.conf <<EOF 
port=0
interface=eth0
bind-interfaces
dhcp-range=192.168.10.50,192.168.10.60,12h
dhcp-boot=/arch/boot/syslinux/lpxelinux.0
dhcp-option-force=209,boot/syslinux/archiso.cfg
dhcp-option-force=210,/arch/
dhcp-option-force=66,192.168.10.102
enable-tftp
tftp-root=/srv/pxe
EOF"

Show Output

resolving dependencies...
looking for conflicting packages...

Packages (3) libnetfilter_conntrack-1.0.6-1  libnfnetlink-1.0.1-2  dnsmasq-2.76-4

Total Installed Size:  0.91 MiB

:: Proceed with installation? [Y/n]
(1/3) checking keys in keyring                                  [###########-----------------------]  33%
(2/3) checking keys in keyring                                  [######################------------]  66%
(3/3) checking keys in keyring                                  [##################################] 100%
(1/3) checking package integrity                                [#---------------------------------]   4%
(2/3) checking package integrity                                [#####-----------------------------]  16%
(3/3) checking package integrity                                [##################################] 100%
(1/3) loading package files                                     [#---------------------------------]   4%
(2/3) loading package files                                     [#####-----------------------------]  16%
(3/3) loading package files                                     [##################################] 100%
(1/3) checking for file conflicts                               [###########-----------------------]  33%
(2/3) checking for file conflicts                               [######################------------]  66%
(3/3) checking for file conflicts                               [##################################] 100%
(1/3) checking available disk space                             [###########-----------------------]  33%
(2/3) checking available disk space                             [######################------------]  66%
(3/3) checking available disk space                             [##################################] 100%
:: Processing package changes...
(1/3) installing libnfnetlink                                   [##################################] 100%
(2/3) installing libnetfilter_conntrack                         [##################################] 100%
(3/3) installing dnsmasq                                        [##################################] 100%
:: Running post-transaction hooks...
(1/2) Updating system user accounts...
(2/2) Arming ConditionNeedsUpdate...

Now start and enable(if preferrable) dnsmasq service

sudo systemctl start dnsmasq
sudo systemctl enable dnsmasq
sudo systemctl status dnsmasq

Show Output


● dnsmasq.service - fA lightweight DHCP and caching DNS server
  Loaded: loaded (/usr/lib/systemd/system/dnsmasq.service; enabled; vendor preset: disabled)
  Active: active (running) since Wed 2017-04-26 21:17:20 EEST; 12s ago
    Docs: man:dnsmasq(8)
Main PID: 1253 (dnsmasq)
  CGroup: /system.slice/dnsmasq.service
          └─1253 /usr/bin/dnsmasq -k --enable-dbus --user=dnsmasq --pid-file

Apr 26 21:17:20 durden.evolve.inc systemd[1]: Starting A lightweight DHCP and caching DNS server...
Apr 26 21:17:20 durden.evolve.inc dnsmasq[1250]: dnsmasq: syntax check OK.
Apr 26 21:17:20 durden.evolve.inc systemd[1]: Started A lightweight DHCP and caching DNS server.
Apr 26 21:17:20 durden.evolve.inc dnsmasq[1253]: started, version 2.76 DNS disabled
Apr 26 21:17:20 durden.evolve.inc dnsmasq[1253]: compile time options: IPv6 GNU-getopt DBus i18n ID…otify
Apr 26 21:17:20 durden.evolve.inc dnsmasq[1253]: DBus support enabled: connected to system bus
Apr 26 21:17:20 durden.evolve.inc dnsmasq-dhcp[1253]: DHCP, IP range 192.168.10.50 -- 192.168.10.60…e 12h
Apr 26 21:17:20 durden.evolve.inc dnsmasq-dhcp[1253]: DHCP, sockets bound exclusively to interface eth0
Apr 26 21:17:20 durden.evolve.inc dnsmasq-tftp[1253]: TFTP root is /srv/pxe
Hint: Some lines were ellipsized, use -l to show in full.
  • Set up a simple http - darkhttpd

Install the package and start the service

sudo pacman --quiet --noconfirm -S darkhttpd
sudo nohup darkhttpd /srv/pxe &

Show Output

resolving dependencies...
looking for conflicting packages...

Packages (1) darkhttpd-1.12-3

Total Download Size:   0.02 MiB
Total Installed Size:  0.08 MiB

:: Proceed with installation? [Y/n] 
:: Retrieving packages...
darkhttpd-1.12-3-i686                   0.0   B  0.00B/s 00:00 [----------------------------------]   0%
 darkhttpd-1.12-3-i686                   0.0   B  0.00B/s 00:00 [----------------------------------]   0%
 darkhttpd-1.12-3-i686                   0.0   B  0.00B/s 00:00 [----------------------------------]   0%
 darkhttpd-1.12-3-i686                  19.1 KiB   191K/s 00:00 [##################################] 100%
(1/1) checking keys in keyring                                  [##################################] 100%
(1/1) checking package integrity                                [##################################] 100%
(1/1) loading package files                                     [##################################] 100%
(1/1) checking for file conflicts                               [##################################] 100%
(1/1) checking available disk space                             [##################################] 100%
:: Processing package changes...
(1/1) installing darkhttpd                                      [##################################] 100%
:: Running post-transaction hooks...
(1/1) Arming ConditionNeedsUpdate...
[1] 1333

Check if webserver is working, it is important that server is running on port 80, so make sure you start it as root

curl -s http://localhost:80/ | egrep href

Show Output


..</a>/
EFI</a>/
arch</a>/
isolinux</a>/
loader</a>/