Uploaded image for project: 'Data Management'
  1. Data Management
  2. DM-10090

Faster (and correct) conversion for NMF deblender

    Details

    • Type: Story
    • Status: Done
    • Resolution: Done
    • Fix Version/s: None
    • Component/s: meas_deblender
    • Labels:
      None

      Description

      The current deblender uses an alternating least squares algorithm to solve for the SED and Intensity matrices that model each source. The problem with this algorithm is that it fixes the intensity, solves for the SED using SDMM, fixes the SED, solves for intensity using SDMM, etc. until a solution converges (or a maximum number of iterations is reached), meaning that the correlation between the terms is ignored. So while each procedure in isolation is guaranteed to converge, the alternating solution is not, and in some cases does not. The good news is that even a non-convergent solution usually appears to be a good fit, however it takes longer for the algorithm to run.

      Boyd 2011 gives an algorithm to solve the NMF problem using ADMM with no constraints, which is an easier system to solve than the current deblender. However, Peter Melchior and I believe that we can adapt the algorithm to work with our current multiple linear constraint formalism (SDMM) to both guarantee convergence and assure faster convergence.

      Because this is a new algorithm, and likely to be the final major algorithmic change, we have decided to implement this procedure before profiling the code and testing the constraints, as optimal values might change slightly with the new algorithm.

        Attachments

          Activity

          Hide
          fred3m Fred Moolekamp added a comment -

          The algorithm has been implement, which is the main issue addressed in this ticket. We have no proof that the algorithm converges as of now, but that will be the work of a new ticket: DM-10138. This Jupyter notebook shows the same field run using the ADMM, SDMM, and GLMM algorithms, and shows that the SED matrix converges to nearly the exact same value in both the SDMM and ADMM algorithms.

          Show
          fred3m Fred Moolekamp added a comment - The algorithm has been implement, which is the main issue addressed in this ticket. We have no proof that the algorithm converges as of now, but that will be the work of a new ticket: DM-10138 . This Jupyter notebook shows the same field run using the ADMM, SDMM, and GLMM algorithms, and shows that the SED matrix converges to nearly the exact same value in both the SDMM and ADMM algorithms.
          Hide
          fred3m Fred Moolekamp added a comment -

          Hi Peter, do you mind reviewing this ticket now. I'm opening new tickets to study convergence and the possible necessity of the translation operator, but both of those issues are outside of the scope of this ticket, which was just to implement the algorithm.

          Show
          fred3m Fred Moolekamp added a comment - Hi Peter, do you mind reviewing this ticket now. I'm opening new tickets to study convergence and the possible necessity of the translation operator, but both of those issues are outside of the scope of this ticket, which was just to implement the algorithm.
          Hide
          pmelchior Peter Melchior added a comment -

          Excellent work! The new GLMM algorithm effectively still does line searches (in the direction of A and then of S), but it applies the constraints at each step instead of wasting iterations on a perfect A update, then a perfect S update, only to find out that these updates are in tension with each other. This is why the convergence is so much better than for the standard algorithm.

          Because we're still doing line searches, we have not truly solved the nonconvexity issue, but we have strongly mitigated its effects by locally linearizing the problem at each step.

          Show
          pmelchior Peter Melchior added a comment - Excellent work! The new GLMM algorithm effectively still does line searches (in the direction of A and then of S), but it applies the constraints at each step instead of wasting iterations on a perfect A update, then a perfect S update, only to find out that these updates are in tension with each other. This is why the convergence is so much better than for the standard algorithm. Because we're still doing line searches, we have not truly solved the nonconvexity issue, but we have strongly mitigated its effects by locally linearizing the problem at each step.
          Hide
          fred3m Fred Moolekamp added a comment -

          Thanks!

          Show
          fred3m Fred Moolekamp added a comment - Thanks!

            People

            • Assignee:
              fred3m Fred Moolekamp
              Reporter:
              fred3m Fred Moolekamp
              Reviewers:
              Peter Melchior
              Watchers:
              Fred Moolekamp, Peter Melchior
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Summary Panel