L1-norm Regularized L1-norm Best-fit line problem

We develop a sparse and outlier-insensitive method for one-dimensional line fitting that can be used as the basis for outlier-insensitive machine learning methods such as principal component analysis. The method is insensitive to outlier observations by formulating procedures as optimization problems seeking the $L_1$-norm best-fit line. It is also able to produce a small number of non-zero principal components with additional penalty term to take sparseness into account. Our algorithm has a worst-case time complexity of $O{(m^2n \log n)}$. Computational results demonstrate that this method can provide outlier-insensitive and sparse solutions. The space required rarely approaches the worst-case bound.