The Mathematics of ECE

Logistics

A square matrix $Q$ is called orthogonal if its columns are an orthonormal set, i.e. $Q^{T} Q = I$ .
Drill: Prove that every orthogonal matrix also has orthogonal rows.
- Hint: what is one way to interpret the statement $Q^{T} Q = I$ ?
Drill: Prove that every orthogonal matrix has determinant $\pm 1$ .
- Hint: Recall two properties of the determinant are $det (A B) = det (A) det (B)$ and $det (A^{T}) = det (A)$ .
A square matrix $S$ is called symmetric if it is equal to its transpose, i.e. $S^{T} = S$ .
Properties:
- The set of symmetric matrices is a vector subspace of the set of all real square matrices.
- $A^{- 1}$ is symmetric if and only if $A$ is symmetric.
- All symmetric matrices are diagonalizable. Further, for any symmetric matrix $S$ there exists an orthonormal set of eigenvectors such that $S$ has eigendecomposition $S = V Λ V^{T}$ , where $V$ is an orthogonal matrix; all eigenvalues are guaranteed to be real, hence $Λ$ is a real diagonal matrix.
  - (These are results of the spectral theorem, which really deserves its own lecture…)
Drill: Prove that for symmetric matrix $S$ and any positive integer $n$ the matrix $A^{n}$ is symmetric.

Any matrix $A \in R^{m \times n}$ may be described by two orthogonal matrices $U \in R^{m \times m}, V \in R^{n \times n}$ and a diagonal (up to the matrix border) non-negative matrix $Σ$ as $A = U Σ V^{T}$

Visualization of the SVD for a 2x2 matrix
(reproduced with permission from Wikipedia)
Intuition: The SVD is a powerful tool to describe the action of any matrix in terms of an orthonormal change of basis ( $V^{T}$ ), non-negative component-wise scaling ( $Σ$ ), and an orthonormal basis reconstruction ( $U$ ).
Drill: Let $A$ have SVD $A = U Σ V^{T}$ . Prove that $A^{T} A$ and $A A^{T}$ share all of their nonzero eigenvalues, and further show that these eigenvalues are exactly the squares of the nonzero diagonal elements of $Σ$ .

Given a matrix $A \in R^{m \times n}$ and a vector $b \in R^{m}$ , $\underset{x \in R^{n}}{minimize} | | A x - b | |_{2}^{2}$
Practical Examples:
- To find the line of best fit over a series of points ${(t_{i}, y_{i})}_{i = 1}^{m}$ , $A = [\begin{matrix} 1 & t_{1} \\ 1 & t_{2} \\ ⋮ & ⋮ \\ 1 & t_{m} \end{matrix}], b = [\begin{matrix} y_{1} \\ y_{2} \\ ⋮ \\ y_{m} \end{matrix}]$

Practical Examples (cont.):
- To find the $(n - 1)$ th order polynomial of best fit over a series of points ${(t_{i}, y_{i})}_{i = 1}^{m}$ , $A = [\begin{matrix} 1 & t_{1} & t_{1}^{2} & \dots & t_{1}^{n - 1} \\ 1 & t_{2} & t_{2}^{2} & \dots & t_{2}^{n - 1} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & t_{m} & t_{m}^{2} & \dots & t_{m}^{n - 1} \end{matrix}], b = [\begin{matrix} y_{1} \\ y_{2} \\ ⋮ \\ y_{m} \end{matrix}]$
- To find the best fit fourier series over a series of points ${(t_{i}, y_{i})}_{i = 1}^{m}$ , $A = [\begin{matrix} 1 & ω^{t_{1}} & ω^{2 t_{1}} & \dots & ω^{(n - 1) t_{1}} \\ 1 & ω^{t_{2}} & ω^{2 t_{2}} & \dots & ω^{(n - 1) t_{2}} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & ω^{t_{m}} & ω^{2 t_{m}} & \dots & ω^{(n - 1) t_{m}} \end{matrix}], b = [\begin{matrix} y_{1} \\ y_{2} \\ ⋮ \\ y_{m} \end{matrix}]$ where $ω = e^{j \frac{2 π}{n}}$

Given a matrix $A \in R^{m \times n}$ and a vector $b \in R^{m}$ , $\underset{x \in R^{n}}{minimize} | | A x - b | |_{2}^{2}$
Drill: What is the minimum value $| | A x - b | |_{2}^{2}$ can take over all possible $x$ ?
For the following drills, assume $rank (A) = min (m, n)$
- Drill: If $m = n$ , how many solutions to the least squares problem are there? What is a closed form expression for these solutions?
- Drill: If $m < n$ , how many solutions to the least squares problem are there? What is a closed form expression for these solutions?
  - Hint: Recall that every set of vectors has a linearly independent subset which have the same span.
  - Hint: Recall that every linearly independent set of vectors in $R^{m}$ which span the entirety of $R^{m}$ contains exactly $m$ vectors.
- Drill: If $m > n$ , how many solutions to the least squares problem are there? What is a closed form expression for these solutions?

Luckily, the least squares problem is convex, so we can solve by setting the derivative equal to 0: $\hat{x} = (A^{T} A)^{- 1} A^{T} b$
- Issue when $m < n$ , $A^{T} A$ is rank-deficient and can’t be inverted…
The pseudoinverse of $A$ is defined using the compact SVD as $A^{+} = V Σ^{- 1} U^{T}$ .
Drill: Prove directly by substitution that $A A^{+}$ is a projection matrix onto the column space of $A$ .

Prove $| | Q x | |_{2}^{2} = | | x | |_{2}^{2}$ for any orthogonal matrix $Q \in R^{n \times n}$ and arbitrary vector $x \in R^{n}$ . In other words, multiplying by an orthogonal matrix does not change the norm of a vector.
Prove that the transpose of an orthogonal matrix is still an orthogonal matrix.
Let $B = {x \in R^{n} such that | | x | |_{2}^{2} = 1}$ . Prove that the action of any arbitrary orthogonal matrix $Q \in R^{n \times n}$ is a bijective endomorphism, i.e. ${Q x | \forall x \in B} = B$ .
Let $Σ \in R^{n \times n}$ be a non-negative diagonal matrix with entries in descending order, i.e. $σ_{1} \geq σ_{2} \geq \dots \geq σ_{n}$ . Prove that $σ_{1}^{2} = max_{y \in B} | | Σ y | |_{2}^{2}$ .
- Hint: assume that $y \neq e_{1}$ . In this case, there exists some index $i^{⋆}$ such that $y_{i^{⋆}}^{2} > 0$ . Another feasible point in $B$ is $y^{'}$ , where all the entries are the same as those in $y$ save that $y_{1}^{'} = \sqrt{y_{1}^{2} + y_{i^{⋆}}^{2}}$ and $y_{i^{⋆}}^{'} = 0$ . Which has a larger objective value?
The operator norm of a matrix $| | A | |$ is defined as $| | A | |^{2} = max_{x \in B} | | A x | |_{2}^{2}$ Using the previous results, solve for the operator norm in terms of the singular values of $A$ .