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$?
Improve this question
$\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
    Commented 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
    Commented Dec 13, 2015 at 2:18

1 Answer 1

Reset to default
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
Improve this answer
$\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$
    – Federico Poloni
    Commented 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
    Commented 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$
    – Federico Poloni
    Commented 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
    Commented Dec 27, 2015 at 19:35

You must log in to answer this question.

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