You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "David Jurgens (JIRA)" <ji...@apache.org> on 2009/12/05 00:11:20 UTC
[jira] Created: (MATH-321) Support for Sparse (Thin) SVD
Support for Sparse (Thin) SVD
-----------------------------
Key: MATH-321
URL: https://issues.apache.org/jira/browse/MATH-321
Project: Commons Math
Issue Type: New Feature
Reporter: David Jurgens
Current the SingularValueDecomposition implementation computes the full SVD. However, for some applications, e.g. LSA, vision applications, only the most significant singular values are needed. For these applications, the full decomposition is impractical, and for large matrices, computationally infeasible. The sparse SVD avoids computing the unnecessary data, and more importantly, has significantly lower computational complexity, which allows it to scale to larger matrices.
Other linear algebra implementation have support for the sparse svd. Both Matlab and Octave have the svds function. C has SVDLIBC. SVDPACK is also available in Fortran and C. However, after extensive searching, I do not believe there is any existing Java-based sparse SVD implementation. This added functionality would be widely used for any pure Java application that requires a sparse SVD, as the only current solution is to call out to a library in another language.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (MATH-321) Support for Sparse (Thin) SVD
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-321?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Luc Maisonobe updated MATH-321:
-------------------------------
Fix Version/s: 3.0
(was: 2.2)
SVD has been once again revamped for 2.1 and will probably be changed again soon.
We need to stabilize the implementation of regular SVD before working on this.
Postponing to 3.0
> Support for Sparse (Thin) SVD
> -----------------------------
>
> Key: MATH-321
> URL: https://issues.apache.org/jira/browse/MATH-321
> Project: Commons Math
> Issue Type: New Feature
> Reporter: David Jurgens
> Fix For: 3.0
>
>
> Current the SingularValueDecomposition implementation computes the full SVD. However, for some applications, e.g. LSA, vision applications, only the most significant singular values are needed. For these applications, the full decomposition is impractical, and for large matrices, computationally infeasible. The sparse SVD avoids computing the unnecessary data, and more importantly, has significantly lower computational complexity, which allows it to scale to larger matrices.
> Other linear algebra implementation have support for the sparse svd. Both Matlab and Octave have the svds function. C has SVDLIBC. SVDPACK is also available in Fortran and C. However, after extensive searching, I do not believe there is any existing Java-based sparse SVD implementation. This added functionality would be widely used for any pure Java application that requires a sparse SVD, as the only current solution is to call out to a library in another language.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (MATH-321) Support for Sparse (Thin) SVD
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-321?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12786673#action_12786673 ]
Luc Maisonobe commented on MATH-321:
------------------------------------
There is some work ongoing (very slowly though, I'm sorry about that) to improve both SVD and eigen decomposition.
The current implementation is a simplified version of lapack DSTEMR. Part of the simplification was to always compute all the eigenvalues, despite the original lapack function allowed to select some of them, either by a value range or by an index range. I want to remove this limitation and provide this feature in commons-math too.
This would be a first step towards partial SVD.
Any help on implementing this is welcome.
> Support for Sparse (Thin) SVD
> -----------------------------
>
> Key: MATH-321
> URL: https://issues.apache.org/jira/browse/MATH-321
> Project: Commons Math
> Issue Type: New Feature
> Reporter: David Jurgens
>
> Current the SingularValueDecomposition implementation computes the full SVD. However, for some applications, e.g. LSA, vision applications, only the most significant singular values are needed. For these applications, the full decomposition is impractical, and for large matrices, computationally infeasible. The sparse SVD avoids computing the unnecessary data, and more importantly, has significantly lower computational complexity, which allows it to scale to larger matrices.
> Other linear algebra implementation have support for the sparse svd. Both Matlab and Octave have the svds function. C has SVDLIBC. SVDPACK is also available in Fortran and C. However, after extensive searching, I do not believe there is any existing Java-based sparse SVD implementation. This added functionality would be widely used for any pure Java application that requires a sparse SVD, as the only current solution is to call out to a library in another language.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (MATH-321) Support for Sparse (Thin) SVD
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-321?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Phil Steitz updated MATH-321:
-----------------------------
Fix Version/s: (was: 2.1)
2.2
> Support for Sparse (Thin) SVD
> -----------------------------
>
> Key: MATH-321
> URL: https://issues.apache.org/jira/browse/MATH-321
> Project: Commons Math
> Issue Type: New Feature
> Reporter: David Jurgens
> Fix For: 2.2
>
>
> Current the SingularValueDecomposition implementation computes the full SVD. However, for some applications, e.g. LSA, vision applications, only the most significant singular values are needed. For these applications, the full decomposition is impractical, and for large matrices, computationally infeasible. The sparse SVD avoids computing the unnecessary data, and more importantly, has significantly lower computational complexity, which allows it to scale to larger matrices.
> Other linear algebra implementation have support for the sparse svd. Both Matlab and Octave have the svds function. C has SVDLIBC. SVDPACK is also available in Fortran and C. However, after extensive searching, I do not believe there is any existing Java-based sparse SVD implementation. This added functionality would be widely used for any pure Java application that requires a sparse SVD, as the only current solution is to call out to a library in another language.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (MATH-321) Support for Sparse (Thin) SVD
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-321?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12795630#action_12795630 ]
Luc Maisonobe commented on MATH-321:
------------------------------------
A partial fix as been committed in subversion repository as of r894908.
The current implementation computes either the compact SVD (considering only positive singular values) or the truncated SVD (considering a user-specified maximal number of singular values).
The issue is however not completely solved yet as the underlying eigendecomposition still computes all eigenvalues,. The SVD upper layer only truncates this computation afterwards. This means lots of things are computed just to be discarded later.
I'll take care of this shortly.
Also note that this implementation still considers only dense matrices, not sparse ones. Any contributions for sparse SVD is welcome!
> Support for Sparse (Thin) SVD
> -----------------------------
>
> Key: MATH-321
> URL: https://issues.apache.org/jira/browse/MATH-321
> Project: Commons Math
> Issue Type: New Feature
> Reporter: David Jurgens
>
> Current the SingularValueDecomposition implementation computes the full SVD. However, for some applications, e.g. LSA, vision applications, only the most significant singular values are needed. For these applications, the full decomposition is impractical, and for large matrices, computationally infeasible. The sparse SVD avoids computing the unnecessary data, and more importantly, has significantly lower computational complexity, which allows it to scale to larger matrices.
> Other linear algebra implementation have support for the sparse svd. Both Matlab and Octave have the svds function. C has SVDLIBC. SVDPACK is also available in Fortran and C. However, after extensive searching, I do not believe there is any existing Java-based sparse SVD implementation. This added functionality would be widely used for any pure Java application that requires a sparse SVD, as the only current solution is to call out to a library in another language.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (MATH-321) Support for Sparse (Thin) SVD
Posted by "Jake Mannix (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-321?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12786250#action_12786250 ]
Jake Mannix commented on MATH-321:
----------------------------------
I'm in the process of porting my sparse SVD work from decomposer (http://decomposer.googlecode.com) to Apache Mahout (see ticket MAHOUT-180 on the mahout JIRA), which has both non-parallized stream-based sparse SVD (using the generalized hebbian algorithm) as well as Hadoopified Lanczos and probabalistic partial decomposition. These are designed to scale to tens of millions of dimensions (the GHA version), and to billions of dimensions or more (in the Hadoopified version - add more machines to your Hadoop cluster, and you can go higher!).
> Support for Sparse (Thin) SVD
> -----------------------------
>
> Key: MATH-321
> URL: https://issues.apache.org/jira/browse/MATH-321
> Project: Commons Math
> Issue Type: New Feature
> Reporter: David Jurgens
>
> Current the SingularValueDecomposition implementation computes the full SVD. However, for some applications, e.g. LSA, vision applications, only the most significant singular values are needed. For these applications, the full decomposition is impractical, and for large matrices, computationally infeasible. The sparse SVD avoids computing the unnecessary data, and more importantly, has significantly lower computational complexity, which allows it to scale to larger matrices.
> Other linear algebra implementation have support for the sparse svd. Both Matlab and Octave have the svds function. C has SVDLIBC. SVDPACK is also available in Fortran and C. However, after extensive searching, I do not believe there is any existing Java-based sparse SVD implementation. This added functionality would be widely used for any pure Java application that requires a sparse SVD, as the only current solution is to call out to a library in another language.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (MATH-321) Support for Sparse (Thin) SVD
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-321?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Phil Steitz updated MATH-321:
-----------------------------
Fix Version/s: 2.1
> Support for Sparse (Thin) SVD
> -----------------------------
>
> Key: MATH-321
> URL: https://issues.apache.org/jira/browse/MATH-321
> Project: Commons Math
> Issue Type: New Feature
> Reporter: David Jurgens
> Fix For: 2.1
>
>
> Current the SingularValueDecomposition implementation computes the full SVD. However, for some applications, e.g. LSA, vision applications, only the most significant singular values are needed. For these applications, the full decomposition is impractical, and for large matrices, computationally infeasible. The sparse SVD avoids computing the unnecessary data, and more importantly, has significantly lower computational complexity, which allows it to scale to larger matrices.
> Other linear algebra implementation have support for the sparse svd. Both Matlab and Octave have the svds function. C has SVDLIBC. SVDPACK is also available in Fortran and C. However, after extensive searching, I do not believe there is any existing Java-based sparse SVD implementation. This added functionality would be widely used for any pure Java application that requires a sparse SVD, as the only current solution is to call out to a library in another language.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.