Summary

What we learned: through \({\bf Ax}={\bf b}\)

• Tuples to vectors:
  • We started with wanting to perform arithmetic on groups of numbers called tuples, as in (1,2,3) + (4,5,-6) = (5,7,-3)
  • With a geometric interpretation (arrows) and dot-product, these became vectors.
  • The geometric interpretation of addition is the parallelogram, and of scalar multiplication is stretching (shrinking, flipping direction).

• The most important operation: linear combination
  • We expressed a linear combination of vectors as $$ {\bf A}{\bf x} \eql {\bf b} $$
  • The scalars are in \({\bf x}\) and the vectors are columns of \({\bf A}\).

• Coordinates:
  • If the columns of \({\bf A}\) are a new basis with its vectors expressed in standard coordinates, then the scalars in \({\bf x}\) are coordinates in that basis.
  • Then, the new-basis coordinates of any \({\bf b}\) in the standard basis (i.e., with standard coordinates) can be computed through $$ {\bf x} \eql {\bf A}^{-1}{\bf b} $$
  • When the new basis has orthogonal vectors (as is common in many graphics applications), this becomes $$ {\bf x} \eql {\bf A}^{T}{\bf b} $$ which is how you see it written in graphics books.

• Exact solution:
  • We applied row operations in succession to reduce $$ {\bf A}{\bf x} \eql {\bf b} $$ to $$ \mbox{RREF}({\bf A}){\bf x} \eql {\bf b}^\prime $$
  • When \({\bf b}\) is in the colspace of \({\bf A}\), then \({\bf x}={\bf b}^\prime\) is the solution, and applying the same operations to \({\bf I}\) produced \({\bf A}^{-1}\)
  • An exact solution implies all kinds of nice things:
    • \({\bf A}{\bf x}={\bf b}\) has a unique solution.
    • \({\bf A}^{-1}\) is unique.
    • \({\bf A}{\bf x}={\bf 0}\) has the unique solution \({\bf x}={\bf 0}\), which is the definition of linear independence of the columns.

• When exact is not possible:
  • When \({\bf b}\) is NOT in the colspace of \({\bf A}\), we did nonetheless get useful information:
    • The pivot rows are a basis for the rowspace.
    • The vectors in \({\bf A}\) occupying the same spots as the pivot columns are a basis for the colspace.
    • The dimension of the rowspace and colspace (the rank of the matrix) is the number of pivots.
  • The least-squares method gives us the colspace vector \({\bf A} \hat{\bf x}\) closest to \({\bf b}\): $$ {\bf A} \hat{\bf x}\; \approx \; {\bf b} $$ This is especially useful when \({\bf A}\) has many more rows than columns (common in curve-fitting).

• Dot product and angle:
  • Since any vector \({\bf u}\) can be first rotated and then stretched to equal any vector \({\bf v}\), we can write $$ {\bf v} \cdot {\bf u} \eql ({\bf B}_\alpha {\bf A}_\theta {\bf u}) \cdot {\bf u} \\ $$ where \({\bf A}_\theta\) performs the rotation and \({\bf B}_\alpha\) performs the stretch: \({\bf v} = {\bf B}_\alpha {\bf A}_\theta {\bf u}\)
  • This resulted, after some algebraic simplification, into the very useful relation between dot-product and angle: $$ {\bf v} \cdot {\bf u} \eql |{\bf v}| |{\bf u}| \cos(\theta) $$

• Orthogonality and projections:
  • When \({\bf A}\) is orthogonal $$ {\bf A}^{-1} \eql {\bf A}^{T} $$ because \({\bf A}^T{\bf A} = {\bf I}\) since row \(i\) in \({\bf A}^T\) (which is column \(i\) from \({\bf A}\)) multiplied by column \(j\) in \({\bf A}\) is zero, and the 1's on the diagonal come from a column's dot-product with itself.
  • The projection of \({\bf u}\) on \({\bf v}\) is a vector in the direction of \({\bf v}\) that is the "shadow" of \({\bf u}\): $$ \mbox{proj}_{\bf v}({\bf u}) \eql \alpha {\bf v} $$ where $$ \alpha \eql \left(\frac{{\bf u}\cdot {\bf v}}{{\bf v}\cdot {\bf v}} \right) $$
  • By subtracting off projections serially, we got Gram-Schmidt and the QR decomposition.
  • An orthogonal matrix when thought of as a matrix that transforms vectors has additional nice properties (it preserves lengths and dot-products).

