2
$\begingroup$

Say we've got $A\in\mathbb{R}^{N\times N}$, and $A=U\textrm{diag}(\sigma_1,\sigma_2,\ldots,\sigma_N) V^\top$ is its singular value decomposition. For a function $f\colon\mathbb{R}_{+}\to\mathbb{R}_{+}$, I am curious if there is a method for efficiently evaluating

$$\hat{A}=U\textrm{diag}(f(\sigma_1),\sigma_2,\ldots,\sigma_n)V^\top,$$ without having to compute the full SVD of $A$ (which can be quite expensive).

My motivation in thinking this might be possible is because for eigenvalues, one can compute the largest eigenvalue-eigenvector pair much faster (numerically speaking) than performing a full eigendecomposition. However, I feel like despite this, the answer is probably still no?

$\endgroup$
3
  • $\begingroup$ @littleO That's a good point -- both operations are quite similar, so if there was an efficient method for computing one, it may translate to the other. However, I haven't seen anything discussing a faster method of computing a rank-$k$ approximation either. I suppose I was hoping that perhaps this is a "simpler" operation, in some sense. $\endgroup$
    – Zim
    Dec 15, 2020 at 23:31
  • $\begingroup$ The answer given suggests a good method, so I'm going to delete my above comments. $\endgroup$
    – littleO
    Dec 16, 2020 at 15:01
  • 1
    $\begingroup$ scicomp.stackexchange.com/questions/7170/svd-and-lanczos-method You can use Krylov methods for the SVD. $\endgroup$
    – Ryan Howe
    Dec 17, 2020 at 14:25

1 Answer 1

Reset to default
2
$\begingroup$

I have not tried implementing this, but it is at least in theory possible to find the top singular vectors (left and right) by power method (just google "SVD power method" and such), and some others -- see here to start and follow the links.

Of course, once you know the top singular vectors and the top singular value it solves the problem in your question.

Indeed, $A=UDV^T$ means precisely that $A=\sum_i \sigma_i u_iv_i^T$ ($A$ takes the unit vector $v_i$ to $\sigma_i u_i$). To replace $\sigma_1$ by $f(\sigma_1)$ just add $(f(\sigma_1)-\sigma_1 )u_1v_1^T$ to $A$.

$\endgroup$
8
  • $\begingroup$ Once you know the top singular vectors (left and right) and the top singular value, how do you get $\hat A$? I don't see it. $\endgroup$
    – littleO
    Dec 16, 2020 at 8:39
  • $\begingroup$ See the edit for this. $\endgroup$
    – Max
    Dec 16, 2020 at 13:27
  • 1
    $\begingroup$ For non-zero singular values, the left singular vectors are eigenvectors of $A^TA$, and the right singular vectors are eigenvectors of $AA^T$. Equivalently, left singular vectors of $A$ are right singular vectors of $A^T$ and vice versa. Once you have any algorithm for one you just apply it to the transposed matrix (though the cost of running it might change of your matrix is very non-square). $\endgroup$
    – Max
    Dec 16, 2020 at 15:35
  • 1
    $\begingroup$ Yes, as one option. But I think you can save some compute, after all $(A^TA)^n=A^T(AA^T)^{n-1}A$. $\endgroup$
    – Max
    Dec 16, 2020 at 15:38
  • 1
    $\begingroup$ Right on, thanks for all the help @Max ! $\endgroup$
    – Zim
    Dec 16, 2020 at 15:40

You must log in to answer this question.

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