More Like this

1. A Converse to Banach's Fixed Point Theorem and its CLS Completeness

   Daskalakis, Constantinos; Tzamos, Christos; Zampetakis, Manolis (January 2018, 50th Annual ACM Symposium on the Theory of Computing)

   Banach's fixed point theorem for contraction maps has been widely used to analyze the convergence of iterative methods in non-convex problems. It is a common experience, however, that iterative maps fail to be globally contracting under the natural metric in their domain, making the applicability of Banach's theorem limited. We explore how generally we can apply Banach's fixed point theorem to establish the convergence of iterative methods when pairing it with carefully designed metrics. Our first result is a strong converse of Banach's theorem, showing that it is a universal analysis tool for establishing global convergence of iterative methods to unique fixed points, and for bounding their convergence rate. In other words, we show that, whenever an iterative map globally converges to a unique fixed point, there exists a metric under which the iterative map is contracting and which can be used to bound the number of iterations until convergence. We illustrate our approach in the widely used power method, providing a new way of bounding its convergence rate through contraction arguments. We next consider the computational complexity of Banach's fixed point theorem. Making the proof of our converse theorem constructive, we show that computing a fixed point whose existence is guaranteed by Banach's fixed point theorem is CLS-complete. We thus provide the first natural complete problem for the class CLS, which was defined in [Daskalakis, Papadimitriou 2011] to capture the complexity of problems such as P-matrix LCP, computing KKT-points, and finding mixed Nash equilibria in congestion and network coordination games. 

   more » « less
2. Fixed-point iterative linear inverse solver with extended precision

   https://doi.org/10.1038/s41598-023-32338-5  

   Zhu, Zheyuan; Klein, Andrew B.; Li, Guifang; Pang, Sean (December 2023, Scientific Reports)

   Abstract Solving linear systems, often accomplished by iterative algorithms, is a ubiquitous task in science and engineering. To accommodate the dynamic range and precision requirements, these iterative solvers are carried out on floating-point processing units, which are not efficient in handling large-scale matrix multiplications and inversions. Low-precision, fixed-point digital or analog processors consume only a fraction of the energy per operation than their floating-point counterparts, yet their current usages exclude iterative solvers due to the cumulative computational errors arising from fixed-point arithmetic. In this work, we show that for a simple iterative algorithm, such as Richardson iteration, using a fixed-point processor can provide the same convergence rate and achieve solutions beyond its native precision when combined with residual iteration. These results indicate that power-efficient computing platforms consisting of analog computing devices can be used to solve a broad range of problems without compromising the speed or precision. 

   more » « less
3. Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities

   Diakonikolas, J (January 2020, Proceedings of Thirty Third Conference on Learning Theory)

   null (Ed.)

   We leverage the connections between nonexpansive maps, monotone Lipschitz operators, and proximal mappings to obtain near-optimal (i.e., optimal up to poly-log factors in terms of iteration complexity) and parameter-free methods for solving monotone inclusion problems. These results immediately translate into near-optimal guarantees for approximating strong solutions to variational inequality problems, approximating convex-concave min-max optimization problems, and minimizing the norm of the gradient in min-max optimization problems. Our analysis is based on a novel and simple potential-based proof of convergence of Halpern iteration, a classical iteration for finding fixed points of nonexpansive maps. Additionally, we provide a series of algorithmic reductions that highlight connections between different problem classes and lead to lower bounds that certify near-optimality of the studied methods. 

   more » « less
4. Accelerated fixed-point iterative reconstruction for fiber borescope imaging

   https://doi.org/10.1364/OE.495252  

   Saiham, Dewan; Zhu, Zheyuan; Klein, Andrew_B; Pang, Shuo_S (October 2023, Optics Express)

   Computational imaging systems with embedded processing have potential advantages in power consumption, computing speed, and cost. However, common processors in embedded vision systems have limited computing capacity and low level of parallelism. The widely used iterative algorithms for image reconstruction rely on floating-point processors to ensure calculation precision, which require more computing resources than fixed-point processors. Here we present a regularized Landweber fixed-point iterative solver for image reconstruction, implemented on a field programmable gated array (FPGA). Compared with floating-point embedded uniprocessors, iterative solvers implemented on the fixed-point FPGA gain 1 to 2 orders of magnitude acceleration, while achieving the same reconstruction accuracy in comparable number of effective iterations. Specifically, we have demonstrated the proposed fixed-point iterative solver in fiber borescope image reconstruction, successfully correcting the artifacts introduced by the lenses and fiber bundle. 

   more » « less
5. CONJECTURES ABOUT SIMPLE DYNAMICS FOR SOME REAL NEWTON MAPS ON ℝ2

   https://doi.org/10.1142/S0218348X19500993  

   DE LEO, ROBERTO (September 2019, Fractals)

   We collect from several sources some of the most important results on the forward and backward limits of points under real and complex rational functions, and in particular real and complex Newton maps, in one variable and we provide numerical evidence that the dynamics of Newton maps [Formula: see text] associated to real polynomial maps [Formula: see text] with no complex roots has a complexity comparable with that of complex Newton maps in one variable. In particular such a map [Formula: see text] has no wandering domain, almost every point under [Formula: see text] is asymptotic to a fixed point and there is some non-empty open set of points whose [Formula: see text]-limit equals the set of non-regular points of the Julia set of [Formula: see text]. The first two points were proved by B. Barna in the real one-dimensional case. 

   more » « less