Principle:Haifengl Smile Decomposition Result Extraction

Overview

Decomposition Result Extraction is the final stage of the Matrix_Decomposition_Pipeline, where the factored components produced by decompositions are accessed, manipulated, and used for downstream analysis. This includes extracting singular values and vectors from SVD, eigenvalues and eigenvectors from EVD, sorting eigenvalues, constructing diagonal matrices, and computing derived quantities such as matrix rank, condition number, null space, and range.

For large sparse matrices where full decomposition is infeasible, Smile provides ARPACK (Implicitly Restarted Arnoldi/Lanczos Method) for computing a small number of extremal eigenpairs or singular triples efficiently.

Theoretical Basis

SVD Result Interpretation

Given the SVD $A=U\mathrm{\Sigma }{V}^T$:

Component	Symbol	Interpretation
Singular values	${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_k$	Importance of each component; square roots of eigenvalues of $A^{T}A$
Left singular vectors	$U=[u_1,u_2,\dots ,u_k]$	Orthonormal basis for the column space of $A$
Right singular vectors	$V=[v_1,v_2,\dots ,v_k]$	Orthonormal basis for the row space of $A$
Diagonal matrix	$\mathrm{\Sigma }=\text{diag}({\sigma }_1,\dots ,{\sigma }_k)$	The "stretching factors" of the transformation

Derived Quantities from SVD

Matrix Rank: The number of singular values above a threshold:

$r=\mathrm{\#}\{i:{\sigma }_i>{ϵ}_{\text{rcond}}\}$

where the threshold is ${ϵ}_{\text{rcond}}=\frac{1}{2}\sqrt{m+n+1}\cdot {\sigma }_1\cdot {ϵ}_{\text{mach}}$.

Condition Number: The ratio of the largest to smallest singular value:

$\kappa (A)=\frac{{\sigma }_1}{{\sigma }_k}$

A condition number close to 1 indicates a well-conditioned matrix. When $\kappa (A)$ is large or infinite, the matrix is ill-conditioned or singular.

Nullity: $\text{nullity}(A)=\min (m,n)-r$

Range Space: The first $r$ columns of $U$ form an orthonormal basis for $\text{range}(A)$.

Null Space: The last $\text{nullity}$ rows of $V^T$ (equivalently, last columns of $V$) form an orthonormal basis for $\text{null}(A)$.

The Eckart-Young Theorem

The truncated SVD provides the best low-rank matrix approximation. Keeping only the top $r$ singular values:

$A_r=\sum _{i=1}^r{\sigma }_i{u}_i{v}_i^T$

minimizes $\Vert A-A_r{\Vert }_F$ and $\Vert A-A_r{\Vert }_2$ over all rank-$r$ matrices. This is the theoretical basis for PCA, latent semantic indexing, and data compression.

EVD Result Interpretation

Given the eigenvalue decomposition of a square matrix $A$:

Symmetric Case

$A=V\mathrm{\Lambda }{V}^T$

where $\mathrm{\Lambda }=\text{diag}({\lambda }_1,\dots ,{\lambda }_n)$ with all real eigenvalues and $V$ is orthogonal.

Spectral properties:

• All eigenvalues are real
• Eigenvectors corresponding to distinct eigenvalues are orthogonal
• $\text{tr}(A)=\sum _i{\lambda }_i$
• $\det (A)=\prod _i{\lambda }_i$
• Positive definite iff all ${\lambda }_i>0$

General (Non-Symmetric) Case

Eigenvalues may be complex: ${\lambda }_i=w_{r,i}+j\cdot w_{i,i}$

The diagonal matrix uses a block structure:

• Real eigenvalue ${\lambda }_i$: a 1x1 block on the diagonal
• Complex conjugate pair ${\lambda }_i=a+bi$: a 2x2 block $\left[\begin{array}{cc}a& b\\ -b& a\end{array}\right]$

Sorting Eigenvalues

Eigenvalues are sorted by descending magnitude:

$|{\lambda }_1{|}^2\ge |{\lambda }_2{|}^2\ge \cdots \ge |{\lambda }_n{|}^2$

where $|{\lambda }_i{|}^2=w_{r,i}^2+w_{i,i}^2$. The corresponding eigenvectors are reordered accordingly.

ARPACK: Large Sparse Eigenproblems

For matrices too large for full EVD ($O(n^3)$), ARPACK computes a small number $k\ll n$ of eigenvalues using the Implicitly Restarted Arnoldi Method (IRAM):

For symmetric matrices (Lanczos variant):

• Builds a Krylov subspace ${{𝒦}}_k(A,v_0)=\text{span}\{v_0,A{v}_0,A^2{v}_0,\dots ,A^{k-1}{v}_0\}$
• Extracts eigenvalue approximations (Ritz values) from the tridiagonal projection
• Applies implicit QR shifts to restart with a refined subspace

Which eigenvalues to compute (SymmOption enum):

Option	Description	Use Case
LA	Largest algebraic	PCA (largest positive eigenvalues)
SA	Smallest algebraic	Graph Laplacian (near-zero eigenvalues)
LM	Largest magnitude	Dominant modes, spectral radius
SM	Smallest magnitude	Near-singular directions
BE	Both ends	Spectral gap analysis

Computational complexity: $O(n\cdot k\cdot \text{ncv})$ where ncv is the number of Arnoldi vectors (typically $3k$), compared to $O(n^3)$ for full EVD.

Key property: ARPACK only requires the action of $A$ on a vector (matrix-vector product), not the matrix entries themselves. This enables use with sparse matrices and implicit matrix representations.

ARPACK SVD

ARPACK can also compute the top-$k$ singular triples by solving the equivalent eigenproblem on $A^{T}A$ (via the AtA implicit matrix wrapper) and recovering the singular vectors.

Relationship to the Pipeline

Construction --> Arithmetic --> Decomposition --> Solving --> Result Extraction
                                                                    ^
                                                                    |
                                                             (this principle)

Result extraction is the final stage that produces the quantities used by ML algorithms: eigenvalues for PCA, singular values for matrix rank, eigenvectors for spectral clustering, and so on.

Related

• Implementation:Haifengl_Smile_SVD_EVD_Results
• Principle:Haifengl_Smile_Matrix_Decomposition

Knowledge Sources

• Smile
• ARPACK Users' Guide
• LAPACK

Domains

Linear_Algebra, Numerical_Computing, Dimensionality_Reduction, Spectral_Analysis