acceptodds
Under review as a conference paper at ICLR 2027

Column Subset Selection with Outliers: Approximation Algorithms Using Fewer Columns

Abstract

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 and can be substantially larger than . 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 -approximation using columns while discarding at most columns, improving the previous column bound, where . We further give an fixed-parameter tractable (FPT) algorithm that selects exactly columns while discarding at most columns and achieves an -approximation.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Column Subset Selection, Outliers

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_2WxuOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies column subset selection with column outliers, using the optimal rank-kk approximation error after discarding at most mm columns as the benchmark. Assuming that this optimal error is positive and that an estimate within a factor of two is available, the authors propose a hierarchical peeling method guided by ridge leverage scores, followed by column sampling, spectral sparsification, and residual trimming on the original matrix. The paper claims that the method achieves a (1+ε)(1+\varepsilon)-approximation while selecting only O(k/ε2)O(k/\varepsilon^2) original columns and discarding at most (1+ε)m(1+\varepsilon)m columns, thereby eliminating the dependence of the previous selected-column bound on the total number of columns dd. In addition, the authors combine dimensionality reduction, a strong coreset for a truncated-residual objective, and exact search to obtain a fixed-parameter tractable algorithm that selects exactly kk columns with an approximation ratio of O(k/ε)O(k/\varepsilon). The results are supported by theoretical analyses in the main text and appendices; no numerical experiments are reported.

Critical strengths
  1. The improvement in the number of selected columns has clear theoretical significance. Compared with the result of Bhaskara and Kumar (2018) discussed in the paper, the authors claim to reduce the number of selected columns to O(k/ε2)O(k/\varepsilon^2), eliminating its dependence on dd while preserving the same approximation accuracy and outlier-budget relaxation. This directly addresses the challenge of obtaining a compact representation using original columns in the presence of outliers. If the key proof issues are resolved, this would constitute a valuable advance.

  2. The treatment of adaptive deletions and final outlier selection is insightful. Lemma 3.1 bounds the total ridge leverage mass of the surviving optimal inliers by 2k2k for any remaining set, while Lemma 3.2 provides score estimates that remain valid under arbitrary subsequent deletions, thereby supporting adaptive peeling. The authors also clearly distinguish the intermediate peeling set from the final residual-trimming set, so the analysis does not require each peeling deletion to correctly identify an outlier. This analytical framework is among the more convincing and potentially reusable aspects of the paper.

Critical weaknesses
  1. Line 1 of Algorithm 6 sets the tail threshold to CtailελC_{\mathrm{tail}}\varepsilon\lambda, whereas the proof of Lemma A.14 requires ctailελc_{\mathrm{tail}}\varepsilon\lambda with a sufficiently small constant ctailc_{\mathrm{tail}}. A sufficiently large constant CtailC_{\mathrm{tail}} is instead used to control the number of selected columns. These constants serve different purposes and should not be conflated.
  2. Algorithm 5 describes the sampling constant ccovc_{\mathrm{cov}} as sufficiently small, whereas Lemma A.12 requires it to be sufficiently large. The algorithm and the proof should use a consistent requirement.
  3. The appendix defines M=⌈(1+ε)m⌉M=\lceil(1+\varepsilon)m\rceil, and the final trimming steps in Algorithms 2 and 3 remove as many columns as possible up to MM. However, the theorems claim that ∣N∣≤(1+ε)m|N|\leq(1+\varepsilon)m. For example, when m=1m=1, ε=1/4\varepsilon=1/4, and at least two columns are eligible for trimming, the current rule removes two columns, exceeding the stated budget of 1.251.25. The comparison argument based on integer set cardinalities could support a stricter final trimming rule, but it does not directly establish the claimed bound for the set returned by the current pseudocode.
Questions for authors
  1. Please provide a complete derivation of the upper-barrier update in Lemma A.13, explicitly specifying the corrected upper-bound quantity, the positive-definiteness conditions, and the weight-selection rule. After correcting the sign, how can the upper- and lower-barrier conditions be shown to remain compatible at every iteration while preserving the claimed spectral-tail bound and running time?

  2. Please provide a consistent choice of constants for Algorithms 5 and 6. In particular, distinguish the small constant governing the tail threshold from the large constant controlling the number of selected columns, and verify that r≥16hr\geq16h and that the final squared spectral residual is at most ελ/16\varepsilon\lambda/16. Do these corrections preserve the O(k/ε2)O(k/\varepsilon^2) selected-column bound and all terms in the running-time bound of Theorem 3.5?

  3. When εm\varepsilon m is not an integer, which rounding rules are used for the intermediate peeling limit and the final trimming budget, respectively? Please explicitly revise Algorithms 2 and 3 so that their actual outputs satisfy the claimed bound ∣N∣≤(1+ε)m|N|\leq(1+\varepsilon)m, and verify the boundary case 0<εm<10<\varepsilon m<1.

