|
About Contribute Source |
| main/svd/ |
The singular value decomposition (SVD) factorizes any matrix into a product of two matrices with orthonormal columns and a diagonal matrix of non-negative numbers, the singular values. It is one of the most important tools in tensor network methods: it reveals the rank of a matrix and its most important directions, it gives the best possible low-rank approximation of a matrix, and, applied to a tensor whose indices have been split into two groups, it factors the tensor into two pieces joined by a new bond index whose dimension can be controlled. Algorithms such as TT-SVD, DMRG, and TRG all rely on it.
Any $m \times n$ matrix $M$, real or complex, can be written as
\begin{equation} M = U S V^\dagger , \qquad M_{ij} = \sum_{\alpha=1}^{k} U_{i\alpha}\, \sigma_\alpha\, \overline{V_{j\alpha}} \end{equation}
where $k = \min(m,n)$ and
The columns of $U$ and $V$ are called the left and right singular vectors. Schematically, for a matrix with more rows than columns:
Each dot in $M$ stands for an entry. The lines in $U$ and $V^\dagger$ stand for their orthonormal columns and rows, and $S$ is nonzero only on its diagonal, with entries that decrease along the diagonal.
This is the thin (or economy) SVD, which is the version used in tensor network codes. The full SVD instead extends $U$ and $V$ to square unitary matrices of size $m \times m$ and $n \times n$, and pads $S$ with zeros. The extra columns only multiply zeros, so they add cost without adding any information.
Some basic properties of the SVD:
In tensor diagram notation, the SVD of a matrix is drawn as
where the singular values form a diagonal matrix $S_{\alpha\alpha'} = \sigma_\alpha \delta_{\alpha\alpha'}$. The orthonormality of the columns of $U$ and $V$ means that contracting either one with its conjugate over the original index gives the identity:
Matrices with this property are called isometries. Note that the products in the other order, $U U^\dagger$ and $V V^\dagger$, are generally not the identity. They are projectors onto the spaces spanned by the columns of $U$ and $V$.
To compute the SVD of a tensor, first choose which of its indices will go on each side of the factorization. Grouping (reshaping) the first set of indices into a single row index and the rest into a single column index turns the tensor into a matrix, which can be decomposed as above. Reshaping $U$ and $V^\dagger$ back gives tensors that carry the original indices:
The new index between $U$ and $V^\dagger$ has dimension at most the smaller of the product of the dimensions of the indices on each side, here $\min(d_1 d_2, d_3 d_4)$ where $d_j$ is the dimension of index $i_j$. Truncating it, as described below, compresses the tensor. Repeating this step is how the TT-SVD algorithm turns a tensor into a matrix product state / tensor train, and how DMRG splits an optimized two-site tensor back into MPS form.
In quantum physics, when $T$ is the wavefunction of a system split into two parts, the SVD is known as the Schmidt decomposition. The singular values are the Schmidt coefficients, and for a normalized state the entanglement entropy between the two parts is $S_\mathrm{E} = -\sum_\alpha \sigma_\alpha^2 \ln \sigma_\alpha^2$.
Keeping only the $r$ largest singular values, together with the matching columns of $U$ and $V$, gives the truncated SVD
\begin{equation} M_r = U_r S_r V_r^\dagger = \sum_{\alpha=1}^{r} \sigma_\alpha\, u_\alpha v_\alpha^\dagger \end{equation}
where $u_\alpha$ and $v_\alpha$ are the columns of $U$ and $V$:
The matrix $M_r$ has rank (at most) $r$, and it is the best such approximation to $M$. This is the Eckart–Young–Mirsky theorem:[1][2] for any matrix $X$ of rank at most $r$,
\begin{align} \|M - M_r\|_F &= \Big( \sum_{\alpha > r} \sigma_\alpha^2 \Big)^{1/2} \leq \|M - X\|_F \\ \|M - M_r\|_2 &= \sigma_{r+1} \leq \|M - X\|_2 \end{align}
More generally, $M_r$ is a best rank-$r$ approximation in every unitarily invariant norm, meaning any norm with $\|W M Z\| = \|M\|$ for all unitary $W$ and $Z$.[2] Besides the Frobenius and spectral norms, this includes the nuclear norm $\sum_\alpha \sigma_\alpha$ and the other Schatten norms. In the Frobenius norm, the best approximation is unique when $\sigma_r > \sigma_{r+1}$. If instead $\sigma_r = \sigma_{r+1} > 0$, there are many equally good choices.
This optimality is why the SVD is so central to tensor networks. The Frobenius norm of a tensor does not depend on how its indices are grouped, so a truncated SVD gives the best approximation of the tensor being factorized for a given dimension of the new bond index. When the rest of a network consists of isometries, as in an MPS in canonical form with its orthogonality center at the tensor being factorized, the error of the whole network equals the error of this local truncation. The truncation is then optimal for the whole network too, and its error is given exactly by the discarded singular values. Without such orthogonality, truncating one bond is still optimal for that tensor but not, in general, for the full network.
The truncated SVD is not optimal, in general, for norms that are not unitarily invariant, such as the largest absolute error of any single entry, or a weighted error $\sum_{ij} W_{ij} |M_{ij} - X_{ij}|^2$. Finding the best low-rank approximation under such a weighted error (which includes the case of missing entries) is NP-hard in general.[3]
In practice the number $r$ of singular values to keep is chosen by one or more of the following rules, often combined, for example “keep at most $r_{\max}$, but fewer if the error target is already met”:
Some further practical points:
For a dense $m \times n$ matrix with $m \geq n$, the thin SVD costs $O(m n^2)$ operations. Standard algorithms first reduce the matrix to bidiagonal form using Householder reflections,[4] and then find the SVD of the bidiagonal matrix iteratively, by QR iteration or by a divide-and-conquer method.[5] The constant in front is noticeably larger than for a QR decomposition or a matrix multiplication of the same size. Computing only the singular values, without the singular vectors, is cheaper. The full SVD is more expensive, since $U$ then has size $m \times m$ instead of $m \times k$, which adds to both the work and the memory needed.
In tensor network algorithms the SVD is often one of the most expensive steps. For example, splitting a two-site MPS tensor with bond dimension $\chi$ and site dimension $d$ requires the SVD of a $(\chi d) \times (d \chi)$ matrix, at a cost of $O(d^3 \chi^3)$.
When only the leading $r \ll \min(m,n)$ singular values are needed, there are cheaper options:
Other decompositions can sometimes take the place of an SVD:
svd in the LinearAlgebra standard library (divide and conquer by default),
and svdsolve in KrylovKit.jl for a few leading singular values.
ITensors.jl provides svd(T, inds; maxdim, cutoff) for tensors, with truncation.numpy.linalg.svd and scipy.linalg.svd for dense matrices,
and scipy.sparse.linalg.svds for a few leading singular values.gesvd (QR iteration) and gesdd (divide and conquer),
which most of the libraries above call internally.