In this work, we propose an optimization framework for estimating a sparse
robust one-dimensional subspace. Our objective is to minimize both the
representation error and the penalty, in terms of the l1-norm criterion. Given
that the problem is NP-hard, we introduce a linear relaxation-based approach.
Additionally, we present a novel fitting procedure, utilizing simple ratios and
sorting techniques. The proposed algorithm demonstrates a worst-case time
complexity of $O(n^2 m \log n)$ and, in certain instances, achieves global
optimality for the sparse robust subspace, thereby exhibiting polynomial time
efficiency. Compared to extant methodologies, the proposed algorithm finds the
subspace with the lowest discordance, offering a smoother trade-off between
sparsity and fit. Its architecture affords scalability, evidenced by a 16-fold
improvement in computational speeds for matrices of 2000x2000 over CPU version.
Furthermore, this method is distinguished by several advantages, including its
independence from initialization and deterministic and replicable procedures.
Furthermore, this method is distinguished by several advantages, including its
independence from initialization and deterministic and replicable procedures.
The real-world example demonstrates the effectiveness of algorithm in achieving
meaningful sparsity, underscoring its precise and useful application across
various domains.

本文提出了一个针对估算稀疏鲁棒一维子空间的优化框架，通过最小化表示误差和惩罚来实现 l1 - 范数准则的优化。基于线性松弛方法，该算法在计算时间上具有最坏情况下的 O (n^2 m log n) 时间复杂度，并在某些情况下实现了稀疏鲁棒子空间的全局最优解，因此具有多项式时间效率。与现有方法相比，该算法能够找到具有最低不一致性的子空间，同时提供了稀疏性和拟合度之间更平滑的权衡。它的架构具有可伸缩性，对于 2000x2000 矩阵，计算速度相比 CPU 版本提高了 16 倍。此外，该方法独立于初始化，具有确定性和可复制性的优点。通过实际应用示例，证明了该算法在实现有意义的稀疏性方面的有效性，并强调其在各个领域中的精确和有用的应用。