 # Compare the convergence of ADMM, SDMM, and GLM algorithms

XMLWordPrintable

## Details

• Type: Story
• Status: Done
• Resolution: Done
• Fix Version/s: None
• Component/s:
• Labels:
None
• Story Points:
3
• Sprint:
DRP S17-5
• Team:
Data Release Production

## Description

The convergence of our new algorithms, SDMM and GLMM are unknown as of now, so we should study the convergence rates of both algorithms (and compare them to the ordinary ADMM) to understand convergence in all three algorithms.

## Activity

The jupyter notebook testNMFproximal.ipynb shows a comparison of all three algorithms using the same settings, except that the ADMM algorithm can only use the monotonicity constraint while ADMM and GLMM use both monotonicity and symmetry.

Runtimes:

• ADMM: 1 min 23 sec
• SDMM: 1 min 0 sec
• GLMM: 22 sec

Convergence

• ADMM: The ADMM loops never converges, however the NMF algorithm converges after 11 iterations, for a total of 200*11 = 2200 iterations. As you can see from the convergence plots in testNMFproximal.ipynb, the ADMM solution nearly convergences in each step but then once the SED is updated in the NMF loop the solution becomes less convergent, which is part of the reason this procedure takes longer.
• SDMM: Using both monotonicity and symmetry greatly improves the convergence, as most SDMM loops converge in 60-150 iterations and the NMF loop converges in 11 iterations. Similar to the ADMM algorithm, convergence takes longer because updating the SED matrix pulls the intensity matrix away from its convergent value.
• GLMM: Only 169 iterations are needed to converge.

This demonstrates the power of both our new SDMM and GLMM algorithms, and shows that under the right conditions GLMM appears to be the best choice for the NMF deblender.

Show Fred Moolekamp added a comment - The jupyter notebook testNMFproximal.ipynb shows a comparison of all three algorithms using the same settings, except that the ADMM algorithm can only use the monotonicity constraint while ADMM and GLMM use both monotonicity and symmetry. Runtimes: ADMM: 1 min 23 sec SDMM: 1 min 0 sec GLMM: 22 sec Convergence ADMM: The ADMM loops never converges, however the NMF algorithm converges after 11 iterations, for a total of 200*11 = 2200 iterations. As you can see from the convergence plots in testNMFproximal.ipynb, the ADMM solution nearly convergences in each step but then once the SED is updated in the NMF loop the solution becomes less convergent, which is part of the reason this procedure takes longer. SDMM: Using both monotonicity and symmetry greatly improves the convergence, as most SDMM loops converge in 60-150 iterations and the NMF loop converges in 11 iterations. Similar to the ADMM algorithm, convergence takes longer because updating the SED matrix pulls the intensity matrix away from its convergent value. GLMM: Only 169 iterations are needed to converge. This demonstrates the power of both our new SDMM and GLMM algorithms, and shows that under the right conditions GLMM appears to be the best choice for the NMF deblender.

## People

• Assignee: Fred Moolekamp
Reporter: Fred Moolekamp
Reviewers:
Peter Melchior
Watchers:
Fred Moolekamp, Peter Melchior