Scaled Relative Graph: Nonexpansive operators via 2D Euclidean Geometry

Ernest Ryu, Robert Hannah, Wotao Yin

Not submitted yet:

Overview

Have you ever fallen asleep while reading a mathematical proof? Have you ever read a proof of convergence but felt you couldn't digest it?

Most convergece proofs of iterative algorithms are written in algebraic equalities and inequalities. Compared to figures, those equations look dull. Even when they are easy to verify, they may still be difficult to understand. Their core ideas of some proofs can be illustrated with figures, but, for the sake of rigor, we write them down with unfriendly equations. It is fair to say that lack of an intuitive way to present a proof creates a barrier between the author and the reader.

The good news is, for nonexpansive operators that constitute popular optimization methods such as forward-backward, alternative projection, Douglas-Rachford, and ADMM, there exist simple 2D graphs that not only capture the core ideas of their convergence proofs but is also a tool to write rigorous proofs and even find best parameters.

In this paper, we introduce a geometric approach to analyzing contractive and nonexpansive fixed point iterations with a new tool called the scaled relative graph (SRG). The SRG provides a rigorous correspondence between nonlinear operators and subsets of the 2D plane. Under this framework, a geometric argument in the 2D plane becomes a rigorous proof of contractiveness of the corresponding operator.

While the reader must see our paper for SRG's definition and examples, below we illustrate how a statement is easily proved by SRG.

 

Citation

E. Ryu, R. Hannah, W. Yin, Scaled relative graph: nonexpansive operators via 2d Euclidean geometry, arXiv:1902.09788, 2019.


« Back