- 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- approximation error after discarding at most 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 -approximation while selecting only original columns and discarding at most columns, thereby eliminating the dependence of the previous selected-column bound on the total number of columns . 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 columns with an approximation ratio of . The results are supported by theoretical analyses in the main text and appendices; no numerical experiments are reported.
Critical strengths
-
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 , eliminating its dependence on 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.
-
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 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
- Line 1 of Algorithm 6 sets the tail threshold to , whereas the proof of Lemma A.14 requires with a sufficiently small constant . A sufficiently large constant is instead used to control the number of selected columns. These constants serve different purposes and should not be conflated.
- Algorithm 5 describes the sampling constant as sufficiently small, whereas Lemma A.12 requires it to be sufficiently large. The algorithm and the proof should use a consistent requirement.
- The appendix defines , and the final trimming steps in Algorithms 2 and 3 remove as many columns as possible up to . However, the theorems claim that . For example, when , , and at least two columns are eligible for trimming, the current rule removes two columns, exceeding the stated budget of . 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
-
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?
-
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 and that the final squared spectral residual is at most . Do these corrections preserve the selected-column bound and all terms in the running-time bound of Theorem 3.5?
-
When 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 , and verify the boundary case .
2 comments
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 in Algorithm 5 to be sufficiently large, as required by Lemma A.12. In Algorithm 6, the parameters are and , with distinct constants. These choices are compatible. For example, taking and , where is the constant in Lemma A.13, ensures and . Combining this with Lemma A.12 gives the required spectral residual bound . These corrections only affect absolute constants. The number of selected columns remains , and the running time in Theorem 3.5 remains unchanged.
Weakness 1. Line 1 of Algorithm 6 sets the tail threshold to Ctailελ, whereas the proof of Lemma A.14 requires ctailελ with a sufficiently small constant ctail. A sufficiently large constant Ctail 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ελ, where ctail is a sufficiently small absolute constant, as specified in the proof of Lemma A.14. The selection budget remains r=⌈CtailK/ε⌉, where Ctail 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 ccov, 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⌉ 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∣).
The existing proofs support this correction. For Algorithm 2, the comparison deletion set has size at most m+εm/10≤(1+ε)m, and hence at most ⌊(1+ε)m⌋. For Algorithm 3, the proof gives ∣D∪B∣<M, so ∣D∪B∣≤M−1≤⌊(1+ε)m⌋. Thus, both comparison deletion sets remain feasible, and the approximation guarantees remain unchanged. When 0<εm<1, both sets contain at most m 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=ΔUgj⊤NWNgj+gj⊤Ngj. By the Sherman–Morrison identity, choosing 1/w>Uj preserves positive definiteness and the upper potential bound. The corrected analysis gives ∑jUj≤1/2, while the lower barrier satisfies ∑jLj≥2/3. Thus, there exists an index j with Uj<Lj, and choosing 1/w=(Uj+Lj)/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.