ℓ ₁ -Norm Regularized ℓ ₁ -Norm Best-Fit Lines

We propose an optimization framework for estimating a sparse outlier-insensitive one-dimensional subspace. Our objective is to minimize both the representation error and a penalty on the loadings using an [Formula: see text]-norm criterion for each. To our knowledge, computational methods for this pure [Formula: see text]-norm formulation have not been previously proposed. Given that the problem is NP-hard, we introduce a linear relaxation-based approach. We present a novel fitting procedure, utilizing sortings of simple ratios. The proposed algorithm has a worst-case time complexity of [Formula: see text]. We show that, under certain circumstances, the method achieves global optimality. Compared with previously proposed methods, the proposed algorithm often finds the subspace with the lowest discordance and offers a smoother tradeoff between sparsity of the estimate and fit. We demonstrate the scalability with a parallel GPU implementation that provides a 16-fold improvement in computational speed for matrices of 2,000 × 2,000 over a serial CPU implementation. Furthermore, this method is distinguished by several advantages, including the lack of a need for initialization and deter