mahout-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Ted Dunning (Commented) (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (MAHOUT-797) MapReduce SSVD: provide alternative B-pipeline per B=R' ^{-1} Y'A
Date Mon, 12 Dec 2011 06:58:30 GMT

    [ https://issues.apache.org/jira/browse/MAHOUT-797?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13167379#comment-13167379
] 

Ted Dunning commented on MAHOUT-797:
------------------------------------

The problem you are having is that a rank deficient matrix doesn't have an inverse because
some of the singular values are zero.

In the Cholesky decomposition of a rank deficient matrix, each step proceeds by dividing by
the next remaining diagonal element.  If that element is zero, then things cannot proceed.
 If you are lucky, you already have the basis formed and could just quit.  Otherwise, there
is more work to do, but that work depends on doing the step with the zero diagonal.  With
pivoting, you work on the columns/rows of the remaining matrix out of order so that you guarantee
to complete the basis.

In general, you should never compute the inverse of any matrix.  Instead, you should use some
sort of solver.  In the case of a triangular matrix, the solver is a back-substitution.
                
> MapReduce SSVD: provide alternative B-pipeline per B=R' ^{-1} Y'A
> -----------------------------------------------------------------
>
>                 Key: MAHOUT-797
>                 URL: https://issues.apache.org/jira/browse/MAHOUT-797
>             Project: Mahout
>          Issue Type: Improvement
>    Affects Versions: 0.5, 0.6
>            Reporter: Dmitriy Lyubimov
>            Assignee: Dmitriy Lyubimov
>             Fix For: Backlog
>
>         Attachments: MAHOUT-797.pdf
>
>   Original Estimate: 48h
>  Remaining Estimate: 48h
>
> Since alternative flow using Cholesky decomposition is extremely easy to add to existing
computations of BB', I am thinking of just adding an option that chooses between B-pipeline
with QR step and B-pipeline with Y'Y-Cholesky step. 
> Ongoing work and some initial code (Y'Y step) is here https://github.com/dlyubimov/mahout-commits/tree/MAHOUT-797.
> I also want to fix what's left unfixed in MAHOUT-638.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

        

Mime
View raw message