Relationship between the optimal solutions of least squares regularized with ℓ0-norm and constrained by k-sparsity

Two widely used models to find a sparse solution from a noisy underdetermined linear system are the constrained problem where the quadratic error is minimized subject to a sparsity constraint, and the regularized problem where a regularization parameter balances the minimization of both quadratic error and sparsity. However, the connections between these two problems have remained unclear so far. We provide an exhaustive description of the relationship between their globally optimal solutions. A partial equivalence between them always exists. We exhibit a sequence of critical parameters that partitions the positive axis into a certain number of intervals. For every regularization parameter inside an interval, there is a sparsity level such that the regularized problem and the constrained problem have the same global minimizers. At the values of the critical parameters, the optimal set of the regularized problem contains two optimal sets of the constrained problem. When the length of the sequence of critical parameters equals the number of all sparsity levels, both problems are quasi-completely equivalent. The critical parameters are obtained from the optimal values of the constrained problem.