SVD (Singular Value Decomposition)

Overview

SVD is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \(m\times n\) matrix. It is related to the polar decomposition.

the singular value decomposition of a :math: mtimes n complex matrix \(M\) is a factorization of the form \(U\)\(\Sigma\)\(V^*\), where \(U\) is a \(m\times m\) complex unitary matrix, \(\Sigma\) is a \(m\times n\) rectangular diagonal matrix with non-negative real numbers on the diagonal, and \(V\) is a \(n\times n\) complex unitary matrix. If \(M\) is real, \(U\) and \(V\) can also be guaranteed to be real orthogonal matrix.

\[M = U{\Sigma}V^*\]

The diagonal entries \(\Sigma_{ii}\) of \(\Sigma\) are known as the singular values of \(M\). The number of non-zero singular values is equal to the rank of \(M\). the Columns of \(U\) and \(V\) are called the left-singular vectors and right-singular vectors of \(M\) respectively.

Implementation

The singular value decomposition of input matrix \(A\) is computed and matrix \(U\), \(S\), \(V\) is generated.

\[A = USV^*\]

In this design, square matrix is supported only. The iterative two-sided Jacobi method is used in this API.

DataType Supported

  • float
  • x_complex<float>
  • std::complex<float>

Interfaces

  • Template parameters:

    • RowsA Row dimension
    • ColsA Column dimension
    • InputType Input data type
    • OutputType Output data type
    • SVDTraits SVDTraits class

  • Arguments:

    • matrixAStrm Stream of input matrix
    • matrixSStrm Stream of singular values input matrix
    • matrixUStrm Stream of left singular vectors input matrix
    • matrixVStrm Stream of right singular vectors input matrix

Note

  • The function will throw an assertion and fail to compile or synthesize, if RowsA != ColsA.
  • For floating point types, subnormal input values are not supported. If used, the synthesized hardware will flush these to zero, and behavior will differ versus software simulation.

Implementation Controls

Specifications

There is a configuration class derived from the base configuration class xf::solver::svdTraits by redefining the appropriate class member.

struct my_svd_config : xf::solver::svdTraits<ROWS, COLS, MATRIX_IN_T, MATRIX_OUT_T> {
    static const int ARCH = SEL_ARCH;
};

The base configuration class is:

template <int RowsA, int ColsA, typename InputType, typename OutputType>
struct svdTraits {
    typedef OutputType SIntType;
    typedef OutputType UIntType;
    typedef OutputType VIntType;
    typedef OutputType CSIntType;
    static const int NUM_SWEEPS = 10;
    static const int MIN_DIM = (RowsA < ColsA ? RowsA : ColsA);
    static const int ARCH = 1;
    static const int OFF_DIAG_II = 8;
    static const int DIAG_II = 8;
};

Note

  • NUM_SWEEPS: The SVD function uses the iterative two-sided Jacobi method. Literature typically suggests 6 to 10 iterations to successfully converge.
  • ARCH: Select implementation. 0 = Basic loop engine. 1 = Pairs based engine.
  • OFF_DIAG_II: Specify the pipelining target for the off diagonal loop.
  • DIAG_II: Specify the pipelining target for the diagonal loop.

The configuration class is supplied to the xf::solver::svd function as a template paramter as follows.

template <int RowsA,
          int ColsA,
          typename InputType,
          typename OutputType,
          typename SVDTraits = svdTraits<RowsA, ColsA, InputType, OutputType> >
svd(hls::stream<InputType >& matrixAStrm,
    hls::stream<OutputType>& matrixSStrm,
    hls::stream<OutputType>& matrixUStrm,
    hls::stream<OutputType>& matrixVStrm)

Key Factors

The following table summarizes that how the key factors which from the configuration class influence resource utilization, function throughput (initiation interval), and function latency. The values of Low, Medium, and High are relative to the other key factors.

Table 2 SVD Key Factor Summary
Key Factor Value Resources Throughput Latency
Iterations (NUM_SWEEP) <10 N/A High Low
Off-diagonal loop pipelining (OFF_DIAG_II) 4 High High Low
>4 Low Low High
Diagonal loop pipeling (DIAG_II) 1 High High Low
>1 Low Low High

Note

  • Iterations: The SVD function uses the iterative two-sided Jacobi method. The default number of iterations is 10.
  • Off-diagonal loop pipelining: the minimum achievable initiation interval (II) is 4, which satisfies the S, U, and V array requirement of four writes every iteration of the off-diagonal loop.
  • Diagonal loop pipelining: value >1, enables Vivado HLS to resource share