Piecewise Linearity of Min-Norm Solution Map of a Nonconvexly Regularized Convex Sparse Model

It is well known that the minimum ${\mathrm{\ell }}_2$-norm solution of the convex LASSO model, say ${\mathbf{x}}_{\star }$, is a continuous piecewise linear function of the regularization parameter $\lambda$, and its signed sparsity pattern is constant within each linear piece. The current study is an extension of this classic result, proving that the aforementioned properties extend to the min-norm solution map ${\mathbf{x}}_{\star }(\mathbf{y},\lambda )$, where $\mathbf{y}$ is the observed signal, for a generalization of LASSO termed the scaled generalized minimax concave (sGMC) model. The sGMC model adopts a nonconvex debiased variant of the ${\mathrm{\ell }}_1$-norm as sparse regularizer, but its objective function is overall-convex. Based on the geometric properties of ${\mathbf{x}}_{\star }(\mathbf{y},\lambda )$, we propose an extension of the least angle regression (LARS) algorithm, which iteratively computes the closed-form expression of ${\mathbf{x}}_{\star }(\mathbf{y},\lambda )$ in each linear zone. Under suitable conditions, the proposed algorithm provably obtains the whole solution map ${\mathbf{x}}_{\star }(\mathbf{y},\lambda )$ within finite iterations. Notably, our proof techniques for establishing continuity and piecewise linearity of ${\mathbf{x}}_{\star }(\mathbf{y},\lambda )$ are novel, and they lead to two side contributions: (a) our proofs establish continuity of the sGMC solution set as a set-valued mapping of $(\mathbf{y},\lambda )$; (b) to prove piecewise linearity and piecewise constant sparsity pattern of ${\mathbf{x}}_{\star }(\mathbf{y},\lambda )$, we do not require any assumption that previous work relies on (whereas to prove some additional properties of ${\mathbf{x}}_{\star }(\mathbf{y},\lambda )$, we use a different set of assumptions from previous work).