README.md

Singular Value Decomposition

This package contains 2 C++ classes: svd and read_matrix and test file with the main function.

Class svd

This class provides factorization of any square matrix M by SVD algorithm for
the square matrices: M = USV^t, where S is the diagonal matrix, and U, V are two orthonormal matrices.

This class contains 5 public functions

void Factorization(std::vector<std::vector> matrix, std::vector<std::vector>& s, std::vector<std::vector>& u, std::vector<std::vector>& v);

void VerifyFactorisition(std::vector<std::vector>& u, std::vector<std::vector>& s, std::vector<std::vector>& v);

int GetRank(std::vector<std::vector>& s);

void GetPseudoinverse(std::vector<std::vector>& s, std::vector<std::vector>& u, std::vector<std::vector>& v, std::vector<std::vector>& pseudoinv);

void VerifyPseudoinverse(std::vector<std::vector>& A, std::vector<std::vector>& A_pesudoinv);

and a number of private functions, see svd.h.

Tracking

The constructor svd contains the boolean variable track.
The default value of track is true that provides the extended log on the console.
Set track = false to reduce the log.

Class read_matrix

This class contains 2 public functions:

std::string get_file_name();

void get_matrix_by_file_name( std::string filename, std::vector<std::vector>& matrix);

and several private functions, see read_matrix.h

Briefly about SVD algorithm

1. Eigenvalues of the symmetric matrix (Power Iteration algorithm)

Let A be the input square matrix. First we find eigenvalues of the symmetric matrix
B = A^t * A. The first loop in the function GetEigenvalsEigenvecs finds
the maximal eigenvalue of B (in magnitude). For explanations of this algorithm, see

1. qr-algorithm,
2. Power itaration

The function GetEigenvalsEigenvecs is recursive, so the remaining eigenvalues will be calculated by the following recursive calls. The function ReduceMatrix transforms the matrix B to the matrix B of the m_size - 1, where m_size is the size if current matrix B.

2. Gauss-Jordan Elimination algorithm

The matrix M = B - \lambda*I is named the traget matrix. For each eigenvalue \lambda, the target matrix B - is transformed into an upper triangular matrix, so called row ecehlon form, seee

3. Gaussian elimination

see function GaussJordanElimination.

3. Eigenalues of target matrix

Further, for each eigenvalue \lambda, the eigenvector vector V(\lambda) of the target matrix M will be found. This is performed by Gauss-Jordan Elimination algorithm,