1
$\begingroup$

I have a matrix $$A=\begin{bmatrix}-0.0550 & -0.0870 & 0.6480 & 0.9830\\ 0.6270 & 0.9730 & 0.9840 & 0.3790\\ 0.6330 & 0.9830 & 0.5530 & -0.2260 \\ -0.1480 & -0.2310 & 0.9270 & 1.5130 \end{bmatrix}$$ and its determinant is $-2.55\cdot10^{-7}$. This matrix is almost singular. I apply SVD to $A$ and find $$\sigma_1=2.3498,\ \sigma_2=1.8096,\ \sigma_3=0.0005,\ \sigma_4=0.0001.$$ I want to know how to find a set $x$ for which $Ax$ is ''small'' can be regarded as an approximate null space. I assume I need to use $\sigma_3$ and $\sigma_4$ because entries of the last two columns of $AV$ are small.

$\endgroup$
2
$\begingroup$

You might want to look into the Eckart-Young theorem.

In a nutshell, write $A = \sum_i \sigma_i u_i v_i^T$ as the SVD where $\sigma_i$ are the singular values in descending order, and $u_i,v_i$ are the left and right respective singular vectors. If you let $A_k = \sum_{i \leq k} \sigma_i u_i v_i^T$, then $A_k$ an the optimal approximation of $A$ with rank $k$ in the Frobenius norm (and in fact, for any unitarily invariant norm).

If you take $x= v_i$, then $\lVert Ax \rVert = \sigma_i$. So, you could consider the span of the small right singular vectors as your approximate null space (which is the null space of the optimal rank $k$ approximation as above).

$\endgroup$
  • $\begingroup$ I think it is late to ask. Is there a way to find the basis for this null space? $\endgroup$ – Simple Oct 11 '16 at 23:43
  • $\begingroup$ As I said in the last sentence, the null space of the rank $k$ approximation is given by $span(v_{i+1},v_{i+2},\ldots)$. $\endgroup$ – Batman Oct 12 '16 at 0:35
3
$\begingroup$

@Batman has succinctly answered the question. Numerical details follow.


The matrix $\mathbf{A}$ has a singular value decomposition of the form $$ \begin{align} % \mathbf{A} &= % \left[ \begin{array}{llll} -0.055 & -0.087 & \phantom{-} 0.648 & \phantom{-} 0.983 \\ \phantom{-} 0.627 & \phantom{-} 0.973 & \phantom{-} 0.984 & \phantom{-} 0.379 \\ \phantom{-} 0.633 & \phantom{-} 0.983 & \phantom{-} 0.553 & -0.226 \\ -0.148 & -0.231 & \phantom{-} 0.927 & \phantom{-} 1.513 \\ \end{array} \right] \\[3pt] &= % \mathbf{U} \, \Sigma \, \mathbf{V}^{*} = % \mathbf{U} \, \left[ \begin{array}{cccc} 2.34981 & 0 & 0 & 0 \\ 0 & 1.80958 & 0 & 0 \\ 0 & 0 & 0.000464489 & 0 \\ 0 & 0 & 0 & 0.000129511 \\ \end{array} \right] \, \mathbf{V}^{*} \end{align} $$ The matrix $\mathbf{A}$ has rank $\rho=4$ and has a condition number of $$ \kappa_{2} = \frac{\sigma_{1}} {\sigma_{\rho}} \approx 18000 $$
You are asking about a low-rank approximation. (E.g., Low-rank Approximation with SVD on a Kernel Matrix) A sequence of approximations follows.

For example, the rank $2$ approximation uses the $2$ largest eigenvalues $$ \mathbf{A}_{2} = \mathbf{U} \, \left[ \begin{array}{cccc} 2.34981 & 0 & 0 & 0 \\ 0 & 1.80958 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{array} \right] \, \mathbf{V}^{*} $$ The total error is $$ \epsilon_{2} = \lVert \mathbf{A} - \mathbf{A}_{2} \rVert_{2} $$ The errors are plotted below for expansions using the largest eigenvalue, the two largest singular values, the three largest singular values, and all singular values.

