Optimizing Gradient Descent with Crank-Nicholson Scheme for Stable Convergence

[pamparana]

Hi everyone,

This is more of a numerical question but I felt this would be the most appropriate forum. I apologise if it is not.

I have a gradient descent problem of the following form:

$$\psi_{n+1}=\psi_{n}+\alpha(\nabla\psi_{n}*D^{2}\psi)$$

I am trying this on a 256x256 image grid where everything is spaced uniformly and dx and dy =1. I am using s step size of 0.5 using a normal gradient descent.

Somewhere down the line the algorithm gets very stable and I see some artefacts appearing and the whole thing falls apart and never converges.

Looking through the internet, people recommend using the Crank-Nicholson scheme to solve these kind of systems. However, I am having trouble formulating this in that scheme.

Would anyone know how I can structure this problem using the CN scheme? Also, is there a way to determine the optimal step-size parameter so as not to cause unstability at each iteration?

Thanks,

Luca

 

[jvicens]

Hello Luca,

Thank you for posting your question here. I can understand your frustration with the artefacts appearing and the instability of your algorithm. I have some experience with gradient descent problems and I can offer some suggestions that may help you.

Firstly, regarding the Crank-Nicholson (CN) scheme, it is a widely used numerical method for solving partial differential equations (PDEs). In your case, the PDE is the gradient descent problem you have stated. The CN scheme is based on a finite difference method that uses a weighted average of the current and next time steps to calculate the solution. It is known for its stability and accuracy, which makes it a suitable choice for your problem.

To formulate your problem using the CN scheme, you need to discretize your PDE into a system of equations. This can be done by dividing your image grid into smaller cells and approximating the derivatives using finite differences. Once you have the system of equations, you can then apply the CN scheme to solve it iteratively. There are many resources available online that can guide you through this process in more detail.

Regarding the optimal step-size parameter, there is no one-size-fits-all solution. It depends on the specific problem and the properties of the PDE being solved. In general, it is recommended to start with a small step size and gradually increase it until you find a good balance between stability and convergence. You can also try different step sizes at different iterations to see which works best for your problem.

I hope this helps and good luck with your research! Let me know if you have any further questions.