2 comments

Weakness 1. Line 1 of Algorithm 6 sets the tail threshold to CtailελC_{\mathrm{tail}}\varepsilon\lambda, whereas the proof of Lemma A.14 requires ctailελc_{\mathrm{tail}}\varepsilon\lambda with a sufficiently small constant ctailc_{\mathrm{tail}}. A sufficiently large constant CtailC_{\mathrm{tail}} is instead used to control the number of selected columns. These constants serve different purposes and should not be conflated.

Response. Thank you for pointing out this typo. In Algorithm 6, the threshold should be θ=ctailελ\theta=c_{\mathrm{tail}}\varepsilon\lambda, where ctailc_{\mathrm{tail}} is a sufficiently small absolute constant, as specified in the proof of Lemma A.14. The selection budget remains r=⌈CtailK/ε⌉r=\lceil C_{\mathrm{tail}}K/\varepsilon\rceil, where CtailC_{\mathrm{tail}} is sufficiently large. This correction does not change the theoretical guarantees.

Weakness 2. Algorithm 5 describes the sampling constant (c_{\mathrm{cov}}) as sufficiently small, whereas Lemma A.12 requires it to be sufficiently large. The algorithm and the proof should use a consistent requirement.

Response. Thank you for pointing out this typo. In line 10 of Algorithm 5, “sufficiently small” should read “sufficiently large” for ccovc_{\mathrm{cov}}, consistent with the sampling requirement in the proof of Lemma A.12. This correction leaves the asymptotic sample-size bound unchanged.

Weakness 3 + Question 3. The appendix defines (M=\lceil(1+\varepsilon)m\rceil), and the final trimming steps in Algorithms 2 and 3 remove as many columns as possible up to (M). However, the theorems claim that (|N|\leq(1+\varepsilon)m). For example, when (m=1), (\varepsilon=1/4), and at least two columns are eligible for trimming, the current rule removes two columns, exceeding the stated budget of (1.25). The comparison argument based on integer set cardinalities could support a stricter final trimming rule, but it does not directly establish the claimed bound for the set returned by the current pseudocode. When (\varepsilon m) is not an integer, which rounding rules are used for the intermediate peeling limit and the final trimming budget, respectively? Please explicitly revise Algorithms 2 and 3 so that their actual outputs satisfy the claimed bound (|N|\leq(1+\varepsilon)m), and verify the boundary case (0<\varepsilon m<1).

Response. Thank you for pointing out this rounding inconsistency. We retain M=⌈(1+ε)m⌉M=\lceil(1+\varepsilon)m\rceil as the intermediate peeling limit. In the final trimming step of Algorithms 2 and 3, the number of discarded columns is corrected to min⁡(⌊(1+ε)m⌋, d−∣S∣)\min\left(\lfloor(1+\varepsilon)m\rfloor,\ d-|S|\right).

The existing proofs support this correction. For Algorithm 2, the comparison deletion set has size at most m+εm/10≤(1+ε)mm+\varepsilon m/10\le(1+\varepsilon)m, and hence at most ⌊(1+ε)m⌋\lfloor(1+\varepsilon)m\rfloor. For Algorithm 3, the proof gives ∣D∪B∣<M|D\cup B|<M, so ∣D∪B∣≤M−1≤⌊(1+ε)m⌋|D\cup B|\le M-1\le\lfloor(1+\varepsilon)m\rfloor. Thus, both comparison deletion sets remain feasible, and the approximation guarantees remain unchanged. When 0<εm<10<\varepsilon m<1, both sets contain at most mm columns, so the corrected algorithms satisfy the original outlier budget.

