\documentclass{article} \usepackage[utf8]{inputenc} \usepackage{amsmath,amssymb} \usepackage{algorithm,algpseudocode} \usepackage{bm} \usepackage{hyperref} \usepackage{float} \usepackage{subcaption} \usepackage{enumitem} \usepackage{xcolor} \definecolor{darkgreen}{rgb}{0.0, 0.5, 0.0} \definecolor{aaltoBlue}{RGB}{0, 51, 102} \definecolor{pinegreen}{cmyk}{0.92,0,0.59,0.25} \definecolor{royalblue}{cmyk}{1,0.50,0,0} \definecolor{lavander}{cmyk}{0,0.48,0,0} \definecolor{violet}{cmyk}{0.79,0.88,0,0} \definecolor{lightblue}{RGB}{173, 216, 230} \usepackage{tikz} \usepackage{pgfplots} \usetikzlibrary{calc,arrows.meta,positioning,fit,shapes.geometric,shapes.misc,intersections,patterns,decorations.pathreplacing,backgrounds,matrix} \usepgfplotslibrary{fillbetween,groupplots} \setcounter{secnumdepth}{-\maxdimen} % Long unbreakable tokens (the ISO/IEC author names in citations, term names % in the title) otherwise overflow the margin by a few points; a modest % emergency stretch lets TeX loosen the paragraph instead. \emergencystretch=2em \usepackage{mleftright} % Project macros used by this entry (auto-extracted). \newcommand{\LapMat}[1]{\mL^{(#1)}} \newcommand{\defeq}{:=} \newcommand{\eigval}[1]{\lambda_{#1}} \newcommand{\eigvalgen}{\lambda} \newcommand{\expcoeff}{\beta} \newcommand{\feature}{x} \newcommand{\featuredim}{d} \newcommand{\featureidx}{j} \newcommand{\featuremtx}{\mX} \newcommand{\featurevec}{\vx} \newcommand{\graph}{\mathcal{G}} \newcommand{\iteridx}{t} \newcommand{\labelvec}{\vy} \newcommand{\lrate}{\eta} \newcommand{\mA}[0]{{\bf A}} \newcommand{\mC}[0]{{\bf C}} \newcommand{\mL}[0]{{\bf L}} \newcommand{\mN}[0]{{\bf N}} \newcommand{\mV}{\mathbf{V}} \newcommand{\mX}[0]{{\bf X}} \newcommand{\nodeidx}{i} \newcommand{\nrnodes}{n} \newcommand{\reals}{\mathbb{R}} \newcommand{\samplecovmtxgeneric}{\widehat{\mC}} \newcommand{\sampleidx}{r} \newcommand{\samplemeanvecgeneric}{\widehat{\bm \mu}} \newcommand{\samplesize}{m} \newcommand{\vu}[0]{{\bf u}} \newcommand{\vv}[0]{{\bf v}} \newcommand{\vw}[0]{{\bf w}} \newcommand{\vx}[0]{{\bf x}} \newcommand{\vy}[0]{{\bf y}} \newcommand{\weights}{\vw} \begin{document} \section{eigenvalue decomposition (EVD)} \subsection*{Author and editors} Alexander Jung\textsuperscript{*}, Department of Computer Science, Aalto University, Espoo, Finland (ORCID \mbox{\href{https://orcid.org/0000-0001-7538-0990}{0000-0001-7538-0990}}) \\ Editors: Konstantina Olioumtsevits (ORCID \mbox{\href{https://orcid.org/0000-0003-2697-8659}{0000-0003-2697-8659}}), Ekkehard Schnoor (ORCID \mbox{\href{https://orcid.org/0000-0001-8252-1499}{0000-0001-8252-1499}}), Aalto University, Espoo, Finland \\ \textsuperscript{*}Corresponding author: \href{mailto:alex.jung@aalto.fi}{alex.jung@aalto.fi} \subsection{Abstract} An eigenvalue decomposition (EVD) of a square matrix breaks the linear map it represents into elementary operations: expanding a vector in the eigenvectors of the matrix, multiplying each expansion coefficient by the corresponding eigenvalue, and summing the scaled terms up again. A matrix that has an EVD is called diagonalizable; symmetric matrices and matrices with distinct eigenvalues are diagonalizable. A dataset with numeric feature vectors can be characterized by the EVD of its sample covariance matrix. The EVD can be used to speed up computations such as the gradient step of gradient descent (GD) methods. For linear regression, each GD iteration then reduces to element-wise operations. The EVD of the Laplacian matrix of an undirected graph is used by spectral clustering. \subsection{Definition} Each day of 2024 at the weather station Krems an der Donau (Austria) is a data point recorded with two features, its lowest and its highest temperature, stacked into a feature vector $\featurevec = \big( \feature_{1}, \feature_{2} \big)^{\top} \in \reals^{2}$. Fig.~\ref{fig_evd_krems_dict} shows $20$ of the $\samplesize = 366$ days $\featurevec^{(1)}, \ldots, \featurevec^{(\samplesize)}$ as a scatterplot together with an ellipse that is computed from their sample mean and sample covariance matrix. The sample mean of the days is \[ \samplemeanvecgeneric = \frac{1}{\samplesize} \sum_{\sampleidx=1}^{\samplesize} \featurevec^{(\sampleidx)} \text{,} \] and their sample covariance matrix is \[ \samplecovmtxgeneric = \frac{1}{\samplesize} \sum_{\sampleidx=1}^{\samplesize} \big( \featurevec^{(\sampleidx)} - \samplemeanvecgeneric \big) \big( \featurevec^{(\sampleidx)} - \samplemeanvecgeneric \big)^{\top} \in \reals^{2 \times 2} \text{.} \] The shape of the ellipse, which outlines the dataset, is determined by an EVD of the sample covariance matrix $\samplecovmtxgeneric$, whose eigenvectors are the axes of the ellipse. \begin{figure}[H] \centering \begin{tikzpicture} \begin{axis}[ width=0.7\linewidth, axis equal image, xlabel={lowest temperature of the day in $^{\circ}$C}, ylabel={highest temperature of the day in $^{\circ}$C}, axis lines=left, clip=false, enlarge x limits=0.12, enlarge y limits=0.08, tick label style={font=\small}, label style={font=\small}, ] \addplot[only marks, mark=*, mark size=1.6pt, color=gray] table[col sep=comma, x=x1, y=x2]{evd_points_plot.csv}; \addplot[black, thick] table[col sep=comma, x=x1, y=x2]{evd_ellipse.csv}; \addplot[->, very thick, black] table[col sep=comma, x=x1, y=x2]{evd_axis1.csv}; \addplot[->, very thick, black, dashed] table[col sep=comma, x=x1, y=x2]{evd_axis2.csv}; \addplot[only marks, mark=x, mark size=3pt, black, very thick] coordinates {(7.176,17.907)}; \node[anchor=east, font=\small] at (axis cs:6.6,17.9) {$\samplemeanvecgeneric$}; \node[anchor=south east, font=\small] at (axis cs:21.214,35.979) {$2\sqrt{\eigval{1}}\,\vv^{(1)}$}; \node[anchor=north west, font=\small] at (axis cs:11.626,14.450) {$2\sqrt{\eigval{2}}\,\vv^{(2)}$}; \end{axis} \end{tikzpicture} \caption{Every $19$th of the $366$ days of 2024 at Krems an der Donau, $20$ days in all, drawn as gray dots. Each day is a data point with two features: the lowest and the highest temperature of that day. The ellipse is computed from the sample mean (cross) and the sample covariance matrix of all $366$ days. The solid arrow and the dashed arrow are the two eigenvectors of that sample covariance matrix, scaled to the half-axes of the ellipse, $2\sqrt{\eigval{j}}\,\vv^{(j)}$. Data generated by \texttt{pythondemos/evd.py} \label{fig_evd_krems_dict}} \end{figure} An EVD for a square matrix $\mA \in \reals^{\featuredim \times \featuredim}$ is a factorization of the form \[ \mA = \mV {\bm \Lambda} \mV^{-1} \text{.} \] The columns of the matrix $\mV = \big( \vv^{(1)}, \,\ldots, \,\vv^{(\featuredim)} \big)$ are eigenvectors of the matrix $\mA$. The diagonal matrix ${\bm \Lambda} = {\rm diag} \big\{ \eigval{1}, \,\ldots, \,\eigval{\featuredim} \big\}$ contains the eigenvalues $\eigval{\featureidx}$ corresponding to the eigenvectors $\vv^{(\featureidx)}$. Multiplying the factorization by $\vv^{(\featureidx)}$ gives $\mA \vv^{(\featureidx)} = \eigval{\featureidx} \vv^{(\featureidx)}$: each eigenvector is a direction that $\mA$ only scales, by the factor $\eigval{\featureidx}$; a single such pair satisfies $\mA \vx = \eigvalgen \vx$, and the EVD collects $\featuredim$ of them, indexed by $\featureidx$. \par The EVD breaks the linear map $\vu \mapsto \mA \vu$ into three elementary operations. A vector $\vu$ is expanded in the eigenvectors, $\vu = \sum_{\featureidx=1}^{\featuredim} \expcoeff_{\featureidx} \vv^{(\featureidx)}$ with the expansion coefficients $\boldsymbol{\expcoeff} = \mV^{-1} \vu$; each coefficient is multiplied by its eigenvalue; and the scaled terms are summed up again, $\mA \vu = \sum_{\featureidx=1}^{\featuredim} \eigval{\featureidx} \expcoeff_{\featureidx} \vv^{(\featureidx)}$. \par Unlike the singular value decomposition (SVD), which exists for every matrix, square or not (Horn and Johnson, 2013, Thm.~2.6.3), the EVD is defined for square matrices only, and it need not exist. Moreover, the same matrix might allow for different EVDs: any nonzero linear combination of eigenvectors with the same eigenvalue is again an eigenvector with this eigenvalue. The geometric multiplicity of an eigenvalue is the maximum number of linearly independent eigenvectors with this eigenvalue (Horn and Johnson, 2013, Sect.~1.4). \par Matrices that allow for an EVD are called diagonalizable. One example of a diagonalizable matrix is \[ \mA = \begin{pmatrix} 1.3 & 0.8 \\ 0.4 & 0.9 \end{pmatrix} \text{.} \] Fig.~\ref{fig_evd_directions} illustrates its EVD. \begin{figure}[H] \begin{center} \begin{tikzpicture}[font=\small, scale=1.4] \draw[black!25] (-1.3,0) -- (3.5,0); \draw[black!25] (0,-0.8) -- (0,2.2); \draw[dotted, black!70] (-0.9,-0.45) -- (3.2,1.6); \draw[dotted, black!70] (0.8,-0.8) -- (-1.2,1.2); \draw[dotted, black!70] (-0.4,-0.8) -- (1.0,2.0); \draw[->, line width=1.1pt] (0,0) -- (1.4,0.7); \node[font=\scriptsize, anchor=north west] at (1.3,0.62) {$\vv^{(1)}$}; \draw[->, dashed, black, thick] (0.04,-0.08) -- (2.42,1.11); \node[font=\scriptsize, anchor=west] at (2.46,1.14) {$\mA \vv^{(1)}$}; \draw[->, line width=1.1pt] (0,0) -- (-0.7,0.7); \node[font=\scriptsize, anchor=south east] at (-0.7,0.7) {$\vv^{(2)}$}; \draw[->, dashed, black, thick] (-0.06,-0.06) -- (-0.41,0.29); \node[font=\scriptsize, anchor=east] at (-0.45,0.32) {$\mA \vv^{(2)}$}; \draw[->, line width=1.1pt] (0,0) -- (0.7,1.4); \node[font=\scriptsize, anchor=south] at (0.7,1.45) {$\vu$}; \draw[->, dashed, black, thick] (0,0) -- (2.03,1.54); \node[font=\scriptsize, anchor=west] at (2.06,1.57) {$\mA \vu$}; \fill (0,0) circle (1.6pt); \end{tikzpicture} \end{center} \caption{The matrix $\mA \in \reals^{2 \times 2}$ from the display above has the eigenvalues $\eigval{1} = 1.7$ and $\eigval{2} = 0.5$, with the eigenvectors $\vv^{(1)}$ along $(2,1)^{\top}$ and $\vv^{(2)}$ along $(-1,1)^{\top}$ (solid arrows). The dashed arrows are the images under $\mA$, and each dotted line carries one solid arrow. The eigenvector $\vv^{(1)}$ stays on its line, stretched to the longer dashed arrow $\mA \vv^{(1)} = \eigval{1} \vv^{(1)}$; the eigenvector $\vv^{(2)}$ stays on its line, shrunk to the shorter dashed arrow $\mA \vv^{(2)} = \eigval{2} \vv^{(2)}$. The vector $\vu = \vv^{(1)} + \vv^{(2)}$ leaves its dotted line: its image $\mA \vu = \eigval{1} \vv^{(1)} + \eigval{2} \vv^{(2)}$ points elsewhere, because its two expansion coefficients are scaled by different factors \label{fig_evd_directions}} \end{figure} Two sufficient conditions for a real-valued square matrix to be diagonalizable are that it is a symmetric matrix or that its $\featuredim$ eigenvalues are distinct (Golub and Van Loan, 2013; Horn and Johnson, 2013, Thm.~1.3.9, Thm.~4.1.5). For a real-valued symmetric matrix, the EVD has additional structure: the eigenvectors can be chosen to form an orthonormal basis, i.e., the matrix $\mV$ in the factorization can be chosen to be orthogonal (Horn and Johnson, 2013, Thm.~4.1.5). The condition that is both necessary and sufficient is that every root of the minimal polynomial of the matrix is simple (Horn and Johnson, 2013, Cor.~3.3.10). For a complex-valued matrix, the first condition is that it is Hermitian; a complex symmetric matrix need not be diagonalizable (Horn and Johnson, 2013, Thm.~4.1.5, Problem~4.4.P10). \par The matrix $\mA$ of Fig.~\ref{fig_evd_directions} is not symmetric, since its off-diagonal entries $0.8$ and $0.4$ differ, but its two eigenvalues $1.7$ and $0.5$ are distinct, so it has an EVD. When neither condition holds, an EVD may not exist: the matrix \[ \mN = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} \] is not symmetric and has the eigenvalue $0$ twice, since the eigenvalues of a triangular matrix are its diagonal entries (Horn and Johnson, 2013, Sect.~1.2, exercise on upper triangular matrices after Def.~1.2.9). The eigenvectors of $\mN$ are all located on the line $\big\{ (a, 0)^{\top} : a \in \reals \big\}$, so there is no invertible matrix $\mV$ whose columns are eigenvectors of $\mN$. \par The ellipse in Fig.~\ref{fig_evd_krems_dict} is the set of feature vectors $\featurevec$ for which the quadratic form $(\featurevec - \samplemeanvecgeneric)^{\top} \samplecovmtxgeneric^{-1} (\featurevec - \samplemeanvecgeneric)$ equals $4$. This set can be characterized more conveniently using an EVD of the sample covariance matrix $\samplecovmtxgeneric$. The matrix $\samplecovmtxgeneric$ is symmetric, so it has an EVD $\samplecovmtxgeneric = \mV {\bm \Lambda} \mV^{\top}$ with an orthogonal matrix $\mV$ that contains the eigenvectors in its columns. Transforming the feature vector $\featurevec$ of a day according to $\widetilde{\featurevec} \defeq \mV^{\top} (\featurevec - \samplemeanvecgeneric)$ turns the quadratic form into \[ (\featurevec - \samplemeanvecgeneric)^{\top} \samplecovmtxgeneric^{-1} (\featurevec - \samplemeanvecgeneric) = \widetilde{\featurevec}^{\top} {\bm \Lambda}^{-1} \widetilde{\featurevec} = \frac{\widetilde{x}_{1}^{2}}{\eigval{1}} + \frac{\widetilde{x}_{2}^{2}}{\eigval{2}} \text{,} \] since $\samplecovmtxgeneric^{-1} = \mV {\bm \Lambda}^{-1} \mV^{\top}$. The ellipse is therefore the set where $\widetilde{x}_{1}^{2}/\eigval{1} + \widetilde{x}_{2}^{2}/\eigval{2} = 4$, with half-axes $2\sqrt{\eigval{1}}$ and $2\sqrt{\eigval{2}}$ along the coordinate axes of $\widetilde{\featurevec}$, that is, along the eigenvectors. The transformed days have the sample covariance matrix $\mV^{\top} \samplecovmtxgeneric \mV = {\bm \Lambda}$: the two new coordinates have sample covariance zero, and the eigenvalues are their sample variances. Replacing each day by its first coordinate $\widetilde{x}_{1}$ alone keeps the direction of largest variance, which is the idea of principal component analysis (PCA) (Bishop, 2006, Sect.~12.1.1). \par Besides describing the shape of a dataset, the EVD can be used to speed up the implementation of a machine learning (ML) method. Consider gradient descent (GD) for linear regression, with the update $\weights^{(\iteridx+1)} = \weights^{(\iteridx)} - (2\lrate/\samplesize) \featuremtx^{\top} \big( \featuremtx \weights^{(\iteridx)} - \labelvec \big)$ for $\iteridx = 0,1,\ldots$, with the feature matrix $\featuremtx$ and label vector $\labelvec$ of the training set (see linear regression). The matrix $\featuremtx^{\top}\featuremtx$ is symmetric, so it has an EVD $\featuremtx^{\top}\featuremtx = \mV {\bm \Lambda} \mV^{\top}$ with an orthogonal matrix $\mV$. In the transformed coordinates $\widetilde{\weights}^{(\iteridx)} \defeq \mV^{\top} \weights^{(\iteridx)}$, the update decouples into \[ \widetilde{w}_{\featureidx}^{(\iteridx+1)} = \big( 1 - (2\lrate/\samplesize) \eigval{\featureidx} \big) \widetilde{w}_{\featureidx}^{(\iteridx)} + (2\lrate/\samplesize) \big( \mV^{\top} \featuremtx^{\top} \labelvec \big)_{\featureidx} \text{.} \] After the one-time computation of the EVD, each iteration is an element-wise multiplication and addition of vectors of length $\featuredim$ (\texttt{pythondemos/evd.py}). \par Another application of the EVD in ML is the clustering of graph-structured data (von Luxburg, 2007). Consider data points represented as the nodes $\nodeidx = 1, \,\ldots, \,\nrnodes$ of an undirected graph $\graph$, e.g., the users of a social network with edges given by friendships. The Laplacian matrix $\LapMat{\graph}$ of the graph $\graph$ is symmetric and positive semi-definite (psd) (von Luxburg, 2007, Prop.~1). It has an EVD $\LapMat{\graph} = \mV {\bm \Lambda} \mV^{\top}$ with an orthogonal matrix $\mV$ and nonnegative eigenvalues. \par If the graph $\graph$ is connected, the EVD has additional structure: the eigenvalue $0$ has multiplicity one, with the all-ones vector as its eigenvector (von Luxburg, 2007, Prop.~2). Moreover, there is then a distinguished eigenvector, called the Fiedler vector: an eigenvector of the smallest nonzero eigenvalue, the algebraic connectivity of $\graph$ (Fiedler, 1973). The Fiedler vector can be used for clustering the nodes of the graph, which is the idea of spectral clustering (von Luxburg, 2007). Fig.~\ref{fig_evd_fiedler_dict} shows the Fiedler vector of a connected graph with six nodes: two clusters of three nodes and a single edge joining the two clusters. \begin{figure}[H] \begin{center} \begin{tikzpicture}[font=\small, gnode/.style={circle, draw, inner sep=1pt, minimum size=13pt}] \node[gnode] (n1) at (0,1.5) {$1$}; \node[gnode] (n2) at (0,0.3) {$2$}; \node[gnode] (n3) at (1.1,0.9) {$3$}; \node[gnode] (n4) at (2.7,0.9) {$4$}; \node[gnode] (n5) at (3.8,1.5) {$5$}; \node[gnode] (n6) at (3.8,0.3) {$6$}; \draw (n1) -- (n2) -- (n3) -- (n1); \draw (n4) -- (n5) -- (n6) -- (n4); \draw (n3) -- (n4); \matrix (V) [matrix of math nodes, left delimiter=(, right delimiter=), row sep=1.5pt, inner sep=1.5pt, font=\small] at (6.5,0.9) { -0.46 \\ -0.46 \\ -0.26 \\ 0.26 \\ 0.46 \\ 0.46 \\ }; \node[font=\small] at ([yshift=11pt]V.north) {$\vv^{(2)}$}; \node[font=\small] at (1.9,-0.55) {(a)}; \node[font=\small] at (6.5,-0.9) {(b)}; \foreach \i/\o in {1/25, 2/50, 3/14, 4/8, 5/-30, 6/-12} { \draw[gray, thin, densely dotted] (n\i) to[out=\o, in=180] ([xshift=-7pt]V-\i-1.west); } \end{tikzpicture} \end{center} \caption{(a) A connected undirected graph with six nodes: the cluster of nodes $1$, $2$, $3$ and the cluster of nodes $4$, $5$, $6$, each node connected to the other two of its cluster. The two clusters are joined by the single edge between nodes $3$ and $4$. (b) The Fiedler vector $\vv^{(2)}$ of the Laplacian matrix of the graph in (a), as a column vector; a thin dotted line connects each node $\nodeidx$ to its entry $v^{(2)}_{\nodeidx}$. The signs of the entries recover the two clusters. Entries computed by \texttt{pythondemos/evd.py} \label{fig_evd_fiedler_dict}} \end{figure} \subsection{Cross References} matrix, eigenvector, eigenvalue, diagonalizable, invertible, orthogonal, Laplacian matrix, algebraic connectivity, Fiedler vector, spectral clustering, GD, linear regression, sample covariance matrix, PCA, spectral decomposition, SVD, minimal polynomial \subsection{References} \begin{enumerate} \item Bishop (2006). Pattern Recognition and Machine Learning. Springer Science+Business Media, New York, NY, USA. \item Fiedler (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2), pp.~298--305. \item Golub and Van Loan (2013). Matrix Computations. 4th ed., The Johns Hopkins Univ. Press, Baltimore, MD, USA. \item Horn and Johnson (2013). Matrix Analysis. 2nd ed., Cambridge Univ. Press, New York, NY, USA. \item von Luxburg (2007). A tutorial on spectral clustering. Statist. Comput., 17(4), pp.~395--416. \end{enumerate} \end{document}