  The least squares problem is formulated in terms of Lp quasi-norm
regularization (0<p<1). Two formulations are considered: (i) an Lp-constrained
optimization and (ii) an Lp-penalized (unconstrained) optimization. Due to the
nonconvexity of the Lp quasi-norm, the solution paths of the regularized least
squares problem are not ensured to be continuous. A critical path, which is a
maximal continuous curve consisting of critical points, is therefore considered
separately. The 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. Along
each critical path, the correspondence between the regularization parameters
(which govern the 'strength' of regularization in the two formulations) is
non-monotonic and, more specifically, it has multiplicity. Two paths of
critical points connecting the origin and an ordinary least squares (OLS)
solution are highlighted. 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. The breakpoints of the
greedy path coincide with the step-by-step solutions generated by using
orthogonal matching pursuit (OMP), thereby establishing a direct link between
OMP and Lp-regularized least squares.
