An active-set proximal quasi-Newton algorithm for ℓ₁-regularized minimization over a sphere constraint

Abstract

The ${\ell }_1$-regularized minimization has been widely used in many data science applications, and certain special constrained ${\ell }_1$-regularized minimizations have also been proposed in some recent applications. In this paper, we consider a sphere constrained ${\ell }_1$-regularized minimization, which can arise in image processing, signal recognition and sparse principal component analysis. Viewing the sphere as a simple Riemannian manifold, manifold-based methods for non-smooth minimization can be applied to solve such a problem, but may still encounter slow convergence in some situations. Our objective of this paper is to propose a new and efficient active-set proximal quasi-Newton method for this problem. The idea behind is to speed up the convergence by separately handling the convergence of both the active and inactive variables. In particular, our method invokes a procedure to effectively estimate active and inactive variables, and then designs the search directions based on proximal gradients and quasi-Newton directions to efficiently treat the convergence of the active and inactive variables, respectively. We show that under some mild conditions, the global convergence is guaranteed, and the complexity is also performed to reveal the computational efficiency. Numerical experience on the ${\ell }_1$-regularized quadratic programming and sparse principal component analysis on both synthetic and real data demonstrates its robustness and efficiency.

Keywords:

• ${\ell }_1$-regularized optimization
• spherical constraint
• proximal gradient method
• quasi-Newton method
• active-set method

AMS-MSC2000:

• 90C30

Acknowledgments

The authors are grateful to the anonymous referees for their useful comments and suggestions to improve the presentation of this paper. Also, they would like to thank Dr. Shiqian Ma for kindly sharing their codes of ManPG-Ada.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 Let $\left\{a^k\right\}$ and $\left\{b^k\right\}$ be two vanishing sequences. We write $a^k=\mathrm{\Theta }\left(b^k\right)$ if there exist two positive scalars $C_1$ and $C_2$ such that $C_1|b^k|\le |a^k|\le C_2|b^k|$ holds for all k.

Additional information

Funding

The work of this author was supported in part by the National Natural Science Foundation of China (NSFC)- 12071332.