Chapter 7 Computational Linear Algebra Flashcards
(18 cards)
What is the computational cost of the standard matrix multiplication algorithm?
O(n^3), where n is the matrix dimension.
What does the product ŷ = Xb represent in linear regression?
The predicted outputs for a dataset X given the linear weights b.
How does the cost of adding matrices compare to multiplying them?
Addition is O(n^2), while multiplication is O(n^3) using the schoolbook method.
What is Strassen’s algorithm and its complexity?
A divide-and-conquer matrix multiplication algorithm with complexity O(n^2.81).
How many matrix multiplications does Strassen’s algorithm use?
Seven multiplications per recursive step.
Why is computing A⁻¹b to solve Ax = b a bad idea?
It is computationally inefficient and numerically unstable.
What is LU decomposition?
Decomposing matrix A into the product of a lower triangular matrix L and an upper triangular matrix U (A = LU).
What is the total computational cost of solving Ax = b using LU decomposition?
O(n^3) for LU decomposition and O(n^2) for forward and back substitution.
Why is LU decomposition without pivoting potentially unstable?
Small pivot values can lead to large errors due to division instability.
What does the ‘P’ in LUP decomposition stand for?
Permutation, used to improve numerical stability by row swapping.
What is machine epsilon?
The smallest number that, when added to 1 in floating point, gives a result different from 1.
What is a well-conditioned problem?
A problem where small changes in input cause small changes in output.
What defines a numerically stable algorithm?
It approximately solves a nearby problem when applied to (A, b).
What are eigenvectors and eigenvalues?
Vectors e such that Ae = λe, where λ is a scalar (eigenvalue).
Why are eigenvalues important in data science?
They enable dimensionality reduction by identifying dominant directions in data.
What is the power method used for?
Finding the dominant eigenvector of a matrix.
When does the power method converge to an eigenvector?
When applied repeatedly to a vector under a matrix with a unique largest eigenvalue.
What does the equilibrium distribution π of a Markov chain satisfy?
Pπ = π, where P is the transition matrix.
