Singular 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\).

Key Sequence

Notation

New Concepts

• Bellman-Ford Algorithm
• dynamic programming
• Floyd-Warshall Algorithm

Important Results / Claims

Questions

Interesting Factoids

Key Sequence

Notation

New Concepts

• longest common subsequence
• knapsack
• independent set

Important Results / Claims

Questions

Interesting Factoids

Key Sequence

Notation

New Concepts

• Principle Component Analysis
• SVD

Important Results / Claims

Questions

Interesting Factoids

Bellman Equation, etc., are really designed for state spaces that are discrete. However, we’d really like to be able to support continuous state spaces! Suppose we have: \(S \in \mathbb{R}^{n}\), what can we do?

Discretization

We can just pretend that our system is a discrete-state MDP by chopping the state space up into small blocks. If you do it, you can cast your \(V\) back to a step function. Recall that this could start exploding: for \(S \in \mathbb{R}^{n}\) and we want to divide each axes into \(k\) values, we will get \(k^{n}\) values!