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$
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 '20 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 '20 at 2:04
  • $\begingroup$ Fixed my arithmetic error. Thx. $\endgroup$
    – wcochran
    Sep 7 '20 at 23:31

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.