On the computational complexity of the conjugate-gradient method for solving inverse scattering problems

Abstract

This paper presents an efficient implementation of the inversion algorithm based on the conjugate-gradient method (CGM) for solving inverse scattering problems. The original CGM provides good image reconstruction and robustness to noise-corrupted data. This method requires the solution of the forward scattering problem and the Fréchet derivative operator of the cost function at each iteration step. However, these procedures can make the computational cost prohibitive, even for moderately sized problems. To avoid the computational burden, a two-step conjugate gradient fast Fourier transform (CG-FFT) procedure is proposed. Such an approach reduces the computational cost and storage requirements of the CGM implementation. The efficient CGM is found to share a computational complexity similar to the distorted-Born iterative method (DBIM). Thus the convergence speed and accuracy of the CGM is compared with the DBIM. Numerical tests using both synthetic and experimental data show effectiveness for solving 2D inverse scattering problems.

Keywords:

• Conjugate gradient method
• distorted born iterative method
• fast Fourier transform
• inverse scattering
• microwave imaging

Acknowledgments

This work has been supported by the Brazilian agencies CAPES and CNPq.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

Jose O. Vargas

Jose O. Vargas received the B.S. degree in Electronic Engineering from the Francisco de Paula Santander University, Cúcuta, Colombia, in 2015 and his M.S. degree in Electrical Engineering from the Federal University of Minas Gerais, Belo Horizonte, Brazil, in 2018. Currently, he is a Ph.D. candidate at the Federal University of Minas Gerais, Belo Horizonte, Brazil. His main research interests include electromagnetic field computation, microwave imaging, inverse problems, and optimization.

André Costa Batista

André Costa Batista received the B.S. degree in Systems Engineering from the Federal University of Minas Gerais, Belo Horizonte, Brazil in 2019. Currently, he is a Ph.D. candidate at the Federal University of Minas Gerais, Belo Horizonte, Brazil. His main research interests include microwave imaging, electromagnetic inverse scattering, inverse problems, optimization, and evolutionary computation.

Lucas S. Batista

Lucas S. Batista received his B.Sc. (2007), M.Sc. (2009), and Ph.D. (2011) degrees in Electrical Engineering from Universidade Federal de Minas Gerais (UFMG), Brazil. He is currently an associate professor with the Department of Electrical Engineering at UFMG. He is involved with the Electrical, Systems, Aerospace, and Control and Automation Engineering courses, as well as the graduate program in Electrical Engineering. His research interests include optimization, computational intelligence, evolutionary computation, decision-making theory, and applications to engineering design problems.

Ricardo Adriano

Ricardo Adriano received his Ph.D. in Electrical Engineering at Universidade Federal de Minas Gerais (UFMG). In 2007, he joined the INRETS–LEOST (The French Institute of Science and Technology for Transport) as a postdoctoral researcher. In 2008, he became an assistant professor at Universidade Federal de São João del-Rei. Afterwards, in 2011, he became an assistant professor at the Department of Electrical Engineering at UFMG. Prof. Adriano has been directly involved with UFMG's undergraduate courses on Systems Engineering and Aerospace Engineering, and with the Graduate Course on Electrical Engineering. His current research involves Computational Electromagnetics; Electromagnetic Compatibility and Optimization of electromagnetic devices.