2
$\begingroup$

Given an $N \times 4$ matrix $A$ $(N \geq 4),$ I can find an approximate (non-trivial) solution to the homogeneous equation $A x = 0$ using singular value decomposition (SVD) assuming that one of the singular values is sufficiently small. Say the SVD yields $A = U \Sigma V^T$ and the smallest singular value is $\sigma,$ then the corresponding column of $V$ yields the approximate solution $\hat{x}.$ Can I quantify how good this solution is based on $\sigma$? Perhaps $\sigma$ tells me something about the magnitude of $\| A \hat{x} \|$?

For example, the matrix

$$ A = \left[\begin{array}{cccc} 2 & 2 & 2 & 2.3 \\ 4 & 4 & 4 & 4 \\ -1 & -1 & -1 & -1 \\ 5 & 5.1 & 5 &5 \\ 3.1 & 3 & 3 &3 \end{array} \right] $$ has singular values $\sigma_1 = 14.9275,$ $\sigma_2 = 0.260285,$ $\sigma_3 = 0.0986021,$ $\sigma_4 = 0.0322844.$ The last column of $V$ is $\hat{x} = [-0.313176,\ -0.457528,\ 0.830508,\ -0.0533385]^T$ which corresponds to $\sigma_4.$ We see this solution is close: $$ A \hat{x} = \left[\begin{array}{c} -0.00307055 \\ 0.025862 \\ -0.0064655 \\ -0.0134253 \\ -0.0119211 \end{array}\right] \approx \mathbf{0} $$ (check here) and $\| A \hat{x} \| = 0.0322866.$ We know the solution is normalized ($\| \hat{x} \|^2 = 1$), but can we quantify the error in the solution based on $\sigma_4?$

Edit: fixed arithmetic errors which match the answer.

$\endgroup$

1 Answer 1

4
$\begingroup$

Indeed, $\| A \hat x \| = \sigma$.

Note that $A = U \Sigma V^T \implies AV = U \Sigma$. Column by column, we see that $A v_i = \sigma_i u_i$, where $u_i$ and $v_i$ are the $i$th columns of $U$ and $V$, respectively, and $\sigma_i$ is the $i$th singular value of $A$.

So, $$ \| A v_i \| = \sigma_i \| u_i \| = \sigma_i. $$

$\endgroup$
3
  • $\begingroup$ But $sqrt(0.0002952607) \neq \sigma_4$? $\endgroup$
    – wcochran
    Sep 7, 2020 at 1:52
  • $\begingroup$ @wcochran Yeah, there must be an error either in the logic in my answer or in the arithmetic in that example. $\endgroup$
    – littleO
    Sep 7, 2020 at 2:04
  • $\begingroup$ Fixed my arithmetic error. Thx. $\endgroup$
    – wcochran
    Sep 7, 2020 at 23:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .