On the Convergence Rate of Projected Gradient Descent for a Back-Projection based Objective
This work provides theoretical justification for faster optimization in inverse problems, which is incremental but useful for researchers and practitioners in computational imaging and signal processing.
The paper analyzes the convergence rate of projected gradient descent for a back-projection-based objective in ill-posed linear inverse problems, showing that it converges faster than least squares objectives, especially with badly conditioned operators, as supported by numerical experiments.
Ill-posed linear inverse problems appear in many scientific setups, and are typically addressed by solving optimization problems, which are composed of data fidelity and prior terms. Recently, several works have considered a back-projection (BP) based fidelity term as an alternative to the common least squares (LS), and demonstrated excellent results for popular inverse problems. These works have also empirically shown that using the BP term, rather than the LS term, requires fewer iterations of optimization algorithms. In this paper, we examine the convergence rate of the projected gradient descent (PGD) algorithm for the BP objective. Our analysis allows to identify an inherent source for its faster convergence compared to using the LS objective, while making only mild assumptions. We also analyze the more general proximal gradient method under a relaxed contraction condition on the proximal mapping of the prior. This analysis further highlights the advantage of BP when the linear measurement operator is badly conditioned. Numerical experiments with both $\ell_1$-norm and GAN-based priors corroborate our theoretical results.