A unified approach for projections onto the intersection of \ell₁ and \ell₂ balls or spheres

arXiv1911.03946MaRDI QIDQ6328874FDOQ6328874

Authors: Hongying Liu, Hao Wang, Mengmeng Song 

Publication date: 10 November 2019

Abstract: This paper focuses on designing a unified approach for computing the projection onto the intersection of an $el{l}_1$ ball/sphere and an $el{l}_2$ ball/sphere. We show that the major computational efforts of solving these problems all rely on finding the root of the same piecewisely quadratic function, and then propose a unified numerical method to compute the root. In particular, we design breakpoint search methods with/without sorting incorporated with bisection, secant and Newton methods to find the interval containing the root, on which the root has a closed form. It can be shown that our proposed algorithms without sorting possess $O(nlogn)$ worst-case complexity and $O(n)$ in practice. The efficiency of our proposed algorithms are demonstrated in numerical experiments.

This page was built for publication: A unified approach for projections onto the intersection of $\ell_1$ and $\ell_2$ balls or spheres

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328874)