Question 1. Please provide a complete derivation of the upper-barrier update in Lemma A.13, explicitly specifying the corrected upper-bound quantity, the positive-definiteness conditions, and the weight-selection rule. After correcting the sign, how can the upper- and lower-barrier conditions be shown to remain compatible at every iteration while preserving the claimed spectral-tail bound and running time?.

Response. Thank you for identifying the sign error in Lemma A.13. We correct the upper bound quantity to Uj=gj⊤NWNgjΔU+gj⊤NgjU_j=\frac{g_j^\top NWNg_j}{\Delta_U}+g_j^\top Ng_j. By the Sherman–Morrison identity, choosing 1/w>Uj1/w>U_j preserves positive definiteness and the upper potential bound. The corrected analysis gives ∑jUj≤1/2\sum_jU_j\le1/2, while the lower barrier satisfies ∑jLj≥2/3\sum_jL_j\ge2/3. Thus, there exists an index jj with Uj<LjU_j<L_j, and choosing 1/w=(Uj+Lj)/21/w=(U_j+L_j)/2 preserves both barriers at every iteration. The resulting upper invariant yields the original spectral tail bound, and the matrix operations and number of iterations remain unchanged. We include the complete derivation in the revised proof of Lemma A.13.

Question 2. Please provide a consistent choice of constants for Algorithms 5 and 6. In particular, distinguish the small constant governing the tail threshold from the large constant controlling the number of selected columns, and verify that (r\geq16h) and that the final squared spectral residual is at most (\varepsilon\lambda/16). Do these corrections preserve the (O(k/\varepsilon^2)) selected-column bound and all terms in the running-time bound of Theorem 3.5?

Response. Thank you for these questions. We correct the constant ccovc_{\mathrm{cov}} in Algorithm 5 to be sufficiently large, as required by Lemma A.12. In Algorithm 6, the parameters are θ=ctailελ\theta=c_{\mathrm{tail}}\varepsilon\lambda and r=⌈CtailK/ε⌉r=\lceil C_{\mathrm{tail}}K/\varepsilon\rceil, with distinct constants. These choices are compatible. For example, taking ctail=1/(64Ctt)c_{\mathrm{tail}}=1/(64C_{\mathrm{tt}}) and Ctail=3072clevCttC_{\mathrm{tail}}=3072c_{\mathrm{lev}}C_{\mathrm{tt}}, where CttC_{\mathrm{tt}} is the constant in Lemma A.13, ensures r≥16hr\ge16h and ∥(I−ΠAS)C~∥22≤ελ32\Vert(I-\Pi_{A_S})\widetilde C\Vert_2^2 \le\frac{\varepsilon\lambda}{32}. Combining this with Lemma A.12 gives the required spectral residual bound ελ/16\varepsilon\lambda/16. These corrections only affect absolute constants. The number of selected columns remains O(k/ε2)O(k/\varepsilon^2), and the running time in Theorem 3.5 remains unchanged.

Reviewer_o4YNOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Column subset selection (CSS) refers to the task of finding a small subset of columns of a matrix that can serve as a basis for approximating all the columns in the original matrix. The authors consider a robust variant of CSS in which one allows the approximation to ignore a set of columns determined to be outliers. The authors appear to take inspiration from a similar approach for robustifying PCA in a way that makes it comparable to CSS. They propose two main algorithms. One that has low approximation error relative to the robust PCA objective but a controlled (but higher than desired) number of columns required; the other has exactly the number of selected columns as the robust PCA being approximated but at the cost of a less good approximation ratio. Both appear to be a substantial improvement over the preexisting method. The work is theoretical in nature and doesn't include numerical experiments.

Critical strengths

This is a well written paper. Despite the topic being theoretically sophisticated, the writing gives the reader a good sense of the overall story.

Critical weaknesses

Numerical experiments would be helpful for understanding whether the distinctions between the three algorithms in Table 1 pan out in practice.

Questions for authors

None

1 comment

Weakness 1. Numerical experiments would be helpful for understanding whether the distinctions between the three algorithms in Table 1 pan out in practice.

Response: Thank you for the suggestion. We agree that numerical experiments would help understand the performance of these algorithms in practice. Our work focuses on theoretical approximation guarantees for CSS with outliers. In particular, our bicriteria algorithm removes the dependence on dd from the selected-column bound while preserving the (1+ε)(1+\varepsilon) approximation and (1+ε)m(1+\varepsilon)m outlier allowance of prior work. We also provide an FPT algorithm that selects exactly kk columns with an O(k/ε)O(k/\varepsilon) approximation.

