MIT 18.065 - Matrix Methods in Data Analysis & Machine Learning Flashcards

Question 1

What is the primary goal of Singular Value Decomposition (SVD)?

Accepted Answer

SVD decomposes a matrix $A$ into three simpler matrices: $A = U \Sigma V^T$. Its primary goal is to reveal the underlying structure of a matrix, including its rank, range, and null space, and to provide a stable way to compute low-rank approximations.

Question 2

Describe the components of the SVD of a matrix $A$.

Accepted Answer

For $A = U \Sigma V^T$:
- $U$: Left singular vectors (orthogonal matrix, columns span the column space of $A$).
- $\Sigma$: Singular values (diagonal matrix with non-negative, decreasing values).
- $V$: Right singular vectors (orthogonal matrix, columns span the row space of $A$).
The columns of $U$ and $V$ are orthonormal.

Question 3

How can SVD be used for low-rank approximation?

Accepted Answer

By keeping only the largest $k$ singular values and their corresponding singular vectors, we can construct a rank-$k$ approximation $A_k = U_k \Sigma_k V_k^T$. This $A_k$ is the best possible approximation to $A$ in terms of Frobenius norm and spectral norm, crucial for data compression and noise reduction.

Question 4

Provide an application of SVD in data analysis.

Accepted Answer

**Image Compression:** An image can be represented as a matrix of pixel values. Applying SVD and then reconstructing the image using only the top $k$ singular values and vectors significantly reduces storage size while retaining most visual information.

Question 5

What is the main objective of Principal Component Analysis (PCA)?

Accepted Answer

PCA is a dimensionality reduction technique that transforms a dataset of possibly correlated variables into a set of linearly uncorrelated variables called principal components. Its goal is to capture as much variance as possible in the fewest possible components.

Question 6

How does PCA relate to SVD?

Accepted Answer

PCA can be performed using SVD. If $X$ is a centered data matrix (mean of each column is zero), the principal components are the right singular vectors ($V$) of $X$, and the singular values ($\Sigma$) are related to the standard deviations of the principal components. Specifically, the covariance matrix $X^T X$ has eigenvectors $V$ and eigenvalues $\Sigma^2$.

Question 7

What are 'principal components' in PCA?

Accepted Answer

Principal components are new orthogonal axes (directions) in the data space that capture the maximum variance. The first principal component captures the most variance, the second captures the most remaining variance orthogonal to the first, and so on. They are linear combinations of the original features.

Question 8

When is PCA particularly useful?

Accepted Answer

PCA is useful for:
- **Dimensionality Reduction:** Reducing the number of features while retaining most of the information.
- **Data Visualization:** Projecting high-dimensional data onto 2 or 3 principal components for plotting.
- **Noise Reduction:** Lower-rank approximations can filter out noise by discarding components with small variances.

Question 9

State the general form of the linear least squares problem.

Accepted Answer

Given a system $A\mathbf{x} = \mathbf{b}$ where $A$ is an $m 	imes n$ matrix ($m > n$, an overdetermined system), the least squares problem seeks to find $\mathbf{x}$ that minimizes the Euclidean norm of the residual: $\min_{\mathbf{x}} \|A\mathbf{x} - \mathbf{b}\|_2^2$.

Question 10

How are the normal equations used to solve the least squares problem?

Accepted Answer

The solution $\hat{\mathbf{x}}$ to the least squares problem satisfies the normal equations: $A^T A \hat{\mathbf{x}} = A^T \mathbf{b}$. If $A^T A$ is invertible (i.e., $A$ has full column rank), then $\hat{\mathbf{x}} = (A^T A)^{-1} A^T \mathbf{b}$.

Question 11

What is the geometric interpretation of the least squares solution?

Accepted Answer

The least squares solution $\hat{\mathbf{x}}$ finds the vector $A\hat{\mathbf{x}}$ in the column space of $A$ that is closest to $\mathbf{b}$. This means $A\hat{\mathbf{x}}$ is the orthogonal projection of $\mathbf{b}$ onto the column space of $A$. The residual vector $(\mathbf{b} - A\hat{\mathbf{x}})$ is orthogonal to the column space of $A$.

Question 12

In what real-world scenario is least squares commonly applied?

Accepted Answer

**Linear Regression:** Fitting a linear model to data points. Given observed data $(x_i, y_i)$, we want to find coefficients $m, c$ for $y = mx + c$ that minimize the sum of squared differences between predicted and actual $y$ values. This extends to multiple linear regression with multiple features.

Question 13

What is the purpose of regularization in least squares (e.g., Ridge Regression)?

Accepted Answer

