A unified approach for projections onto the intersection of ℓ_1 and ℓ_2 balls or spheres
share
This paper focuses on designing a unified approach for computing the projection onto the intersection of an ℓ_1 ball/sphere and an ℓ_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(n log n) worst-case complexity and O(n) in practice. The efficiency of our proposed algorithms are demonstrated in numerical experiments.
READ FULL TEXT