randomness
Last edited: November 11, 2025randomness is a resource which can be used.
Our unit of computation is a randomized turing machine
some questions of randomness
save time/space by using randomness: we used to believe that \(P \subset \text{Randomized } P\), \(L \subset \text{Randomized } L\), etc. But we now think \(P = \text{Randomized } P\) (intuition: if solving SAT requires circuits of exponential size, then \(P\) is equal to Randomized \(P\)).
efficient derandomized: can we reduce usage of randomization—i.e. completely derandomize it while not loosing a lot of efficiency?
singular value decomposition
Last edited: November 11, 2025Singular value decomposition is a factorization of a matrix, which is a generalization of the eigendecomposition of normal matricies (i.e. where \(A = V^{-1} D V\) when \(A\) is diagonalizable, i.e. by the spectral theorem possible when matricies are normal).
Definitions
Singular value decomposition Every \(m \times n\) matrix has a factorization of the form:
\begin{equation} M = U D^{\frac{1}{2}} V^{*} \end{equation}
where, \(U\) is an unitary matrix, \(D^{\frac{1}{2}}\) a diagonalish (i.e. rectangular diagonal) matrix with non-negative numbers on its diagonal called singular values, which are the positive square roots of eigenvalues of \(M^{* }M\) — meaning the diagonal of \(D^{\frac{1}{2}}\) is non-negative (\(\geq 0\)). Finally, \(V\) is formed columns of orthonormal bases of eigenvectors of \(M^{*}M\).