Math - Null Space and Singular Value Decomposition (SVD)

Introduction

The three most basic & important matrix factorizations in pure & applied linear algebra are:

• QR Decomposition (Gram-Schmidt Orthogonalization)
• LU Decomposition (Gaussian Elimination)
• SVD Decomposition (Singular Value Decomposition)

At various points of my career in robotics, computer vision, and machine learning, Singular Value Decomposition (SVD) has been a cornerstone and serves as a powerful data reduction tool that transforms high-dimensional data into a more manageable lower-dimensional form.

Singular Value Decomposition Intuition

Let A be an m x n matrix. The goal is to decompose A into $A = U\Sigma V^T$, where U is mxm, and m > n

• $U$ is m x m orthonormal matrix, aka left singular vectors.
• $\Sigma$ is m x n diagonal matrix, all elements are non-negative, and decreasing $\sigma 1 > \sigma 2 > \sigma 3… $.
• $V$ is n x n orthonormal matrix, aka right singular vectors

To solve for the above matrices, A’s correlation matrix $A^T A$ can be written as:

Note, because $V$ is orthonormal, $V^T=V^{-1}$. Then, $A^T A = V \Sigma^2 V^{-1}$, and that is eigen value decomposition. More explanation see here.

In fact, U and V are “unitary”. That is $UU^T = U^TU = I$. That means:

• V is the eigen vectors of $A^TA$

• $\Sigma = diag(\sqrt{\sigma_1}, \sqrt{\sigma_2} …)$ (mxn), where $\sigma_n$ are eigen values of $A^TA$

Similarly, $AA^T = U \Sigma^2 U^{-1}$. We can see that the eigen values of $AA^T$ and $A^TA$ are the same (their dimensions are different, but the one with larger dimension will just have more zeros).

• $U = [u_1 … u_n]$, eigen vectors of $AA^T$

So singular value decomposition of $A$ really is the eigen value decomposition of its correlation matrices, $A^TA$ and $AA^T$.

Important CAVEAT: do not compute SVD using the above method, it’s not accurate and not efficient. Method based on QR factorization is faster.

Interpretations of U, $\Sigma$, V

• Each singular value in sigma is an “importance”.
• Each column in $U$ corresponds to each singular value (or importance)
• $V$ is a “mixture” of columns.
  • Eventually, this will become: $\sqrt{\sigma_1} u_1 v_1^T + \sqrt{\sigma_2}u_2v_2^T …$ (the sum of outer products). Each term increasingly improves the estimate of SVD
• Economy SVD: we sometimes just care about the non-zero part of sigma and their corresponding eigen vectors in U, because their vector products comprise the final matrix $A$. So, the returned values are: $U$ as mxn, $\Sigma$ as nxn, and $V$ as nxn, are returned
  • Many times, people would return the first $r$ columns and rows of $U$ and $V^T$

Applications

• In eigen face, each column of U is a face’s pixels in columns
  • Each term $\sqrt{\sigma_1} u_1 v_1^T$ has rank 1, because it’s formed by only 1 linearly independ row and column
• Image Compression: By SVD’ing an image and keeping first 5 columns of the U matrix (so they are eigen vectors of the image column space) and first 5 rows of the V matrix, we can already see some features.
• Digital Watermark: after SVD’ing an image, one can change an column in $U$ or $V$ with low $\sigma$ value to their own “digital watermark”.

• Plane Detection

In OpenCV::cvFindExtrinsicCameraParams2, the goal is to find extrinsics of two cameras given 3D points from frame 1, and 2D pixel values from frame 2. This line actually does the check.

Code In Action

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <Eigen/Dense>
using namespace std;
int main() {
    // Define the matrix A
    Eigen::MatrixXd A(2, 3);
    A << 1, 0, 0,
         0, 2, 0;

    // Compute the SVD of A
    Eigen::JacobiSVD<Eigen::MatrixXd> svd(A, Eigen::ComputeFullU | Eigen::ComputeFullV);
    Eigen::MatrixXd U = svd.matrixU();
    Eigen::MatrixXd V = svd.matrixV();
    Eigen::VectorXd singularValues = svd.singularValues();

    cout<<U<<endl;
    cout<<V<<endl;
    cout<<singularValues<<endl;   
}

Here is an online C++ compiler with Eigen

More Remarks

SVD is like “Data Driven Generalization of Fourier Transform”. It’s one of the transformations used in the last generation computational science tools, which maps a system into a new coordinates. In a system like facial recognition, we have a bunch of data but no off-the-shelf mathematical model for Fourier Tranformation. SVD allows us to tailor a model with those data to the specific problem.

• It can be used in PCA to form a basis for a reduced-dimension coordinate system. This is used in Google Page Rank, facial recognition algorithms (eigen faces), recommender systems in Aamazon and facebook; It’s a very money-making tool ;).

• Previous
  Math - Interpoloation
• Next
  Math - t-SNE