2
$\begingroup$

It is known that solving systems of linear equations is reducible to SVD in a straightforward way; if you want to solve $\mathbf{Ax}=\mathbf{b}$, then you can perform SVD on $\mathbf{A}$ and minimize $||\mathbf{UDVx}-\mathbf{b}||$.

However, is there a reverse reduction that is also very efficient? That is, if you can solve linear equations, you can solve SVD?

EDIT: Because of Denis's comment/answer below, it looks like there isn't a reduction in general. But I'm interested in these problems over $\mathbb{C}$; so, the new question is: If we can solve linear equations over $\mathbb{C}$ exactly or approximately, can we perform an "approximate" SVD (for some suitable notion of "approximate")?

The answer still seems to be in the negative, but I defer to people who actually know something about this.

Improve this question
$\endgroup$
1
  • $\begingroup$ Most practical uses of SVD are approximate anyway, in the sense that exact closed forms to singular values (and thus vectors) are not easy to compute if the characteristic polynomial of $\mathbf{A}^T \mathbf{A}$ has degree > 4. $\endgroup$
    – J. M. isn't a mathematician
    Commented Nov 14, 2010 at 12:02

1 Answer 1

Reset to default
6
$\begingroup$

I don't think so. Solving linear equations is an algebraic problem, where the scalar field is arbitrary: $\mathbb R$ or $\mathbb C$, but also $\mathbb Q$, $\mathbb F_{p^n}$, $k(X)$, $\mathbb Q_p$, $\mathbb Q(\alpha)$ ($\alpha$ algebraic). In many cases, there is no analogue of SVD at all. This is why Gauss elimination remains meaningful.

When the scalar field is $\mathbb R$ or $\mathbb C$, SVD is one aspect of resolution. But it has the flaw that it cannot be done exactly in finitely many operation. Thus you have to choose between (costly) exact methods ($LU$ factorization, which is reminiscent to Gauss) or iterative approximations (relaxation, SSOR, conjugate gradient, SVD, ...) Notice that the conjugate gradient is theoretically an exact method, but in practice it is used in an iterative way.

You may have a look to my book Matrices : Theory and Applications, Grad. Text in Math. 216, Springer-Verlag. The second edition is released now.

Improve this answer
$\endgroup$
3
  • $\begingroup$ That's quite interesting. What do you mean by "one aspect of resolution"? $\endgroup$
    – Henry Yuen
    Commented Nov 14, 2010 at 8:32
  • $\begingroup$ @Henry: Denis means you can solve linear equations with SVD if the scalar field is $\mathbb{R}$ or $\mathbb{C}$ (though it is certainly the most expensive way to do so if your linear system isn't that ill-conditioned!); it's difficult to find usable analogues of SVD when the scalar fields are slightly more exotic. $\endgroup$
    – J. M. isn't a mathematician
    Commented Nov 14, 2010 at 12:05
  • $\begingroup$ The only other case where an SVD is known to exist is with $p$-adic entries. The field is $\mathbb Q_p$. See Kedlaya's book p-adic differential equations. Cambridge Studies in Advanced Mathematics, 125. Cambridge University Press, Cambridge, 2010. $\endgroup$
    – Denis Serre
    Commented Nov 14, 2010 at 13:03

You must log in to answer this question.

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