l1-norm regularized l1-norm best-fit lines
This work addresses robust subspace estimation for applications requiring sparsity and computational efficiency, representing an incremental improvement with specific algorithmic advances.
The paper tackles the problem of estimating a sparse robust one-dimensional subspace by minimizing l1-norm representation error and penalty, proposing a linear relaxation-based algorithm with polynomial time complexity and achieving global optimality in some cases. It demonstrates a 16-fold speed improvement for 2000x2000 matrices and offers a smoother trade-off between sparsity and fit compared to existing methods.
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.