Reviewer_mKHFOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Column Subset Selection (CSS) is a special case of PCA in which only input features can be collected to span a subspace. The goal of CSS with outliers is to select k columns and m outlier columns so as the the sqaured distances from remaining columns to the subspace is minimized.

This paper provides new bicriteria approximation algorithms for CSS with outliers. The first result is a ridge-leverage score based peeling algorithm that achieve 1+ϵ1+\epsilon-approximantion while using O(k/ϵ2)O(k/\epsilon^2) columns and excluding (1+ϵ)m(1+\epsilon)m outliers. The second result is an FPT algorithm (with running time exponential on poly(k/ϵ)\mathrm{poly}(k/\epsilon)) that k/ϵk/\epsilon-approximantion by using kk columns but still excluding (1+ϵ)m(1+\epsilon)m outliers. The peeling algorithm is interesting to me. Authors also employ a few algorithmic techiniques to make the running near-linear.

Critical strengths

Interesting new results and techniques in an important problem.

Critical weaknesses

The main results in this paper all have bicriteria approximation guarantee, which requires to exclude more outliers, or using more columns, or both. Without a corresponding lower bound to support the necessity of this relaxtion, these upper bounds are not particularly strong. In particular, excluding more outliers can make the loss function considerably smaller and the approximation ratio appears to be a loose guarantee in this case.

Questions for authors

Is there any evidence that excluding (1+ϵ)m(1+\epsilon)m outliers is unavoidable? What is the main technical challenge to design algorithms that use the same number of outliers?

1 comment

Weakness 1. The main results in this paper all have bicriteria approximation guarantee, which requires to exclude more outliers, or using more columns, or both. Without a corresponding lower bound to support the necessity of this relaxtion, these upper bounds are not particularly strong. In particular, excluding more outliers can make the loss function considerably smaller and the approximation ratio appears to be a loose guarantee in this case.

Response. Thank you for raising this concern. Bhaskara and Kumar (2018, Corollary 13) provide relevant conditional hardness evidence. Under their Smallest rr-Edge Subgraph conjecture, obtaining a multiplicative approximation for PCA with at most mm discarded columns is NP-hard even when a substantially larger output dimension is allowed. Their reduction uses zero-optimum instances, so it does not directly establish the necessity of our specific (1+ε)m(1+\varepsilon)m allowance in the positive-error setting.

We agree that additional deletions can substantially reduce the reconstruction error. Our bicriteria algorithm preserves the same (1+ε)m(1+\varepsilon)m outlier allowance and (1+ε)(1+\varepsilon) approximation guarantee relative to OPTk,m(A)\mathrm{OPT}_{k,m}(A) as Bhaskara and Kumar (2018), while reducing the selected-column bound from O(kε6(log⁡dm+1ε))O(\frac{k}{\varepsilon^6}(\log\frac{d}{m}+\frac{1}{\varepsilon})) to O(k/ε2)O(k/\varepsilon^2). Thus, our improvement removes the dependence on dd and improves the dependence on ε\varepsilon without further relaxing the guarantees of prior work.

Question 1. Is there any evidence that excluding (1+ϵ)m(1+\epsilon)m outliers is unavoidable? What is the main technical challenge to design algorithms that use the same number of outliers?.

Response. Thank you for these questions. As discussed in our response to Weakness 1, Bhaskara and Kumar (2018, Corollary 13) provide conditional hardness evidence for maintaining the original outlier budget. Their reduction uses zero-optimum instances and does not establish the necessity of our specific (1+ε)m(1+\varepsilon)m allowance in the positive-error setting.

The main technical challenge is that the outlier set and the selected column span must be determined jointly. A column with a large reconstruction error may be an outlier or an important inlier whose direction is not well captured by the current span. Under a strict mm-outlier budget, an algorithm must handle such columns while maintaining a small selected-column set and the required approximation guarantee.

Our peeling approach illustrates this difficulty. Although we guarantee ∣D∩I⋆∣≤εm/10|D\cap I^\star|\leq\varepsilon m/10, the subsequent spectral approximation only covers the surviving columns. Thus, achieving an exact-mm guarantee would require controlling the reconstruction error of the removed optimal inliers or finding another feasible deletion set within the original budget.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.