Regularization adds a penalty term to the least squares objective function to prevent overfitting, especially when features are highly correlated or the number of features is large. Ridge Regression adds an $L_2$ penalty: $\min_{\mathbf{x}} \|A\mathbf{x} - \mathbf{b}\|_2^2 + \lambda \|\mathbf{x}\|_2^2$, where $\lambda > 0$ is the regularization parameter.

Question 14

What is the fundamental idea behind the Fourier Transform?

Accepted Answer

The Fourier Transform decomposes a function (or signal) into its constituent frequencies. It transforms a signal from the time (or spatial) domain into the frequency domain, revealing the amplitudes and phases of the sine and cosine waves that sum up to the original signal.

Question 15

Explain the difference between Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT).

Accepted Answer

The **DFT** is the mathematical definition for transforming a finite sequence of discrete data points into the frequency domain. The **FFT** is an efficient algorithm for computing the DFT. It significantly reduces the computational complexity from $O(N^2)$ to $O(N \log N)$, making Fourier analysis practical for large datasets.

Question 16

How is Fourier Analysis applied in signal processing?

Accepted Answer

Fourier analysis is used for:
- **Filtering:** Removing unwanted frequencies (e.g., noise) from a signal.
- **Spectral Analysis:** Identifying dominant frequencies and their strengths in a signal.
- **Compression:** Representing signals more compactly by discarding high-frequency components that contribute less to the overall signal.

Question 17

Why are randomized algorithms becoming important in matrix methods for data analysis?

Accepted Answer

For extremely large matrices (common in modern data), deterministic algorithms for SVD, PCA, or solving linear systems can be computationally prohibitive (too slow or memory-intensive). Randomized algorithms offer significant speedups and memory savings by working with smaller, 'sketched' versions of the original data, while still providing accurate approximations.

Question 18

Describe the core idea behind randomized SVD.

Accepted Answer

Randomized SVD typically involves two main steps:
1.  **Sketching:** Project the original large matrix $A$ onto a lower-dimensional subspace using a random matrix $G$, creating a smaller matrix $Y = AG$. This captures the 'range' of $A$.
2.  **Factorization:** Compute a standard SVD on the smaller matrix $Y$ (or a related matrix) to obtain an approximation of the SVD of $A$ with high probability.

Question 19

What are the main benefits of using randomized algorithms for matrix computations?

Accepted Answer

The main benefits include:
-   **Speed:** Significantly faster for large matrices, often near-optimal.
-   **Memory Efficiency:** Requires less memory as it operates on smaller sketches.
-   **Scalability:** Better suited for distributed and parallel computing environments.
-   **Robustness:** Can be less sensitive to numerical precision issues in some cases.

Question 20

What is the Moore-Penrose Pseudoinverse and its relation to least squares?

Accepted Answer

The Moore-Penrose pseudoinverse $A^+$ is a generalization of the matrix inverse. For a full-rank matrix $A$, the least squares solution $\hat{\mathbf{x}} = (A^T A)^{-1} A^T \mathbf{b}$ can be written as $\hat{\mathbf{x}} = A^+ \mathbf{b}$, where $A^+ = (A^T A)^{-1} A^T$. It provides a unique solution even for singular or non-square matrices by minimizing the norm of the solution.

Question 21

Define the Frobenius Norm of a matrix $A$.

Accepted Answer

The Frobenius norm of an $m 	imes n$ matrix $A$ is defined as $\|A\|_F = \sqrt{\sum_{i=1}^m \sum_{j=1}^n |a_{ij}|^2}$. It is analogous to the Euclidean norm for vectors and is often used to measure the 'size' or 'magnitude' of a matrix, particularly in low-rank approximation problems (e.g., SVD).

Question 22

How do eigenvalues and eigenvectors relate to PCA?

Accepted Answer

If $C$ is the covariance matrix of a centered data matrix, then the eigenvectors of $C$ are the principal components, and their corresponding eigenvalues represent the amount of variance explained by each principal component. The principal components are ordered by their eigenvalues in decreasing order, indicating their importance.

Question 23

What is the concept of a 'data matrix' in data analysis?

Accepted Answer

A data matrix typically represents a dataset where rows correspond to individual observations or samples, and columns correspond to different features or variables. For example, in a dataset of house prices, each row might be a house, and columns could be 'square footage', 'number of bedrooms', 'price', etc. This structure is fundamental for applying matrix methods.

MIT 18.065 - Matrix Methods in Data Analysis & Machine Learning

Cards in this deck

Related Flashcard Sets

JLPT N2 - Upper-Intermediate Japanese Kanji, Grammar & Expressions

CompTIA Network+ (N10-008) - Networking Fundamentals & Subnetting

HSK 4 - Intermediate Chinese Vocabulary & Grammar

CompTIA Network+ (N10-008) - Networking Fundamentals & Protocols