Circumcentered reflections method for wavelet feasibility problems

Abstract

We introduce a two-stage global-then-local search method for solving feasibility problems. The approach pairs the advantageous global tendency of the Douglas–Rachford method to find a basin of attraction for a fixed point, together with the local tendency of the circumcentered reflections method to perform faster within such a basin. We experimentally demonstrate the success of the method for solving nonconvex problems in the context of wavelet construction formulated as a feasibility problem. 

References

• F. J. Aragón Artacho, R. Campoy, and M. K. Tam. The Douglas–Rachford algorithm for convex and nonconvex feasibility problems. Math. Meth. Oper. Res. 91 (2020), pp. 201–240. doi: 10.1007/s00186-019-00691-9
• R. Behling, J. Y. Bello Cruz, and L.-R. Santos. Circumcentering the Douglas–Rachford method. Numer. Algor. 78.3 (2018), pp. 759–776. doi: 10.1007/s11075-017-0399-5
• R. Behling, J. Y. Bello-Cruz, and L.-R. Santos. On the linear convergence of the circumcentered-reflection method. Oper. Res. Lett. 46.2 (2018), pp. 159–162. issn: 0167-6377. doi: 10.1016/j.orl.2017.11.018
• J. M. Borwein, S. B. Lindstrom, B. Sims, A. Schneider, and M. P. Skerritt. Dynamics of the Douglas–Rachford method for ellipses and p-spheres. Set-Val. Var. Anal. 26 (2018), pp. 385–403. doi: 10.1007/s11228-017-0457-0
• J. M. Borwein and B. Sims. The Douglas–Rachford algorithm in the absence of convexity. Fixed-point algorithms for inverse problems in science and engineering. Springer, 2011, pp. 93–109. doi: 10.1007/978-1-4419-9569-8_6
• I. Daubechies. Orthonormal bases of compactly supported wavelets. Commun. Pure Appl. Math. 41.7 (1988), pp. 909–996. doi: 10.1002/cpa.3160410705
• N. D. Dizon, J. A. Hogan, and J. D. Lakey. Optimization in the construction of nearly cardinal and nearly symmetric wavelets. In: 13th International conference on Sampling Theory and Applications (SampTA). 2019, pp. 1–4. doi: 10.1109/SampTA45681.2019.9030889
• N. D. Dizon, J. A. Hogan, and S. B. Lindstrom. Circumcentering reflection methods for nonconvex feasibility problems. arXiv preprint arXiv:1910.04384 (2019). url: https://arxiv.org/abs/1910.04384
• D. J. Franklin. Projection algorithms for non-separable wavelets and Clifford Fourier analysis. PhD thesis. University of Newcastle, 2018. doi: 1959.13/1395028.
• D. J. Franklin, J. A. Hogan, and M. K. Tam. A Douglas–Rachford construction of non-separable continuous compactly supported multidimensional wavelets. arXiv preprint arXiv:2006.03302 (2020). url: https://arxiv.org/abs/2006.03302
• D. J. Franklin, J. A. Hogan, and M. K. Tam. Higher-dimensional wavelets and the Douglas–Rachford algorithm. 13th International conference on Sampling Theory and Applications (SampTA). 2019, pp. 1–4. doi: 10.1109/SampTA45681.2019.9030823
• B. P. Lamichhane, S. B. Lindstrom, and B. Sims. Application of projection algorithms to differential equations: Boundary value problems. ANZIAM J. 61.1 (2019), pp. 23–46. doi: 10.1017/S1446181118000391
• S. B. Lindstrom and B. Sims. Survey: Sixty years of Douglas–Rachford. J. Aust. Math. Soc. 110 (2020), 1–38. doi: 10.1017/S1446788719000570
• S. B. Lindstrom, B. Sims, and M. P. Skerritt. Computing intersections of implicitly specified plane curves. J. Nonlin. Convex Anal. 18.3 (2017), pp. 347–359. url: http://www.yokohamapublishers.jp/online2/jncav18-3
• S. G. Mallat. Multiresolution approximations and wavelet orthonormal bases of L²(R). Trans. Amer. Math. Soc. 315.1 (1989), pp. 69–87. doi: 10.1090/S0002-9947-1989-1008470-5
• Y. Meyer. Wavelets and operators. Cambridge University Press, 1993. doi: 10.1017/CBO9780511623820
• G. Pierra. Decomposition through formalization in a product space. Math. Program. 28 (1984), pp. 96–115. doi: 10.1007/BF02612715