Math for Machine Learning - Chapter 14: Gram-Schmidt Process and QR Decomposition

This expert-level quiz delves into the intricacies of the Gram-Schmidt process and QR decomposition, two fundamental tools in linear algebra for machine learning. Moving beyond basic application, these questions will challenge your understanding of numerical stability, algorithmic variants, geometric interpretations, and practical applications in solving least squares problems. You will be tested on the subtle but critical differences between Classical and Modified Gram-Schmidt, the reasons for preferring Householder or Givens methods, and the deep connections between the factorization $A=QR$ and properties like determinants, rank, and condition numbers.

To succeed, you must be familiar with the following concepts and formulae:

Gram-Schmidt Orthogonalization:

Given a basis ${\mathbf{v}_1, \dots, \mathbf{v}_n}$, an orthogonal basis ${\mathbf{u}_1, \dots, \mathbf{u}_n}$ is constructed as:

• $\mathbf{u}_1 = \mathbf{v}_1$

• $\mathbf{u}_k = \mathbf{v}_k - \sum_{j=1}^{k-1} \text{proj}_{\mathbf{u}_j}(\mathbf{v}_k) = \mathbf{v}_k - \sum_{j=1}^{k-1} \frac{\langle \mathbf{v}_k, \mathbf{u}_j \rangle}{\|\mathbf{u}_j\|^2} \mathbf{u}_j$

An orthonormal basis ${\mathbf{q}_1, \dots, \mathbf{q}_n}$ is then $\mathbf{q}_k = \frac{\mathbf{u}_k}{\|\mathbf{u}_k\|}$.

QR Decomposition:

Any real matrix $A$ with linearly independent columns can be factored as $A = QR$, where:

• $Q$ is a matrix with orthonormal columns ($Q^T Q = I$).

• $R$ is an upper triangular, invertible matrix.

The entries of R are given by $r_{ij} = \langle \mathbf{a}_j, \mathbf{q}_i \rangle$ for $i<j$ and $r_{ii} = \| \mathbf{a}_i - \sum_{k=1}^{i-1} r_{ki} \mathbf{q}_k \| _2$.

This quiz is designed to solidify your expertise, preparing you for advanced topics in numerical optimization and data analysis.