Approximate null space of an almost singular matrix

Question

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.

Answer 1

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

Answer 2

@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.

---

$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}^{*} $$

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}^{*} $$

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}^{*} $$

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}^{*} $$

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.