Minimization of $L_1$ Over $L_2$ for Sparse Signal Recovery with Convergence Guarantee

The ratio of the $L_1$ and $L_2$ norms, denoted by $L_1/L_2$, becomes attractive due to its scale-invariant property when approximating the $L_0$ norm to promote sparsity. In this paper, we incorporate the $L_1/L_2$ formalism into an unconstrained model in order to deal with both noiseless and noisy observations. To design an efficient algorithm, we derive an analytical solution for the proximal operator of the $L_1/L_2$ functional. Since the analytical solution depends on the sparsity of an unknown signal, we develop a bisection search method to find the desired sparsity and the corresponding solution to the proximal operator of $L_1/L_2$. With the newly developed solver of the proximal operator, we propose a specific variable-splitting scheme for the alternating direction method of multipliers so that we can establish its global convergence under mild assumptions and prove its linear convergence rate under suitable conditions. Experimentally, we conduct extensive numerical simulations to demonstrate the efficiency of the proposed approach over the state-of-the-art methods in sparse signal recovery with and without noise.