most recent 30 from http://mathoverflow.net 2013-05-20T16:49:58Z http://mathoverflow.net/feeds/question/46024 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46024/what-is-the-relationship-between-singular-value-decomposition-and-solving-linear Henry Yuen 2010-11-14T07:18:10Z 2010-11-14T08:35:41Z

<p>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}||$. </p> <p>However, is there a reverse reduction that is also very efficient? That is, if you can solve linear equations, you can solve SVD?</p> <p>EDIT: Because of Denis's comment/answer below, it looks like there isn't a reduction <i>in general</i>. 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")?</p> <p>The answer still seems to be in the negative, but I defer to people who actually know something about this.</p>

http://mathoverflow.net/questions/46024/what-is-the-relationship-between-singular-value-decomposition-and-solving-linear/46026#46026 Denis Serre 2010-11-14T08:23:38Z 2010-11-14T08:23:38Z

<p>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.</p> <p>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. </p> <p>You may have a look to my book <em>Matrices : Theory and Applications</em>, Grad. Text in Math. 216, Springer-Verlag. The second edition is released now.</p>