A Barzilai-Borwein-like iterative half thresholding algorithm for the \(L_{1/2}\) regularized problem (Q292553)

Minimizing \(f(x)\) with \(L_{1/2}\) regularization means that we add to the objective function a regularization term of the form \(\rho\|x\|_{1/2}^{1/2}=\rho \sum_k |x_k|^{1/2}\) with \(\rho>0\). Different ideas from the literature are combined to get a new algorithm. An approximation of the objective function is obtained as in the iterative reweighted algorithm (IRL) of \textit{Z. Lu} [Math. Program. 147, No. 1--2 (A), 277--307 (2014; Zbl 1308.90170)]. If the objective function is an \(L_2\)-norm, a closed form IRL solution for the one-dimensional problem is used in [\textit{Z. Xu} et al., ``\(L_{1/2}\) regularization: a thresholding representation theory and a fast solver'', IEEE Trans. Neural Netw. Learn. Syst. 23, 1013--1027 (2012)] to formulate an iterative half thresholding algorithm (IHTA) for the \(L_2\)-\(L_{1/2}\) problem. The authors add to this a step-length computation of \textit{J. Barzilai} and \textit{J. M. Borwein} [IMA J. Numer. Anal. 8, No. 1, 141--148 (1988; Zbl 0638.65055)] and give a detailed formulation of the resulting BBIHTA algorithm. Conditions for convergence, sparsity of the result, and complexity of the algorithm are analyzed.