ℓ_p-regularized least squares (0 < p < 1) and critical path

This paper elucidates the underlying structures of ℓ_p-regularized least squares problems in the nonconvex case of 0 < p < 1. The difference between two formulations is highlighted (which does not occur in the convex case of p = 1): 1) an ℓ_p -constrained optimization (P^p_c) and 2) an ℓ_p-penalized (unconstrained) optimization (L_λ ^p). It is shown that the solution path of (L_λ^p) is discontinuous and also a part of the solution path of (P^p_c). As an alternative to the solution path, a critical path is considered, which is a maximal continuous curve consisting of critical points. Critical paths are piecewise smooth, as can be seen from the viewpoint of the variational method, and generally contain non-optimal points, such as saddle points and local maxima as well as global/local minima. Our study reveals multiplicity (non-monotonicity) in the correspondence between the regularization parameters of (P^p_c) and (L_λ^p). Two particular paths of critical points connecting the origin and an ordinary least squares (OLS) solution are studied further. One is a main path starting at an OLS solution, and the other is a greedy path starting at the origin. Part of the greedy path can be constructed with a generalized Minkowskian gradient. This paper of greedy path leads to a nontrivial close-link between the optimization problem of ℓ_p -regularized least squares and the greedy method of orthogonal matching pursuit.