9
$\begingroup$

I have a matrix $A \in \mathbb{R}^{p \times q}$ of rank $r$ and its SVD decomposition, i.e, $$ A = U S V^\top, $$ where $U \in \mathbb{R}^{p \times r}$ and $V \in \mathbb{R}^{q \times r}$ are orthonormal, $S = \mathrm{diag}\left(s_1, \dots, s_r\right)$, and $s_i \in \mathbb{R}$. I would like to compute SVD for $B = [A_{i_1}, \dots, A_{i_k}] \in \mathbb{R}^{p \times k}$, and $k \leq r$, i.e., for a matrix that consists of a full rank selection of columns from $A$.

If SVD is straightforwardly applied to $B$, then the time complexity would be $\mathcal{O}(pk\min(p,k))$. Can I do that more efficiently?

Note:

  • If you consider the the right singular vectors of $A$, column selection effectively leads to projecting these to a subspace in the canonical basis. Projection does not preserve the angles between the vectors, and hence one cannot do better than just re-doing the SVD on $B$.
  • However, does there exist a rotation of the $V$ singular vectors that preserves the angles and it could be done more efficiently than just running SVD on $B$?
$\endgroup$
2
  • $\begingroup$ If $B$ is just a selection of columns of $A$, why not simply multiplying $V^T$ with a permutation matrix which is truncated $\endgroup$
    – percusse
    Dec 4, 2015 at 8:35
  • 1
    $\begingroup$ Unfortunately, truncation of the column space does not lead to a valid decomposition of matrix $B$. It basically projects the original matrix $A$ onto the preserved column subspace. This does not solve the problem. $\endgroup$
    – maruan
    Dec 13, 2015 at 2:18

1 Answer 1

5
$\begingroup$

After some research, I managed to find a reasonable answer. The operation is called updating (in case of adding new columns to the original matrix) or donwdating (in case of removing) of the SVD. Full update/downdate of SVD with a single column can be done in $\mathcal{O}\left(r^2(1 + p + q)\right)$ time [1]. Such modifications of SVD can be also parallelized.

Here are a few links to papers that deal with this problem:

  1. Fast low-rank modifications of the thin singular value decomposition
  2. A stable and fast algorithm for updating the singular value decomposition
  3. A fast and stable algorithm for downdating the singular value decomposition
$\endgroup$
4
  • $\begingroup$ There is something fishy in your computational complexity. How can adding columns be $O(r^2)$ when reading the input (the column vector to add) may contain alone more than $r^2$ entries? $\endgroup$ Dec 16, 2015 at 20:00
  • $\begingroup$ Thanks for spotting this. I double checked and it's indeed $O(r^2 + p + q)$ given that all the data is already in memory. The $O(p + q)$ term comes from a couple of vector-to-matrix multiplications. $\endgroup$
    – maruan
    Dec 18, 2015 at 1:36
  • 1
    $\begingroup$ Are you sure it's not $O(r(p+q+r))$? That would make more sense to me, since I'd expect that you have to project your new column $x$ on the reduced $r$-dimensional space with something like $U^Tx$. $\endgroup$ Dec 18, 2015 at 7:05
  • $\begingroup$ Thanks. In fact, there are matrix-matrix multiplications ($p \times r$ and $q \times r$ with $r \times r$) that are necessary to construct new orthonormal subspace matrices. If one wants to update singular values only, you are right, the time complexity would be $O(r(p+q+r))$. $\endgroup$
    – maruan
    Dec 27, 2015 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.