[Linear Algebra] Inner Product

Over-determined Linear Systems

• Over-determined linear systems
  • number of equations >> number of variables
  • data amount >> feature dimension
  • usually no solution exists

    e.g.

    Feature A	Feature B	Feature C	label
    $A_1$	$B_1$	$C_1$	$L_1$
    $A_2$	$B_2$	$C_2$	$L_2$
    $\vdots$	$\vdots$	$\vdots$	$\vdots$
    $A_{100}$	$B_{100}$	$C_{100}$	$L_{100}$

    Total data num : 100
    Feature dim : 3
    Over-determined linear system

Vector Equation Perspective

• Vector equation form
  • $\begin{bmatrix}A_1 \\A_2 \\ \vdots \\A_{100} \end{bmatrix} x_1 + \begin{bmatrix}B_1 \\B_2 \\ \vdots \\B_{100} \end{bmatrix} x_2 + \begin{bmatrix}C_1 \\C_2 \\ \vdots \\C_{100} \end{bmatrix} x_3 = \begin{bmatrix}L_1 \\L_2 \\ \vdots \\L_{100} \end{bmatrix}$
  • $\textbf{a}_1 x_1 + \textbf{a}_2 x_2 + \textbf{a}_3 x_3 = \textbf{b}$
  • Compared to original space $\mathbb{R}^{100}$ ($\textbf{a}_1, \textbf{a}_2, \textbf{a}_3, \textbf{b} \in \mathbb{R}^{100}$), $\textrm{Span}\begin{Bmatrix} \textbf{a}_1, \textbf{a}_2, \textbf{a}_3 \end{Bmatrix}$ will be a thin hyperplane
  • So it is likely that $\textbf{b} \notin \textrm{Span}\begin{Bmatrix} \textbf{a}_1, \textbf{a}_2, \textbf{a}_3 \end{Bmatrix}$, which mean no solution exists

Motivation for Least Squares

• Even if no solution exists, we want to approximately obtain the solution for an over-determined system
• Then, how can we define the best approximate solution?

Inner Product

• Given $\textbf{u}, \textbf{v} \in \mathbb{R}^n$, we can consider $\textbf{u}$ and $\textbf{v}$ as $n \times 1$ matrices
• The transpose $\textbf{u}^T$ is a $1 \times n$ matrix, and the matrix product $\textbf{u}^T \textbf{v}$ is a $1 \times 1$ matrix, which we write as a scalar without brackets
• The number $\textbf{u}^T \textbf{v}$ is called the inner product or dot product of $\textbf{u}$ and $\textbf{v}$, and it is written as $\textbf{u} \cdot \textbf{v}$

Properties of Inner Product

• Theorem : let $\textbf{u}$, $\textbf{v}$ and $\textbf{w}$ be vectors in $\mathbb{R}^n$, and let $c$ be a scalar

  • a ) $\textbf{u} \cdot \textbf{v} = \textbf{v} \cdot \textbf{u}$
  • b ) $(\textbf{u} + \textbf{v}) \cdot \textbf{w} = \textbf{u} \cdot \textbf{w} + \textbf{v} \cdot \textbf{w}$
  • c ) $(c \textbf{u}) \cdot \textbf{v} = c (\textbf{u} \cdot \textbf{v}) = \textbf{u} \cdot (c \textbf{v})$
  • d ) $\textbf{u} \cdot \textbf{u} \geq 0$, and $\textbf{u} \cdot \textbf{u} = 0$ if and only if $\textbf{u} = \textbf{0}$

• Properties (b) and (c) can be combined to produce the following rule

  • $(c_1 \textbf{u}_1 + \cdots + c_p \textbf{u}_p) \cdot \textbf{w} = c_1 (\textbf{u}_1 \cdot \textbf{w}) + \cdots + c_p (\textbf{u}_p \cdot \textbf{w})$