Unit 2 - Practice Quiz

The definition of an eigenvector of a matrix is a non-zero vector that, when multiplied by , results in a scaled version of itself. The scaling factor is the eigenvalue .

Eigen decomposition is defined only for square matrices (), which limits its direct application in many machine learning scenarios where data matrices are often rectangular.

The eigen decomposition of a matrix factors it into , where is the matrix of eigenvectors and is a diagonal matrix containing the corresponding eigenvalues.

The eigenvectors of a covariance matrix point in the directions of the greatest variance (spread) of the data. The corresponding eigenvalues indicate the magnitude of this variance. This is the core idea behind PCA.

Unlike eigen decomposition, SVD is a general factorization that can be applied to any rectangular matrix, making it more widely applicable in machine learning.

The SVD of a matrix is given by . The matrix is a diagonal matrix containing the singular values of , which are always non-negative and are ordered from largest to smallest.

In SVD, both and are orthogonal matrices. This means their columns are orthonormal vectors, and their transpose is equal to their inverse ( and ).

The magnitude of the singular values indicates their importance. Larger singular values correspond to directions that capture more of the variance or "energy" of the data in the matrix.

PCA is a dimensionality reduction technique used to transform a high-dimensional dataset into a lower-dimensional one by finding new uncorrelated variables (principal components) that capture the maximum variance.

Geometrically, PCA performs a rotation of the original coordinate system to a new one. The axes of this new system, called principal components, are aligned with the directions of maximum variance in the data.

From an optimization perspective, the first principal component is defined as the direction (a linear combination of the original features) along which the projected data has the largest possible variance.

The principal components are the eigenvectors of the data's covariance matrix (or the correlation matrix, if the data is standardized). The eigenvalues indicate the amount of variance captured by each component.

By construction, the principal components are orthogonal to each other. This means that in the new feature space, the resulting variables are linearly uncorrelated, which is a desirable property.

LDA is a supervised dimensionality reduction technique. Its main objective is to project data onto a lower-dimensional space in a way that maximizes the distance between the means of different classes while minimizing the variance within each class.

The key difference is that LDA is a supervised algorithm because it uses the class labels of the data to find the best projection for classification. PCA is unsupervised and only considers the variance of the data, ignoring any class labels.

The optimization objective of LDA is to find a projection that maximizes the distance between the centers of the different classes (between-class variance) and simultaneously minimizes the spread of data within each class (within-class variance).

Because LDA explicitly tries to model the difference between classes, it is often used as a dimensionality reduction step before applying a classification model, such as in face recognition or text classification.

