On Partial Smoothness, Activity Identification and Faster Algorithms of $L_{1}$ Over $L_{2}$ Minimization
Min Tao, Xiao–Ping Zhang, Zi-Hao Xia
Abstract
The <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$L_{1}/L_{2}$</tex-math></inline-formula> norm ratio arose as a sparseness measure and attracted a considerable amount of attention due to three merits: (i) sharper approximations of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$L_{0}$</tex-math></inline-formula> compared to the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$L_{1}$</tex-math></inline-formula>; (ii) parameter-free and scale-invariant; (iii) more attractive than <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$L_{1}$</tex-math></inline-formula> under highly-coherent matrices. In this paper, we first establish the partly smooth property of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$L_{1}$</tex-math></inline-formula> over <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$L_{2}$</tex-math></inline-formula> minimization relative to an active manifold <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">${\cal M}$</tex-math></inline-formula> and also demonstrate its prox-regularity property. Second, we reveal that ADMM<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">${}_{p}$</tex-math></inline-formula> (or ADMM<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">${}^{+}_{p}$</tex-math></inline-formula>) can identify the active manifold within a finite iterations. This discovery contributes to a deeper understanding of the optimization landscape associated with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$L_{1}$</tex-math></inline-formula> over <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$L_{2}$</tex-math></inline-formula> minimization. Third, we propose a novel heuristic algorithm framework that combines ADMM<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">${}_{p}$</tex-math></inline-formula> (or ADMM<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">${}^{+}_{p}$</tex-math></inline-formula>) with a globalized semismooth Newton method tailored for the active manifold <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">${\cal M}$</tex-math></inline-formula>. This hybrid approach leverages the strengths of both methods to enhance convergence. Finally, through extensive numerical simulations, we showcase the superiority of our heuristic algorithm over existing state-of-the-art methods for sparse recovery.