Multicollinearity and SVD

Question

I compute the Singular Value Decomposition of a $n \times n$ matrix. If the matrix is not full rank, and I have 2 collinear columns, I end up with one singular value equal to 0. Is it possible to find out which columns of the original matrix are collinear from the result of the SVD ?

This is a simple example. I would then like, for a more complicated matrix where a group of columns are multicollinear, to identify this group.

Therefore I want to know if the SVD can go beyond just knowing the number of multicollinear columns and identifying the multicollinear group of columns.

Answer 1

You can do the following:

Compute the SVD of $A\in\mathbb{R}^{n\times n}$: $$ A=[U_1,U_2]\begin{bmatrix}\Sigma & 0 \\ 0 & 0\end{bmatrix}\begin{bmatrix}V_1^T \\ V_2^T\end{bmatrix}, $$ where $V_2\in\mathbb{R}^{n\times k}$, $k=\dim\mathcal{N}(A)$, is contains the orthonormal basis of the nullspace of $A$. Next, compute the QR factorization with pivoting of the matrix $V_2^T$ such that $$\tag{✽} V_2^T\Pi=QR=Q\begin{bmatrix}R_1 & R_2\end{bmatrix}, $$ where $\Pi$ is a permutation matrix and $R_1$ is nonsingular upper triangular matrix (e.g., MATLAB's qr function with three output arguments can do it). From $AV_2=0$ and (✽), we have now $$ 0 = AV_2=A\Pi\Pi^TV_2=A\Pi(V_2^T\Pi)^T=A\Pi\begin{bmatrix}R_1^T \\ R_2^T\end{bmatrix}Q^T $$ and hence (since $Q$ is square and non-singular) $$\tag{☺} A\Pi\begin{bmatrix}R_1^T \\ R_2^T\end{bmatrix}=0. $$ Now partition $A\Pi$ as $A\Pi=[A_1,A_2]$ conformingly to the partitioning of $R$ to get from (☺) that $$ A_1R_1^T+A_2R_2^T=0, $$ therefore $$ A_1=-A_2R_2^TR_1^{-T}. $$ Consequently, the columns of $A_1$ can be written as linear combinations of the columns of $A_2$ (with the coefficients given by the matrix $-R_2^TR_1^{-T}$). Note that you don't need to compute these coefficients, but only to compute the pivoted QR factorization. The permutation matrix can then be directly used to identify these dependent columns.

---

A simple MATLAB example:

The following matrix $A$ has rank 2:

A =

     1     3     1     2
     0     0     0     0
     1     0     0     0
     1     3     1     2

Using

[U S V]=svd(A)

gives

U =

    0.7063   -0.0344    0.7071    0.0000
         0         0   -0.0000    1.0000
    0.0486    0.9988    0.0000    0.0000
    0.7063   -0.0344   -0.7071   -0.0000

S =

    5.4835         0         0         0
         0    0.9650         0         0
         0         0    0.0000         0
         0         0         0    0.0000

V =

    0.2665    0.9638         0         0
    0.7728   -0.2136    0.5976    0.0000
    0.2576   -0.0712   -0.3586    0.8944
    0.5152   -0.1424   -0.7171   -0.4472

Hence

V2 = V(:,3:4)

Compute the QR factorisation of $V_2^T$ with pivoting:

[Q R e]=qr(V2','vector')

Q =

   -0.3721    0.9282
    0.9282    0.3721


R =

    0.9636   -0.1482         0   -0.2224
         0   -0.8321         0    0.5547

e =

     3     4     1     2

We can see, that the columns 3 and 4 are dependent on the others (actually only the second one from the structure of $R_2$).