5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$).

$\endgroup$
  • $\begingroup$ Thank you very much ! That works very well, I am also able to detect quasi-multicollinearity, which was the reason to use SVD in the first place. $\endgroup$ – vkubicki Apr 23 '14 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.