Trace The trace of a matrix \(A \in \mathbb{R}^{n \times n}\) is the sum of its diagonal entries: \begin{equation} \notag \text{tr}(A) = \sum_{i=1}^n a_{ii} = \sum_{i=1}^n e_i^T A e_i, \end{equation} where \(e_i\) is the $i$-th column of the identity matrix. Many scientific computing and machine learning applications require estimating the trace of a square linear … Continue reading Randomized Algorithm for Trace Estimation
Tag: algorithm
One-sided Jacobi Algorithm
Outline of the Algorithm The Jacobi algorithm for computing the singular value decomposition (SVD) of a general matrix \(A \in \mathbb{R}^{m \times n}\) was proposed by Hestenes. The algorithm proceeds as follows: \begin{equation}\notag A^{(0)} = A, \quad A^{(k+1)} = A^{(k)} J^{(k)}, \quad A^{(\infty)} = U \varSigma, \end{equation} for \(k = 1, 2, \dots\), where \(J^{(k)}\) … Continue reading One-sided Jacobi Algorithm
Cholesky QR Algorithm
Let \(X \in \mathbb{R}^{ m \times n }\) with \(m \ge n\) of full column rank. The Cholesky QR (CholQR) algorithm computes a QR factorization of \(X\) by forming the Gram matrix \(A = X^{T} X\), computing its Cholesky factorization \(A = R^{T} R\), and finally finding the \(Q\) factor by \(Q = XR^{-1}\). Here, … Continue reading Cholesky QR Algorithm
The Jacobi algorithm for eigenvalues
Given a symmetric \(A \in \mathbb{R}^{n\times n}\), the Jacobi algorithm produces a sequence of orthogonally similar matrices \(A_{k+1} = J_{k}^{T} A_{k} J_{k}\) for \(k = 1,2,\dots\), \(A_{1} = A\), and \(J_{k}\) are the carefully constructed Jacobi rotations. In fact, the Jacobi rotation is the same as the Givens rotation, but we give the credit to … Continue reading The Jacobi algorithm for eigenvalues