errors


$k = 4$

The full rank case uses all $4$ singular values to reconstruct the input matrix $$\mathbf{A}_{4} = % \mathbf{U} \, \left[ \begin{array}{cccc} 2.34981 & 0 & 0 & 0 \\ 0 & 1.80958 & 0 & 0 \\ 0 & 0 & 0.000464489 & 0 \\ 0 & 0 & 0 & 0.000129511 \\ \end{array} \right] \, \mathbf{V}^{*} $$

A4

The total error is numerical noise $$ \epsilon_{4} = \lVert \mathbf{A} - \mathbf{A}_{4} \rVert_{2} = 1.17 \times 10^{-15} $$


$k = 3$

The next case uses the $3$ largest singular values to reconstruct the input matrix $$\mathbf{A}_{3} = % \mathbf{U} \, \left[ \begin{array}{cccc} 2.34981 & 0 & 0 & 0 \\ 0 & 1.80958 & 0 & 0 \\ 0 & 0 & 0.000464489 & 0 \\ 0 & 0 & 0 & 0 \\ \end{array} \right] \, \mathbf{V}^{*} $$

A3

The total error is negligible $$ \epsilon_{3} = \lVert \mathbf{A} - \mathbf{A}_{3} \rVert_{2} = 0.00013 $$

The row and column space both has a null space of dimension $1$, and these vectors are already computed; they are the final column vectors for the column and row space matrices. $$ % \begin{align} % \mathcal{N}\left( \mathbf{A} \right) &= \text{span } \left\{ \, \mathbf{V}_{4} \, \right\} \\ % \mathcal{N}\left( \mathbf{A}^{*} \right) &= \text{span } \left\{ \, \mathbf{U}_{4} \, \right\} % \end{align} % $$


$k = 2$

This case uses the $2$ largest singular values to reconstruct the input matrix $$\mathbf{A}_{2} = % \mathbf{U} \, \left[ \begin{array}{cccc} 2.34981 & 0 & 0 & 0 \\ 0 & 1.80958 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{array} \right] \, \mathbf{V}^{*} $$

A2

The total error is comparable to the previous case $$ \epsilon_{3} = \lVert \mathbf{A} - \mathbf{A}_{3} \rVert_{2} = 0.00046 $$

Now the row and column space both have a null space of dimension $2$; the final $2$ column vectors for the column and row space matrices. $$ % \begin{align} % \mathcal{N}\left( \mathbf{A} \right) &= \text{span } \left\{ \, \mathbf{V}_{3}, \, \mathbf{V}_{4} \, \right\} \\ % \mathcal{N}\left( \mathbf{A}^{*} \right) &= \text{span } \left\{ \, \mathbf{U}_{3}, \, \mathbf{U}_{4} \, \right\} % \end{align} % $$


$k = 1$

The last case uses only the largest singular value $$\mathbf{A}_{1} = % \mathbf{U} \, \left[ \begin{array}{cccc} 2.34981 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{array} \right] \, \mathbf{V}^{*} $$

A1

The total error $$ \epsilon_{4} = \lVert \mathbf{A} - \mathbf{A}_{4} \rVert_{2} = 1.80958 $$ is comparable to the size of the input matrix $$ \lVert \mathbf{A} \rVert_{2} = 2.34981 $$

The null spaces follow. $$ % \begin{align} % \mathcal{N}\left( \mathbf{A} \right) &= \text{span } \left\{ \, \mathbf{V}_{2}, \, \mathbf{V}_{3}, \, \mathbf{V}_{4} \, \right\} \\ % \mathcal{N}\left( \mathbf{A}^{*} \right) &= \text{span } \left\{ \, \mathbf{U}_{2}, \, \mathbf{U}_{3}, \, \mathbf{U}_{4} \, \right\} % \end{align} % $$


The panels below compare the low rank approximations more directly.

grid

$\endgroup$

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.