• Eigenvectors:
  • When $$ {\bf A}{\bf x} \eql \lambda {\bf x} $$ for some vectors \({\bf x}\), such a vector is called an eigenvector and the corresponding scalar \(\lambda\) is called an eigenvalue.
  • Repeated application of \({\bf A}\) to an initial vector results in rapid convergence to the eigenvector with the highest (in magnitude) eigenvalue, provided the starting vector is not one of the other eigenvectors.
  • For symmetric matrices \({\bf A} = {\bf A}^T\), the eigenvectors form an orthogonal basis, and the eigenvalues turn out to be real (possibly negative) numbers.
  • If we place these eigenvectors into a matrix \({\bf S}\) we get the eigendecomposition $$ {\bf A} \eql {\bf S} {\bf \Lambda} {\bf S}^T $$ which we exploited in PCA.
  • For a special subclass of symmetric matrices, called positive semidefinite matrices, the eigenvalues are all negative real numbers, which plays an important role in the SVD.

• SVD/PCA:
  • For any (square or non-square) matrix \({\bf A}\) of rank \(r\), both \({\bf A}^T {\bf A}\) and \({\bf A} {\bf A}^T\) are positive semidefinite, meaning their eigenvalues are nonnegative.
  • Put the (orthonormal) eigenvectors of \({\bf A}^T {\bf A}\) into the matrix \({\bf V}\), and the (orthonormal) eigenvectors of \({\bf A} {\bf A}^T\) into \({\bf U}\). Then, $$ {\bf A} \eql {\bf U} {\bf \Sigma} {\bf V}^T $$ where \(\Sigma\) is the diagonal matrix of eigenvalues \(\sqrt{\lambda_1}, \sqrt{\lambda_2},\ldots,\sqrt{\lambda_r}\). This is the SVD.
  • We get even lower-ranked representations (useful in compression, missing-entry completion) by setting all but the top few \(\lambda_i\)'s to zero.
  • When \({\bf A}\) is a mean-centered data matrix (multidimensional samples as columns), then \({\bf A} {\bf A}^T\) is the covariance, whose eigenvectors \({\bf U}\) can be used for PCA coordinates: $$ {\bf Y} \eql {\bf U}^{-1} {\bf A} $$
  • Then \({\bf Y}\) is decorrelated with, typically, the highest variance in the first few dimensions.

• Bezier/DFT:
  • These two topics are independent; both involve linear combinations of "other things" than real-valued vectors.

  • The DFT:
    • Think of the columns of \({\bf A}\) in \({\bf Ax}={\bf b}\) as special complex vectors.
    • And both \({\bf x}\) and \({\bf b}\) as complex vectors.
    • Each element in each of these vectors is some power of \(\omega=e^{\frac{2\pi i}{N}}\), one of complex N-th roots of 1.
    • Then, with the inverse-DFT, \({\bf b}\) is the data, \({\bf A}\) has the elements of the inverse-DFT matrix, \({\bf b}\) has the "signal" and \({\bf x}\) is the vector of Fourier coefficients (containing frequency information).
    • This direction goes from frequency to signal, which we wrote as $$ {\bf DF} \eql {\bf f} $$
    • In the opposite direction, going from signal to frequency, \({\bf A}^{-1}\) is converts from data to Fourier coefficients: \({\bf x}={\bf A}^{-1} {\bf b}\), which we wrote as $$ {\bf F} \eql {\bf D}^{-1} {\bf f} \eql \frac{1}{N}{\bf D}^H{\bf f} $$ after showing that \({\bf D}\) is orthogonal.

  • Bezier:
    • This is the one topic that strays from \({\bf Ax}={\bf b}\).
    • Here, we defined two functions of this kind: $$\eqb{ x(t) & \eql & a_0 (1-t)^3 + 3a_1 t (1-t)^2 + 3a_2 t^2(1-t) + a_3 t^3\\ y(t) & \eql & b_0 (1-t)^3 + 3b_1 t (1-t)^2 + 3b_2 t^2(1-t) + b_3 t^3 }$$ where the \(a_i,b_i\) coefficients are the scalars in the linear combination of special polynomials (called Bernstein polynomials).
    • Then, with the really neat approach of parametric representation of curves, we let $$\eqb{ x(t) & \eql & \;\;\; \mbox{ x coordinate of the point } (x(t), y(t))\\ y(t) & \eql & \;\;\; \mbox{ y coordinate of the point } (x(t), y(t)) }$$ and plot the points. This is the curve we get.
    • As a bonus, if we plot the points \((a_i,b_i)\), moving them around changes their values and therefore the curve, allowing visual design with control points.