Given a dataset \[\mathcal{D} = \{(x_1, y_1), (x_2, y_2), (x_3, y_3), \ldots, (x_n, y_n)\}\] of data points \(x_i \in \mathbb{R}^d\) and the corresponding labels \(y_i \in \mathbb{R}\), a linear regression is a model that predicts a label \(\hat{y}_i\) for each input vector \(x_i\) by a relation: \[\hat{y}_i = x_i^Tw + b, \quad i=1, 2, \ldots , n\] where \(w = [w_1\ w_2\ \ldots \ w_d]^T\) is a \(d\) dimensional weight vector.
Introduce a constant feature 1 to each of the data point and construct a data matrix \(A\) of size \(n \times (d+1)\), where each row is one data-point (the last column being all ones): \[A = \begin{bmatrix} \rule[.2ex]{1em}{0.2pt} & x_1^T & \rule[.2ex]{1em}{0.2pt} & 1 \\ \rule[.2ex]{1em}{0.2pt} & x_2^T & \rule[.2ex]{1em}{0.2pt} & 1 \\ & \vdots & & 1 \\ \rule[.2ex]{1em}{0.2pt} & x_n^T & \rule[.2ex]{1em}{0.2pt} & 1 \end{bmatrix}\]
Similarly, redefine the weight vector to a \((d+1)\)-dimensional vector: \[w = [ w_1 \ w_2\ \ldots \ w_d \ b]^T\]
With these modifications, the predictions for all the \(n\) data-points can be written in a combined form as \(Aw\).
If \(y = [y_1\ y_2\ \ldots \ y_n]^T\) be the \(n\times 1\) column vector of the actual labels, the problem is to find the best (in the least square sense) solution \(w\) of the equation \[Aw = y\]
The optimum solution is obtained by solving the normal equation: \[A^TAw = A^T y\]
In case, \(A^TA\) is invertible, the optimum solution \[\hat{w} = (A^TA)^{-1}A^Ty\]
In case, \(A^TA\) is not invertible, we need to replace \((A^TA)^{-1}\) with the pseudo inverse \((A^TA)^\dagger\).
Polynomial regression: Transform the features of the data-points via a feature map \(\phi\) which takes as input the features and produces all possible powers and combination of powers of features upto degree \(p\) and then perform linear regression in the transformed feature space. The result is same as that of the linear regression except for the fact that the data matrix \(A\) now contains as its rows \(\phi (x_i)^T\), \(x_i\) being the \(i\)-th data point.
Linear regression with regularization: The loss function for the regularized linear regession, also known as the ridge regression is given by \[L(w) = \dfrac{1}{2} \left(\Vert A w -y\Vert^2 + \lambda \Vert w\Vert^2\right)\] Minimizing the loss function for the optimum weight \(\hat{w}\) leads to solving the equation \[(A^TA+\lambda I)\hat{w} = A^T y\] which gives \[\hat{w} = (A^TA+\lambda I)^{-1} A^T y\]
Too small value of \(\lambda\) leads to overfitting. (It is almost no regularizaton)
Too large value of \(\lambda\) leads to underfitting.
Given a square matrix \(A\), an eigenvalue \(\lambda\) is a scalar so that for some vector \(x\), the equation \[Ax =\lambda x\] is satisfied. The corresponding vector \(x\) is known as an eigenvector.
The eigenvalues can be obtained by solving the characteristic equation \[\det(A-\lambda I)=0\] For a matrix \(A\) of size \(n\times n\), this is a polynomial equation in \(\lambda\) of degree \(n\). Its \(n\) roots are the eigenvalues of \(A\).
The eigenvectors are the solutions of the equation \[(A-\lambda I)x =0\] That is to say that the eigenvectors lie in the null space of the matrix \((A-\lambda I)\), for each \(\lambda\).
Geometrically, eigenvectors are vectors whose direction doesn’t change when they are multiplied by \(A\). They are only stretched by a stretching factor \(\lambda\).
For matrices that are diagonal, upper triangular or lower triangular, the eigenvalues are the entries on the main diagonal.
Eigenvalues of similar matrices are exactly the same.
If \(\lambda\) is an eigenvalue of \(A\) with an eigenvector \(v\), then \(\lambda^k\) is an eigenvalue of \(A^k\) with the same eigenvector \(v\). In addition, if \(A\) is invertible, then \(\lambda^{-1}\) (that is \(1/\lambda\)) is an eigenvalue of \(A^{-1}\) with the same eigenvector.
Eigenvalues of \(A^T\) are same as those of \(A\). However, the eigenvectors are not the same.
If \(\lambda_1\), \(\lambda_2\), …, \(\lambda_n\) be the \(n\) eigenvalues of \(A\), then \[\begin{aligned} \lambda_1 +\lambda_2 + \ldots + \lambda_n & = & \mathrm{trace}(A) \\ \lambda_1 \lambda_2 \cdots \lambda_n & =& \det (A)\end{aligned}\]
A symmetric matrix has all its eigenvalues real.
Eigenvectors associated with distinct eigenvalues are independent.
A square matrix \(A\) is said to be diagonalizable if there exists an invertible matrix \(P\) such \[P^{-1} A P = \Lambda,\] a diagonal matrix.
For a square matrix \(A\) of size \(n\times n\), if the \(n\) eigenpairs are \((\lambda_1, v_1)\), \((\lambda_2, v_2)\), \(\ldots\), \((\lambda_n, v_n)\), form a matrix \(P\) be formed by taking as its columns the vectors \(v_1\), \(v_2\), \(\ldots\), \(v_n\), respectively: \[P = \begin{bmatrix} \mid & \mid & \cdots & \mid \\ v_1 & v_2 & \cdots & v_n \\ \mid & \mid & \cdots & \mid \end{bmatrix}\] This matrix \(P\) diagonalizes the matrix \(A\), that is, the product \(P^{-1}AP\) is a diagonal matrix whose diagonal entries are the corresponding eigenvalues: \[P^{-1}AP = \Lambda = \begin{bmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots \\ & & & \lambda_n\end{bmatrix}\]
Conversely, given matrix \(P\) and the diagonal matrix \(\Lambda\), we can construct the matrix \(A\) as \[A = P\Lambda P^{-1}\]
The diagonalizing matrix \(P\) is not unique.
Not all matrices possess \(n\) linearly independent eigenvectors, so not all matrices are diagonalizable.
If \(A\) is diagonalized by \(P\), so that \(A = P \Lambda P^{-1}\), then for any integer \(k\): \[A^k = P \Lambda^k P^{-1}\]
A real matrix \(Q\) is said to be orthogonal if and only if \[Q^TQ=I \Rightarrow Q^{-1} = Q^T.\]
The columns of an orthogonal matrix are orthonormal.
If \(A\) is real and symmetric matrix (\(A^T=A\)), then:
Eigenvalues of \(A\) are real.
Eigenvectors associated with distinct eigenvalues are orthogonal.
\(A\) is orthogonally diagonalizable, that is, \(\exists\) an orthogonal matrix \(Q\) such that \(A=Q\Lambda Q^T\) for a diagonal matrix \(\Lambda\). The matrix \(Q\) contains, as its columns, the normalized eigenvectors of \(A\).