论文标题
$ l_1 $ - 正规化$ l_1 $ - norm最佳拟合线问题
$L_1$-norm regularized $L_1$-norm best-fit line problem
论文作者
论文摘要
这项工作开发了一种稀疏且异常的方法，可以拟合一维子空间，该子空间可以用作替代特征向量方法，例如主成分分析（PCA）。该方法通过将程序制定为优化问题，对基于$ \ ell^1 $ narmy寻求最佳拟合线的优化问题对异常观察不敏感。它还能够通过利用额外的惩罚条款引起稀疏性来产生稀疏的主组件。该算法的最差时间为$ o {（m^2n \ log n）} $，在某些条件下，会产生全球最佳解决方案。在合成和现实世界数据集中测试了该算法NVIDIA CUDA中该算法的实现，并将其与现有方法进行了比较。结果证明了所提出的方法的可伸缩性和效率。
This work develops a sparse and outlier-insensitive method to fit a one-dimensional subspace that can be used as a replacement for eigenvector methods such as principal component analysis (PCA). The method is insensitive to outlier observations by formulating procedures as optimization problems that seek the best-fit line according to the $\ell^1$ norm. It is also capable of producing sparse principal components by leveraging an additional penalty term induce sparsity. The algorithm has a worst-case time complexity of $O{(m^2n \log n)}$ and, under certain conditions, produces a globally optimal solution. An implementation of this algorithm in the parallel and heterogeneous environment NVIDIA CUDA is tested on synthetic and real world datasets and compared to existing methods. The results demonstrate the scalability and efficiency of the proposed approach.
