6
$\begingroup$

I want to compute the Generalized Singular Value Decomposition for sparse matrices with a size of up to 1000000 x 1000000 (not necessarily square). The method is going to be used in machine learning (classification).

Currently I'm using the function ggsvd (here) from the LAPACK package which is a Fortran implementation.

What it does is computing matrices U, V, X, C, S for given matrices A and B such that

A = U * C * transposed(X)

B = V * S * transposed(X)

where C and S are diagonal matrices containing the singular values of A and B respective. (Explanation from Matlab)

With SVD one can do a low-rank approximation meaning that only the r largest singular values with most information are being computed to approximate the input matrix.

I am now wondering if this is also possible in the GSVD so that not all the singular values have to be computed. I would like to compute only the r largest values or to stop computing when a value is below a given threshold.

My assumption is that it's not possible because the singular values of A and B are computed pairwise and if a pair contains the largest singular value of A its mate of B doesn't have to be necessarily.

A short explanation why it is possible (and maybe a link to an implementation that offers this option) or not would be very nice.

$\endgroup$
  • 1
    $\begingroup$ Please note that ggsvd computes the generalized svd in a different form with respect to the one presented in matlab, see the lug. $\endgroup$ – Stefano M Jul 30 '13 at 11:17
  • 1
    $\begingroup$ With reference to the matlab gsvd, the generalized singular values are defined as sqrt(diag(C'*C)./diag(S'*S)) (or $\alpha_i / \beta_i$ with reference to the lug.) It is therefore possible to define the largest singular values. If those are useful for a low rank approx, it depends on your application, and also on the structure of your problem: which are the sizes and ranks of $A$ and $B$? $\endgroup$ – Stefano M Jul 30 '13 at 11:33
  • $\begingroup$ The sizes vary but can be up to 1000000x1000000. Not sure about the ranks. $\endgroup$ – Matthias Munz Jul 30 '13 at 12:47
  • 1
    $\begingroup$ Are both matrices square? Dense or sparse? Can you give the context in which you are looking for the gsvd? May be you should edit your question to clarify those points $\endgroup$ – Stefano M Jul 30 '13 at 13:00
  • $\begingroup$ The matrices are sparse and not square. The method is going to be used in machine learning (classification). $\endgroup$ – Matthias Munz Jul 30 '13 at 13:07
4
$\begingroup$

I'm not an expert in this field, but being your $A$ and $B$ sparse, matlab and LAPACK are not a good choice.

For sparse matrices a quick literature search confirmed that algorithms for the computation of a few extremal generalized singular values have been described, as one might expect. (Some random results from google scholar: http://www.win.tue.nl/~hochsten/pdf/jdgsvd.pdf and http://www.cs.berkeley.edu/~richie/cs294.data/project/reading/zha_sparse_gensvd.pdf.gz)

Unfortunately I'm not aware of their implementation in available libraries, but here I hope to be contradicted from the more knowledgeable.

$\endgroup$
  • $\begingroup$ I'm not sure if you read my comment thats why I paste it once again here: Stefano, could you explain in more detail, why it is possible in GSVD to only compute the r largest singular values for both A and B (and not compute the rest)?. I am still wondering what "pairwise" means here: netlib.org/lapack/explore-html/dd/db4/dggsvd_8f.html $\endgroup$ – Matthias Munz Aug 7 '13 at 8:29
  • $\begingroup$ It's just terminology: if $\sigma_i = \alpha_i / \beta_i$, then $\sigma_i$ are the generalized singular values of $(A, B)$. xGSVD returns the $(\alpha_i, \beta_i)$ pairs, and does not compute $\sigma_i$ for you (this is because $\beta_i$ may be equal to zero, the corresponding singular value being infinite). $\endgroup$ – Stefano M Aug 8 '13 at 17:24

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.