A user-item interaction matrix is a common way to represent user preferences. The rows represent users, the columns represent items, and the cells contain the ratings users have given to items (or a 1 if they've interacted with it, 0 otherwise).

Matrix factorization for recommendation systems learns latent features. These are not explicitly defined but are abstract characteristics that the model discovers to explain the observed ratings. For example, a latent feature for movies might correspond to the "amount of action" or "suitability for children".

After decomposing the user-item matrix into user-feature () and item-feature () matrices, the predicted rating for user and item is calculated by taking the dot product of the user's latent vector (row in ) and the item's latent vector (column in ). This reconstructs the original matrix, filling in the missing values.

Eigen decomposition is a factorization of a matrix into its eigenvectors and eigenvalues, defined as . This definition is strictly for square matrices (), as non-square matrices do not have eigenvalues in the same sense. To analyze a non-square matrix like , we often use SVD or compute the eigen decomposition of the square covariance matrix .

By definition, . If we apply again, we get . Applying it a third time gives . Thus, is an eigenvector of with eigenvalue .

A key property of real symmetric matrices is that their eigenvectors corresponding to distinct eigenvalues are mutually orthogonal. This property is fundamental to Principal Component Analysis (PCA), where the eigenvectors of the symmetric covariance matrix form an orthogonal basis representing the principal components.

Eigen decomposition of a covariance matrix is sensitive to the scale of the features. A feature with a much larger variance (due to scale) will dominate the first principal component, as PCA (which uses this decomposition) seeks to maximize variance. This can mask the contribution of other important but smaller-scale features. Standardization is typically required to mitigate this.

The SVD is closely related to the eigen decomposition of and . Specifically, . This is the eigen decomposition of . The diagonal entries of are the squared singular values (), which are the eigenvalues of . Therefore, the singular values are the square roots of the eigenvalues of .

The number of non-zero singular values of a matrix is equal to its rank. For an matrix, the rank is at most . In this case, and , so the maximum possible rank (and thus the maximum number of non-zero singular values) is .

The Eckart-Young-Mirsky theorem states that the best rank- approximation of a matrix in the sense of minimizing the Frobenius norm (or the spectral norm) is obtained by truncating the SVD. That is, is the closest rank- matrix to .

If , then its inverse is . The singular values of are the diagonal entries of , which are , where are the singular values of . This holds because an invertible matrix must have all non-zero singular values.

Geometrically, PCA performs a rotation of the coordinate system. The first principal component is the direction in which the data varies the most. The second principal component is the direction orthogonal to the first that captures the most remaining variance, and so on. These components form a new orthogonal basis for the data.

Minimizing the reconstruction error (the error between the original data points and their compressed-and-decompressed versions) is equivalent to maximizing the variance of the projected data. This error is precisely the sum of the squared Euclidean distances from the original points to their lower-dimensional projections.

The eigenvalues of the covariance matrix represent the variance captured by each corresponding principal component. The large drop-off after the second eigenvalue (from 8 to 0.1) indicates that the first two components capture the vast majority of the variance in the data (). The remaining two components contribute very little (total of $0.15$). This implies the data is intrinsically low-dimensional and can be reduced to 2D.

PCA calculates the eigenvectors of the covariance matrix. The formula for covariance involves the mean of the data. If the data is not centered at the origin, the first principal component might simply point from the origin to the center of the data cloud, rather than capturing the direction of maximum variance within the data cloud. Mean-centering ensures that the analysis focuses solely on the variance.

Unlike PCA, which is an unsupervised method that maximizes total variance, LDA is a supervised method that explicitly uses class labels. Its goal is to find a lower-dimensional space where the classes are as well-separated as possible. It achieves this by maximizing the ratio of between-class scatter (variance between class means) to within-class scatter (variance within each class).

The number of linear discriminants (the dimensions of the output space) in LDA is at most , where is the number of classes. This is because with classes, there are at most degrees of freedom for the positions of the class means relative to each other. For 4 classes, the maximum number of dimensions is .

The core of LDA is to find a projection that maximizes the ratio of between-class scatter to within-class scatter. This optimization problem is mathematically equivalent to solving the generalized eigenvalue problem , or . The eigenvectors are the linear discriminants.

PCA seeks the direction of maximum variance, while LDA seeks the direction of maximum class separability. If the primary source of variance in the dataset is the difference between the classes themselves, then the direction that maximizes variance (PC1) will likely be very similar to the direction that maximizes class separation (LD1).

The factorization learns a low-dimensional representation (latent features) for each user (rows of ) and each item (rows of ). The core idea is that user preferences and item attributes can be described by these latent factors. The dot product of a user's latent vector and an item's latent vector then gives a prediction for a missing rating.

A crucial aspect of matrix factorization algorithms like Alternating Least Squares (ALS) or Stochastic Gradient Descent (SGD) is that they only evaluate the loss function over the known ratings. The objective is to find latent factors that best reconstruct the observed part of the matrix, and then use these factors to generalize and predict the unobserved ratings.

The predicted rating is calculated by the dot product. For user and item , the predicted rating is . For user and item , the prediction is . Since , the model predicts a higher preference for item , so it would be recommended.

Overfitting occurs when the model learns the training data too well, including its noise, and fails to generalize to unseen data. Regularization is a standard technique to combat this. By adding a penalty term to the loss function (e.g., ), we discourage the model from learning excessively large values in the latent factor matrices, promoting a simpler and more generalizable model.

If a matrix is not diagonalizable, it means it lacks a full set of linearly independent eigenvectors. However, its behavior can still be fully characterized by the Jordan Normal Form. This decomposition reveals that the system's evolution may not just be simple scaling along axes, but can also include shearing effects represented by Jordan blocks, which are crucial for understanding the system's true dynamics.

The matrix simplifies to . The matrix is a diagonal matrix of size with ones in the first diagonal positions and zeros elsewhere. The matrix is the standard form for an orthogonal projection matrix onto the subspace spanned by the first columns of . This subspace is, by definition, the column space of .

The covariance matrix of the new data is . Since is orthogonal, is similar to . Similar matrices have the same eigenvalues. Therefore, the variances of the principal components (the eigenvalues) remain exactly the same. The new principal components themselves (the eigenvectors of ) are rotated versions of the original ones.

When the number of features is greater than the number of samples , the data lies in a subspace of dimension at most , causing to be singular. The standard and most principled approach is to first use PCA to project the data into the -dimensional subspace where class structure is preserved and is guaranteed to be non-singular (C is number of classes). After this pre-processing step, LDA can be successfully applied. This two-stage process is often called PCA+LDA or Regularized LDA.

The objective function balances reconstruction error with a regularization penalty on the magnitudes of the latent vectors. As , the penalty term dominates the objective function. To minimize the total loss, the model must make this penalty term as small as possible. The only way to do this is to force to zero, which means must converge to the zero vector, regardless of the reconstruction error for the single rating.

The condition for a matrix to be diagonalizable is that it must possess a full set of linearly independent eigenvectors that can form a basis for the vector space. Orthogonality of eigenvectors is a stronger condition guaranteed only for normal matrices (), a class which includes symmetric matrices but not all diagonalizable matrices. Therefore, for a general non-symmetric diagonalizable matrix, we can only be sure of linear independence.

The error of the best rank-k approximation is given by the Frobenius norm of the matrix formed by the discarded singular components. In this case, . The Frobenius norm of a rank-1 matrix is . Since and are unit vectors, the norm is simply the remaining singular value. More formally, . For , this sum only has one term, .

An eigenvalue of the covariance matrix represents the variance of the data along the corresponding eigenvector's direction. A zero eigenvalue means there is zero variance in that direction. This is only possible if all data points are confined to a hyperplane (an affine subspace) that is orthogonal to that eigenvector. If there are zero eigenvalues, it implies the data lies in an intersection of such hyperplanes, which defines an affine subspace of dimension . This indicates perfect multicollinearity among the features.

The LDA projection vector is the leading eigenvector of . For two classes, . The within-class scatter is . Thus, . This is a rank-1 matrix, and its only non-zero eigenvector must be in the direction of the vector that spans its column space, which is .

The key advantage of ALS is its parallel structure. When item factors are fixed, the objective function decouples into independent quadratic minimization problems for each user factor . This means all user factors can be computed in parallel. The same holds true when solving for item factors. This property allows ALS to scale effectively on distributed computing platforms like Spark, where the independent computations can be spread across many machines, making it more efficient than the inherently sequential updates of SGD in such environments.

The equation defines the stationary distribution of a Markov chain. It means that if the probability distribution of states is given by the vector , then after one transition step, the new distribution will still be . This vector represents the equilibrium state of the system, where the probability of being in any given state becomes constant over time.

A rapid decay in singular values signifies that most of the matrix's 'energy' or information is captured by the first few singular values and vectors. This means that a truncated SVD, for a small , will be an excellent approximation of the full matrix . This is the basis for techniques like PCA and data compression, as the high-dimensional matrix can be effectively represented by much smaller matrices .

Standard PCA is an algorithm that finds a low-dimensional projection maximizing variance. PPCA is a generative model that assumes observed data is generated from lower-dimensional latent variables via a linear map plus Gaussian noise. PPCA's parameters are fit by maximizing data likelihood. This probabilistic framing allows for handling missing data naturally and provides a measure of uncertainty. Standard PCA can be recovered as a special case of PPCA when the variance of the noise term approaches zero.

The between-class scatter matrix is formed by the sum of outer products of vectors , where are class means and is the overall mean. These vectors are linearly dependent (they sum to zero when weighted by class sizes) and thus span a subspace of dimension at most . Since LDA finds eigenvectors of , and the rank of this product is limited by the rank of , there can be at most non-zero eigenvalues and thus at most useful discriminant directions.

Mean imputation forces the factorization model to learn latent factors that can reconstruct the global mean for a large number of entries. For a sparse user with only a few ratings, the imputed mean values will dominate their row in the matrix. Consequently, their learned latent vector will be optimized to represent an 'average' user, not their specific, sparse preferences. This washes out individual taste and leads to generic recommendations for these users.

This is a classic scenario highlighting the difference between unsupervised PCA and supervised LDA. PCA will find the direction of maximum variance, which is along the clusters' length. Projecting onto this axis will cause the two classes to overlap completely, making classification impossible. LDA, being supervised, will ignore the direction of high variance and instead find the direction that maximizes class separability. This direction is orthogonal to the clusters' length, and projecting onto it will perfectly separate the two classes.

In the SVD of a tall matrix (), there are at most non-zero singular values. In the product , the last columns of are always multiplied by zero. The Thin SVD avoids computing these unnecessary columns of and the zero-rows of . It produces , , and such that . This decomposition is exact (not an approximation) and more memory- and computationally-efficient.

The eigenvalues of the matrix are , where are the eigenvalues of . If is the eigenvalue of closest to the shift , then will be the smallest among all . Consequently, its reciprocal, , will be the largest. Therefore, applying Power Iteration to the shifted-inverse matrix will cause it to converge to the eigenvector corresponding to this dominant eigenvalue, which is the same eigenvector corresponding to the desired eigenvalue of the original matrix .

Without constraints, the problem is ill-posed because one could arbitrarily scale up the latent factors and scale down the transformation matrix without changing the product . To obtain a unique solution that corresponds to principal components, we require the basis vectors (the columns of ) to be orthonormal. This constraint forces the solution for to be the matrix whose columns are the top eigenvectors of the covariance matrix of , which is the definition of the principal components.

Different users have different rating baselines, and different items have different average ratings. These are significant sources of variance in the data. By explicitly modeling these main effects with bias terms, we allow the more complex interaction term, , to focus on modeling the residual signal: the specific affinity of a user for an item that isn't explained by their general tendencies. This separation of concerns leads to a more accurate and interpretable model.