Column Subset Selection with Outliers: Approximation Algorithms Using Fewer Columns

We study the column subset selection problem with outliers, where the goal is to select a small subset of columns that approximates the input matrix after discarding at most mm outlier columns. The existing bicriteria algorithm utilizes iterative uniform sampling and achieves a strong approximation guarantee, but its column complexity depends on the number of columns $d$ and can be substantially larger than $k$. A natural approach to reducing the column complexity is to use importance sampling. However, large importance scores need not correspond to columns useful for reconstructing the inliers, since arbitrary outliers may introduce high-leverage directions and dominate the sampling distribution. Directly applying importance sampling may make it difficult to preserve the inlier structure with a small number of selected columns. To address this difficulty, we propose a ridge-leverage peeling method that avoids separating inlier and outlier scores, allowing us to iteratively remove columns without identifying the outliers while controlling the number of discarded inliers. The resulting algorithm achieves a $(1+\epsilon )$-approximation using $O(k/{\epsilon }^2)$ columns while discarding at most $(1+\epsilon )m$ columns, improving the previous $O\left(\frac{k}{{\epsilon }^6}\left(\log \frac{d}{m}+\frac{1}{\epsilon }\right)\right)$ column bound, where $\epsilon \in (0,1/2)$. We further give an fixed-parameter tractable (FPT) algorithm that selects exactly $k$ columns while discarding at most $(1+\epsilon )m$ columns and achieves an $O(k/\epsilon )$-approximation.