Projections onto the Intersection of a One-Norm Ball or Sphere and a Two-Norm Ball or Sphere
- PDF / 631,382 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 11 Downloads / 231 Views
Projections onto the Intersection of a One-Norm Ball or Sphere and a Two-Norm Ball or Sphere Hongying Liu1 · Hao Wang2
· Mengmeng Song1
Received: 11 November 2019 / Accepted: 6 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper focuses on designing a unified approach for computing the projection onto the intersection of a one-norm ball or sphere and a two-norm ball or sphere. We show that the solutions of these problems can all be determined by the root of the same piecewise quadratic function. We make use of the special structure of the auxiliary function and propose a novel bisection algorithm with finite termination. We show that the proposed method possesses quadratic time worst-case complexity. The efficiency of the proposed algorithm is demonstrated in numerical experiments, which show the proposed method has linear time complexity in practice. Keywords Projection · Intersection · 1 ball · Bisection method · Duality Mathematics Subject Classification 49M29 · 90C06 · 90C46
1 Introduction The use of the 1 ball/sphere constraint (or equivalently the 1 norm regularization) often results in sparse solutions and empirical success in various applications [1–8]. One of the most popular methods for solving these problems is the (sub)gradient projection method and the block-coordinate descent method, since they only need the
Communicated by Juan Parra.
B
Hao Wang [email protected] Hongying Liu [email protected] Mengmeng Song [email protected]
1
School of Mathematical Sciences, Beihang University, Beijing 100083, China
2
School of Information Science and Technology, ShanghaiTech University, Shanghai 201210, China
123
Journal of Optimization Theory and Applications
calculations of the (sub)gradient of the objective to construct projection subproblems. Therefore, the efficiency of the (sub)gradient projection methods critically depends on the efficiency of solving the subproblems. These subproblems mainly include the following three types: (P1) Euclidean projection onto the intersection of an 1 ball and an 2 ball, (P2) Euclidean projection onto the intersection of an 1 sphere and an 2 sphere and (P3) Euclidean projection onto the intersection of an 1 ball and an 2 sphere. (P1) and (P3) are often involved in the gradient projection methods for sparse principal component analysis (sPCA) [1–3,9]. (P2) is an integral part in efficient sparse nonnegative matrix factorization [4,5], supervised online autoencoder intended for classification using neural networks that features sparse activity and sparse connectivity [6] and dictionary learning with “sparseness-enforcing projections” [7]. (P3) also arises in sparse generalized canonical correlation analysis (SGCCA) [8] and is used by Witten et al. [3] for computing the rank-1 approximation for a given matrix along with a block-coordinate descent method. Many studies have appeared focusing on the Euclidean projections involving an 1 ball [10–14], the common point of which is to formu
Data Loading...
