2
$\begingroup$

I have understood how CUR and SVD works, but have not been able to understand the following.

  1. How can we use CUR in place of the SVD decomposition?
  2. Do the $C$ and $R$ matrices in the CUR follow the same properties as those of $U$ and $V$ matrices in the SVD decomposition?

If we want to reduce the dimension of the original matrix, say, from $n$ to $k$, which matrix of CUR we can use to project original matrix, so that we will get $k$-dimensional data points?

$\endgroup$
1
$\begingroup$

In SVD decomposition:

$$ A_{m\times n}= U_{m\times m} \Sigma_{m\times n}V^{H}_{n\times n} $$ Here, $U$ and $V$ are unitary matrices of left- and right singular vectors, and $\Sigma$ is a diagonal matrix containing real singular values in a decreasing order.

In your application, you are using a truncated SVD (rank $k$), thus $$ A_{m\times n}\approx U_{m\times k} \Sigma_{k\times k}V^{H}_{k\times n} $$ where $U$ and $V$ are parts of unitary matrices containing left and right singular vectors corresponding to $k$ largest singular values.

Compare that to a $k$-rank CUR decomposition: $$ A_{m\times n}\approx C_{m\times k} U_{k\times k}R_{k\times n} $$

  • $C$ and $R$ in CUR decomposition contain $k$ columns and $k$ rows of $A$. Since rank-$k$ CUR decomposition is not unique, different CUR decomposition will feature different rows\columns.
  • Entries of $C$ and $R$ come directly from $A$ and have an easy interpretation, as opposed to entries of $U$ and $V$ in SVD decomposition.
  • $C$ and $R$ are not unitary in any way, as opposed to $U$ and $V$ in SVD decomposition.
  • $U$ in CUR decomposition is a full $k\times k$ matrix, as opposed to a real diagonal $k\times k$ matrix $\Sigma$.

So, taking into account that, I would not say that $C$ and $R$ in CUR decomposition follow the same properties as $U$ and $V$ in SVD decomposition. I would say, the only property that is the same between them is their dimensions ($m\times k$ and $k\times n$ in the rank-$k$ case).

Now, how can you use CUR instead of SVD. Instead of using a unique (not discussing repeating singular values) rank-$k$ SVD decomposition, that provides you with the best rank-$k$ approximation (in the Frobenius-norm sense), you will have to use one-of-many CUR decomposition. Depending on your purpose, you may want to choose one subset of CUR decomposition over the other, that is very problem- and algorithm dependent.

$\endgroup$
  • $\begingroup$ Can you please explain, which matrix (C or R) we can use to reduce the dimension of original data? $\endgroup$ – Prathamesh Raut Apr 1 '18 at 11:33
  • $\begingroup$ Usually, you would use both, to select $k$ columns and rows in $C$ and $R$, respectively. Technically, nothing prohibits you to use a CUR decomposition by taking $k_1$ columns from $C$ and $k_2$ rows in $R$ and adjusting $U$ accordingly. But I never saw that in action (might not have enough experience). $\endgroup$ – Anton Menshov Apr 1 '18 at 16:01
  • $\begingroup$ Is there any special formula to choose the values of $r$ and $c$, the number of rows and column to sample from original matrix $A$? $\endgroup$ – Prathamesh Raut Apr 11 '18 at 13:01
  • $\begingroup$ Please, don't use comments to ask new questions. But you are effectively asking a question, is there a formula to estimate the rank of the matrix. $\endgroup$ – Anton Menshov Apr 11 '18 at 13:09

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.