Spectral proximal method for solving large scale sparse optimization

¹ Mathematical and Actuarial Sciences Department, Lee Kong Chian Faculty of Engineering and Science, University Tunku Abdul Rahman, 43000 Selangor, Malaysia
² Institute for Mathematical Research, Universiti Putra Malaysia, Serdang 43400, Malaysia

^* Corresponding author: gillianwoo@1utar.my

Abstract

In this paper, we propose to use spectral proximal method to solve sparse optimization problems. Sparse optimization refers to an optimization problem involving the ι₀ -norm in objective or constraints. The previous research showed that the spectral gradient method is outperformed the other standard unconstrained optimization methods. This is due to spectral gradient method replaced the full rank matrix by a diagonal matrix and the memory decreased from Ο(n²) to Ο(n). Since ι₀-norm term is nonconvex and non-smooth, it cannot be solved by standard optimization algorithm. We will solve the ι₀ -norm problem with an underdetermined system as its constraint will be considered. Using Lagrange method, this problem is transformed into an unconstrained optimization problem. A new method called spectral proximal method is proposed, which is a combination of proximal method and spectral gradient method. The spectral proximal method is then applied to the ι₀-norm unconstrained optimization problem. The programming code will be written in Python to compare the efficiency of the proposed method with some existing methods. The benchmarks of the comparison are based on number of iterations, number of functions call and the computational time. Theoretically, the proposed method requires less storage and less computational time.