5
$\begingroup$

The square of the largest singular value of a linear map $A$ can be computed by using the power iteration for $A^TA$ and one advantage of this is that the iteration is matrix free, i.e. you only need to apply the linear map and its adjoint but never need the matrix $A$ explicitly.

Do you know any matrix free method to compute the largest singular value of a linear map $A$ that does not use applications of the adjoint, but only applications of the linear map $A$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

You could use the characterization $$ \sigma_{\max} = \max_{\dim S = 1} \min_{x \in S} \frac{||Ax||_2}{||x||_2} $$ Creating random vectors $x$ and computing the norm of $||Ax||_2$ will give an estimate (from below) of $\sigma_{\max}$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is there a reason why you didn't use $\sigma_\max = \max_{\|x\|_2=1}\|Ax\|_2? But more important: Do you know a way to provide (probabilistic) error estimates for this method? In fact, this was one of my first ideas as well, but it turned out that the method only gives very crude lower bounds. $\endgroup$
    – Dirk
    Jun 19 at 19:24
  • $\begingroup$ - No particular reason. - I am not surprised it is very slow to provide anything useful. No I do not know any estimate. $\endgroup$
    – user7440
    Jun 20 at 20:43
  • $\begingroup$ Here is another suggestion: * Y = []; x0 = [ normalized random vector non-null]; * Loop on k @ Y <- orthonormal basis for span{ [Y, random vector] } @ X <- orthonormal basis for the Krylov space K(x0, A) of dimension k @ Compute the SVD of $Y^T A X$ I do not know about error estimates for such method. $\endgroup$
    – user7440
    Jun 20 at 21:00

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.