Linear Time Approximation Algorithm for Column Subset Selection with Local Search
Authors: YuanBin Zou
Ziyun Huang
Jinhui Xu
Jianxin Wang
Qilong Feng
Venue: NeurIPS 2024 poster (2024)
Keywords: Column Subset Selection
Local Search
Primary area: optimization

Abstract: The Column Subset Selection (CSS) problem has been widely studied in dimensionality reduction and feature selection. The goal of the CSS problem is to output a submatrix S, consisting of k columns from an n×d input matrix A that minimizes the residual error ‖A-SS^\dagger A‖_F^2, where S^\dagger is the Moore-Penrose inverse matrix of S. Many previous approximation algorithms have non-linear running times in both n and d, while the existing linear-time algorithms have a relatively larger approximation ratios. Additionally, the local search algorithms in existing results for solving the CSS problem are heuristic. To achieve linear running time while maintaining better approximation using a local search strategy, we propose a local search-based approximation algorithm for the CSS problem with exactly k columns selected. A key challenge in achieving linear running time with the local search strategy is how to avoid exhaustive enumerations of candidate columns for constructing swap pairs in each local search step. To address this issue, we propose a two-step mixed sampling method that reduces the number of enumerations for swap pair construction from O(dk) to k in linear time. Although the two-step mixed sampling method reduces the search space of local search strategy, bounding the residual error after swaps is a non-trivial task. To estimate the changes in residual error after swaps, we propose a matched swap pair construction method to bound the approximation loss, ensuring a constant probability of loss reduction in each local search step. In expectation, these techniques enable us to obtain the local search algorithm for the CSS problem with theoretical guarantees, where a 53(k+1)-approximate solution can be obtained in linear running time O(ndk^4\log k). Empirical experiments show that our proposed algorithm achieves better quality and time compared to previous algorithms on both small and large datasets. Moreover, it is at least 10 times faster than state-of-the-art algorithms across all large-scale datasets.

Linear Time Approximation Algorithm for Column Subset Selection with Local Search
Yuanbin Zou Ziyun Huang", Jinhui Xu*, Jianxin Wang Qilong Feng :2:
School of Computer Science and Engineering, Central South University, Changsha 410083, China
"Xiangjiang Laboratory, Changsha 410205, China
Department of Computer Science and Software Engineering, Penn State Erie, The Behrend College
*Department of Computer Science and Engineering, State University of New York Buffalo. NY, USA
The Hunan Provincial Key Lab Bioinformatics, Central South University, Changsha 410083, China
yuanbinzou@csu. edu, cn, csuf eng@mail csu. edu. cn, zxh201 0psu edu, jinhui@buff alo. edu, jxwang@mail, csu. edu. cn
Abstract
The Column Subset Selection (CSS) problem has been widely studied in dimen- sionality reduction and feature selection. The goal of the CSS problem to output submatrix S, consisting of k columns from SSTA| Al where S the Moore-Penross inverse
input matrix A that mini-
mizes the residual error | - SS matrix of S. Many previous approximation algorithms have non-linear running times in both n and d, while the existing linear-time algorithms have a relatively larger approximation ratios. Additionally, the local search algorithms in existing results for solving the CSS problem are heuristic. To achieve linear running time while maintaining better approximation using local search strategy, we propose a local search- based approximation algorithm for the CSS problem with exactly k columns selected. A key challenge achieving linear running time with the local search strategy is how to avoid exhaustive enumerations of candidate columns for constructing swap pairs in each local search step. To address this issue, we propose a two-step mixed sampling method that reduces the number of enumer- ations for swap pair construction from (dd) two-step mixed sampling method reduces the search space of local search strat- egy, bounding the residual error after swaps is non-trivial task. To estimate the changes in residual error after swaps, we propose matched swap pair construction method to bound the approximation loss, ensuring a constant probability loss reduction in each local search step. In expectation, these techniques enable us to obtain the local search algorithm for the CSS problem with theoretical guarantees, where 53(k 1)-approximate solution (ndkk* 4 log k)). Empirical experiments show that our proposed algorithm achieves better quality and time compared to previous algorithms on both small and large datasets. Moreover, it is at least 10 times faster than state-of-the-a algorithms across all large-scale datasets.
linear time. Although the
be obtained in linear running time
"Corresponding Author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Introduction
In machine learning, handling high-dimensional datasets often requires the use of dimensionality re- duction techniques, among which Singular Value Decomposition (SVD) is one of the most commonly utilized techniques practice. The goal of SVD is minimize the Frobenius norm of the error, aiming to achieve a low-rank approximation of matrix with theoretical guarantees. An alternative way select small subset of columns from the matrix as representations well approximate the given matrix, which is known as the Column Subset Selection (CSS) problem. The CSS problem has been widely studied in machine learning for dimensionality reduction with improved interpretability. As pointed out in [4 17 13 20), the number of selected columns k is much smaller than both and d, i.e., < min (n,d). d]. We consider the following CSS problem.
Definition 1.1. Given a matrix A E Ruxd and a positive integer k. the goal of CSS problem is to select k columns of A forming a matrix S E Baak that minimizes the residual error
|| - S
where St represents the the square of Frobenius norm.
inverse matrix of S. and || = E Σj=1 A2 denotes
The CSS problem is known to be UG-hard (9] For the CSS problem, several heuristic algorithms
22 23
were proposed. However, main concern for these heuristics is the lack of theoretical
guarantees on both the running time and approximation error. Several (1 + -)-aprooximaaion bi-
criteria algorithms have been proposed for the CSS problem [19 4 3 15 Many of these algorithms achieve running time of O(nd poly(k)). which referred to as linear in both n and d [26] [1]. Although these algorithms achieve (1 + =appprooxiittnnn,, they require selecting more than & columns. For the CSS problem with exactly & columns selected, Boutsidis et al. [5) proposed an O log k)- approximation algorithm with (minn(n²d, ndf) }) running time, using leverage score sampling and QR decomposition methods. Deshpande and Rademacher [13] proposed a volume sampling algorithm, which yields a (A: + 1>-approximation in time O(kdn logn). n) Guruswami and Sinop [T9] gave an improved approximation algorithm with O(n2dk) dk) rumning time using fast volume sampling method, achieving the same (k + 111++-papppa -aappoxiimatin The running time of these algorithms has at least a quadratic dependence on n or d. Deshpande and Vempala [15] presented a linear- time algorithm with (k + 1) )-aapproximation using adaptive sampling method.
Although the algorithm using the adaptive sampling method 15) achieves the linear running time, its approximation ratio is considerably larger than other algorithms. Moreover, shown in 23 local search can improve the quality of the solution for the CSS problem. However, a potential limitation of the local search algorithm proposed in (23 is the lack of theoretical guarantees on the number of local search steps required for reaching convergence.
To apply the local search strategy to handle the CSS problem, the running time of each iteration is quadratically dependent on d, making it impractical for large-scale datasets. More specifically, the single-swap strategy in local search enumerates Okk)) swaps to improve the current solution, where the swap pair is constructed between the given matrix and the set of selected columns during the local search step. This method results in an O(nd2 x22) running time in each iteration, making difficult to maintain linear running time in both n and d. Secondly, to the best of our knowledge, there is no available result that provides an approximation guarantee for solving the CSS problem using the local search strategy.
1.1 Our Contribution
In this paper, propose a local search algorithm for solving the CSS problem with running time linear in both n and d. The key challenge for the local search algorithm is to avoid the (nd
running time caused by enumerating all possible swap pairs. To overcome this challenge, we propose a two-step mixed sampling method that selects a candidate column with a specific probability for swapping, reducing the enumeration of swap pairs from (dk) to k. By applying the two-step mixed sampling method, the running time of each local search step is reduced from O(nd² to O(ndk?).
Although the two-step mixed sampling method accelerates the local search process, bounding the residual error of the solution after swaps is a non-trivial task. Specifically, it is challenging to theoretically estimate the improvement in the approximation loss of the current solution after swaps.

---

To address this issue, we propose a matched swap-par pair construction method. This method identifies matched column pairs between the current solution and the optimal solution. Based on these matched pairs, we guarantee that the two-step mixed sampling method can find a column. With constant probability, this column reduces the residual error of the updated solution by a multiplicative factor of (1/k) in each local search step. With this approach, the expected number of iterations can be bounded by ( log k). Therefore, we obtain a local search-based approximation algorithm with OOdkk* log k) running time. The main contributions of this paper are summarized as follows.
For the CSS problem, we propose a new algorithm that uses local search with two-step mixed sampling method. This method avoids the quadratic dependence of d on running time by reducing the number of swap pair enumerations during the local search process. Addi- tionally, we propose a matched swap-pair construction method to bound the improvement of residual error during swaps. With these techniques, we achieve a 53(k + aapprooximtaoo with exactly l columns selected, where the running time of our proposed algorithm is (nddk* log k).
Numerical experiments show that our algorithm performs better in terms of quality both small and large datasets compared to previous algorithms that selects exactly k columns, and is least 10 times faster than the state-of-the-ard algorithms on all large datasets.
Table I:
Comparison of existing results for the CSS Problem with exactly columns selected, where is the number of rows in the given matrix, d is the number of columns, and k is the number of selected columns.
References
Approximation Ratio
Method
Running Time
15
(k + 1)!
adaptive sampling
O(ndk*)
O log
leverage score sampling + QR decomposition
(minn( ndf))
13
++1 k
volume sampling
O(kn log n) O O(ndk log k)
19
fast volume sampling
This paper
53 + 1)
local search + two-step mixed sampling
1.2 Related Work
Within the framework of rank-revealing QR factorization (RRQR) several poly(k: d)- approximation results 7 [8] have been proposed. These results achieve running time of Ondd)) while selecting exactly k columns to solve the CSS problem with Frobenius norm error. Deshpande al. [4] gave the lower bound of (k: + 1>aapproximation for the problem. Furthermore, Boutsidis et al. 5 proposed a randomized algorithm with Ominn (n²²,, ndd) running time and O log k)- approximation. More precisely, Deshpande and Rademacher [13] provided a deterministtc (k + 1)- approximation with O(dn² nk) running time. To improve the running time, Guruswami and Sinop [19 proposed an dk)) time randomized algorithm with (A + 1)-approximation. Additionally, there are many bi-criteria algorithms that relax the number of selected columns. Volume sampling methods have been widely applied to the CSS problem. Deshpande and Vempala [15] utilized these methods to achieve a PTAS, selecting Okk/2² + x-2 log k) columns. Boutsidis et al. proposed linear-time algorithm with a (1 + a-approximation, requiring Ok:/e) columns selected. Guruswami and Sinop [9] developed a deterministic algorithm that also achieves (1 -)aapproximation with
Okk/e) columns selected. Civril and Magdon-Ismail [0] gave improved bounds for obtaining a
PTAS using k-leverage score sampling and SVD, by selecting Ō(k log k/e²) 3 columns. Altschuler
et al. I developed distributed greedy algorithm for the objective |SStAA|? Wang and Singh (2 studied the CSS problem in the missing-data case. Several bi-criteria algorithms have been proposed for the CSS problems with E norm [12 [1 25 g. In both offline and online settings, Woodruff and Yasuda 29 provided several bi-criteria algorithms for the CSS problem with the lp norm.
2 Preliminaries
For any positive integer nt, let [n]] denote the set (I, Given a matrix A E Raxd let As be the element in the i-th row and the j-th column of A, and define the Frobenius norm of A as
²Ò(n) denotes the asymptotic complexity, ignoring polylogarithmic factors, iec. terms of the form poly(log n).
3

---

Algorithm LSCSS
Input: a matrix A E Rx an integer k, and the number of iterations T Output: submatrix consisting of k columns from A
Initialize I E A, A.
2: for 1, do
3: for - 2........ k do
4: Sample column index i [d] with probability = = ||,/1///
5: Update I = IU {i) and F A AzA
6: end for
7: if equal to then d zero matrix D, and each diagonal entry Da (52 (nd (++) 9: Compute A +- A D and set I = 0.
1A~AA A=1A
8: Initialize
10: end if
11: end for
12: Compute = + D and set AG.
13: for < 1.2..... do
1-LS(A',k,5 15: end for
14:
16: Let Z be the set of column indices of S.
return Az.
Algorithm LS
Input: a matrix A' E gnxd, integer k, and a matrix S E goxk Output: a submatrix consisting of k columns from A'
1: Compute the residual matrix F = A' -SS A'.
2: Sample set of 10k column indices from A', where each column index picked with probability E, 1 | /////11........
3: Uniformly sample an index p E C.
4: Let Z be the set of the columns indices of S in A'.
5: if there exists an index E I such that f(A', A' AI)to)U(1)) < () then
6: Find an index E I that minimizes f(4', A A(()((())
7: I = T\gg) (p).
8: end if
9: return Az.
|| - A2,. Denote A, as the j-th column of A, and A; as the i-th row of A. Let A be the transpose of A and A be the Moore-Penrose inverse of A. Given let be the set of column indices from A, and let Az denote the n x [Z] submatrix of consisting of the columns corresponding
d matrix A.
the indices in I. For matrix A, the linear span of its column vectors is denoted as span (A). For any two n x d matrices A and B, ||A]][ S |||||]]]] [BI22 and ||AB|| S |||l||/ B|| Given any matrix E Ruxd the singular value decomposition (SVD) of can be written as A Σ J,u,V," where 01 ... on 0 are the singular values. (ui....,u,, "n R are the left singular vectors, and {ei,.... va) Rd are the right singular vectors. Denote rank(A) A) be the rank of a matrix A, which is the number of non-zero singular values of A. Moreover, we denote A₁ Σ Frobenius norm. The spectral norm of A, denoted by ||A]],, is defined as the largest singular value of A. i.e., ||A|| maax (A). Given solution 5 to the CSS problem on matrix A, define the residual error of S f(A, S) = | SSt
o,u.vo
the best rank-k approximation A under the
Linear Time Local Search Algorithm for CSS Problem
In this section, we propose local search approximation algorithm for solving the CSS problem, called LSCSS, which maintains running time lincar in both and d. Directly applying single-swap

---

local search to solve the CSS problem results in an ("ndk?") running time by enumerating all possible swap pairs. Thus, is challenging to apply the local search method to solve the CSS problem while maintaining a linear dependence on both n and d in the running time. To avoid O(dd k²) running time in each local search step, we propose a two-step mixed sampling method to reduce the running time from (nd? to (nddk²). Although the sampling method reduces the running time by directly using the single-swap local search, analyzing the bound of improvement on the residual error after swaps is a difficult task. To provide a theoretical analysis for the local search step, we propose a matched swap pair construction method to bound the improvement on the residual error during swaps. By carefully analyzing the improvement, we show that our proposed algorithm achieves 53 + 1) -p-aprooximation with O(nck* log k) running time. The detailed algorithm for the CSS problem is given in Algorithm !
The LSCSS algorithm mainly comprises local search and two-stage mixed sampling components. The high-level idea behind our proposed local search is to identify a swap pair that minimizes the residual error in each iteration. The swap pair consists of a column from the input matrix to swap in and column from the current solution to swap out. By repeating this process, the algorithm produces an updated solution with better quality. Moreover, the two-stage mixed sampling method involves two steps for obtaining candidate column from the input matrix. Firstly, a set of column indices is constructed by sampling each column with probability proportional to its residual error for the current solution. Then, a column is uniformly selected from the set of candidate indices as the final column to swap in. To ensure that the input matrix for the local search process is full rank, we construct new matrix A' by adding small perturbation matrix D to the original matrix A during the initialization, where D is full-rank and has non-zero values only on its diagonal. The full-rank property of A' is used in subsequent analysis.
The LSCSS algorithm begins by obtaining an initial solution S with exactly columns and con- structing a full-rank matrix A' during the initialization (steps 1-12 of Algorithm [ which achieves (k + -a-approxii solution on A'. We start by initializing an index set I and setting the matrix E = A. A new column index is added to Z by sampling each column index i from [d] with probability proportional to p; = || [E 1/.1/// EI? Then, E' is updated as E = A AI A. Repeating this process k times, we obtain an initial solution S = Az. To construct a full-rank matrix, we construct an n x d zero matrix D and compute the parameter a = || S5t Allx> min (n. dl + 1)!) 1/22 using the initial solution S and A. Each diagonal entry D;; is set to a. Since rank(A + D) = rank D), we construct the full-rank matrix A' by adding the full-rank matrix D to the input matrix A. To solve
the CSS problem on A', we execute steps 3-6 of Algorithm to obtain the solution S = Az. The requires O(ddk2) time.
detailed process described in steps 1-12 of Algorithm [
The local search performed in steps 13-15 of Algorithm D plays a crucial role in LSCSS, involving two main steps. Firstly, we compute the matrix E = A' SS A' for the current solution S. Then, a set C' of 10k column indices is constructed by sampling each column index i from [d] with probability p; || ET Next, a column index p uniformly selected from C, referred as the "swap- in" column index. Let I denote the set of column indices of S in A'. Subsequently, if there exists an index 9 E I such that f(A', AZ ( < fAA,, S), we choose q as the "swap-out" column index and update the set of indices to = I {q} U {p). Finally, Algorithme 2 returns the solution S = A/- After repeating this process T = O log k) times, Algorithm| returns the final solution S for the input matrix A.
In the following, we explain in more detail how our proposed local search algorithm achieves 53(k: + -pparoooximtto for the original matrix A. Given an initial solution, the main idea for residual error
analyzing the approximation ratio of our algorithm is to bound the improvement during the swaps in the local search step. To achieve this bound, we propose a matched swap pair construction method that guarantees (Lemma and I Lemma(3.7 3.7). By carefully analyzing the improvement, we show that with constant probability the approximation loss of the current solution can be reduced by multiplicative factor of - ((1/k) in each iteration of the local search algorithm (Lemma 3.8). This implies that after O log k) iterations, we have || - SssssssA A I 26(k: + 1)]|A' - A (Theorem 3.9). Finally, by amalyzing the change in the residual error caused by removing matrix D from A', we obtain ||A' SST A' 13= < 53(k + A)][A - A& | in expectation (Lemma 3.1
improvement in the current solution by swapping one column
We assume that the matrix A has been normalized such that
|| = 1/4. Otherwise, we can Next, we consider single iteration of Algorithm normalize each element Aij in A as Aij = 2|
Ag
5

---

We assume that the current solution has a high residual error (larger than 25(k + 1) - before executing Algorithm on A'. Otherwise, the initial solution a 25(k + 1) approximation for the input matrix A'.
Let S {s.,...,,8)) 8 be the optimal solution with exactly h selected for A', and let S {si...., S be the current solution. We define of (A,, S S,,,,,s S.)*) arg min.es [(A', 5 Ms* (U{s}) {s}) is mini-
as mapping function that finds from S such that the residual error f(A', , S {s mized. Thus, we say that s* is captured by , S, 8*). Each column 8 E S is captured by exactly one column from S. Let denote the of column indices of S in matrix A'. We denote as the set of columns indices in S that do not capture any optimal columns. We denote H as the set of indices where each column in S captures exactly one optimal column.
The main idea behind the matched swap pair construction method is to analyze the change in residual caused by swapping index from set H (or L.) with index from sampled column, using two-step mixed sampling approach for the current solution S. For the column 8h (where h E H) in S, Sh. captures exactly the column s) of the optimal solution S*, serving as the candidate column for s/. If the residual eтrоr of swapping
to replace 5j is large, we prove that with constant probability, sampling new column can reduce the residual error and update sh. Similarly, for the column (where E L) in S, does not match any optimal column. We also show that, with constant probability, sampling a column from the imput matrix A' can reduce the residual error for columns in set L. To analyze the improvement in residual error during swaps, we focus on single swap process, evaluating both the increase in residual error from removing column from S and the decrease in residual error from inserting new column. We give the following definition to measure the change resulting from removing column.
Definition 3.1. Let A' RRaxd be a full-rank matrix, and let S be a solution on A'. Let I be the set of column indices of S. The change in residual error by removing the column i from I is defined as
(, ((m))))))) ((A,
To bound S,',,,IV, of solution S on the matrix A', we provide the theoretical guarantee in the following lemma. (Detailed proof of Lemma i.2 given in Appendix A.1)
Lemma 3.2. Let A' Raxd be a full-rank matrix, and let S be solution on A'. Let I be the of the column indices in S. For E I, we have
S S1A''
To further analyze the bound on 7 (i))) we decompose the projection matrix A'7 1.4' and show that the expected upper bound 7(A', (,I((() is proportional to ||||| (Detailed proof of Lemma 3.3 given in Appendix A.
d be full-rank matrix, be a positive integer, and let be the set of column indices of S for the CSS problem on A'. In expectation, the following inequality holds
Lemma 3.3. Let A' E x
1.2 d2 11
A''
In the following, we theoretically bound the residual error resulting from adding a candidate column index p the set I of column indices in S, where p chosen using the two-step mixed sampling method. (Detailed proof of Lemma 3.4 given Appendix A.I)
Lemma 3.4. Let A' E Raxd be a full-rank matrix, & be a positive integer, and let be a solution with the set I of column indices in S. Let E A' SS A'. The column index p is obtained by In expectation, the following inequality holds
executing steps 2-3 of Algorithm 2
1 f(A', f(A fe(AA' + 10 1(4,
where fa(A', opt) denotes the best rank-k solution.
According to the aforementioned mapping function Φ(-), we obtain the subset H from the set I of column indices and the set H.H. By using the matched swap pair construction method, there two cases for the residual error of the current solution:

---

1. For the set H, where ΣMEH f , {
21 Eiez f(A', Av3))
50
29 2. For the set R = I,H, where EtER , A'zur)) 2 50 Eier , A22,1))
By Lemma 3.2 and Lemma 3.4 we define the good columns s; for i E I with respect to S as follows.
Definition 3.5. Let A' E R be a full-rank matrix, and let be a positive integer. Let S be the optimal solution with exactly k columns selected, and let I" be the set of column indices in St. Let be any solution with exactly k columns selected, and let I be the set of column indices in S. A column index i I is called good if
f(A', (AA1,))))))))))))))))))))))))A - (5)) -(A', (-) (I (PH())))
11 ((AA'AA' + 1 ((A)
100k J (A',S),
where 1" II" is the column index mapped from i I by the function o()). and p is column index obtained by executing steps 2-3 of Algorithm [
Definition 3.5 estimmtess the gain from replacing the column 8y with column obtained using the two-step sampling method. Next, we argue that if case (1) happens, the sum of residual errors for the good columns large. (Detailed proof of Lemma 3.6 is given in Appendix A.1)
Lemma 3.6. Let A' E Raxd be a full-rank matrix, k be positive integer, and let S be the solution to the CSS problem on A' Let I be the set of column indices in S. If EnEn f(A,, A'z(()) Z 21 Eiez (A', A' ((1)) and f(A',
25(k- + (A', op), we have
Σ
S(A', A'IMN)) Z 125
1 S(A',
KEH.b good
Since R I I,H, it holds that I. S R. The index set contains two subsets: T. and R L,, where the indices in L do not capture any optimal columns according to the mapping function @(-) and the indices in R''L capture at least two columns. Similar to case (1), we argue that case (2) occurs, the sum of residual errors for the good columns is large. (Detailed proof of Lemma 3.7 is given in Appendix A.1)
Lemma 3.7. Let A' E Raax be a full-rant matrix, & be a positive integer, and let S be a solution for the CSS problem on matrix A'. Let I be the set of column indices in S. If ErER [AA, , A' A'Ty(T)) 2 29/50 EiEz [(A', , A' (A1) and [(A', 2 25(k + (A opl), we have
Σ
A'''A'' N 125 iET
E(AA)
rER. is good
In the following, we prove that if the residual error of the current solution is larger than 25(k - (A', opt), each local search step reduces the residual error by a factor of 1 ( with constant probability. (Detailed proof of Lemma 3.8 is given in Appendix A.1)
Lemma 3.8. Let A' E Rudd and S E Rkxdd be the input matrices for Algorithm where is positive integer and S is the solution of the CSS problem on A'. Suppose that J {(A, Z 25 + 1)- [A''', opt). Then, with probability at least 1/1375, Aggorithm@]eet returns a new solution S' with
S(A',S") < (1-11(100k))(("'
Subsequently, we prove that the LSCSS algorithm achieves 26(k -aapproxiination for A' after O log k) iterations.
Theorem 3.9. Let A' E BRdd
d be the input matrix obtained in step 12 of Algorithm 7 let k be
positive integer, and let be the solution returned after executing Algorithm (kk log k) times. Then, it holds that
E||A'- - sestsstAAs A'1?2 < 26(k + 1)][
ALllE
where Ale is the best rank-k approximation of A' for the CSS problem. The running time of Algorithm i is Orrdk" log k).
7

---

Proof. Let S denote the submatrix consisting of k columns obtained in step 12 of Algorithm For the initial solution S. Deshpande and Vempala [1] provide an approximation ratio of (I: + 1)! Before executing steps 13-15 of Algorithm the residual error of the initial solution $ is larger than 25(k + 1)]l - A/.l According to Lemma 3.8 with probability 1/1375, we can reduce the residual error by multiplicative factor of (1 1/000).
Let T Ok2 log kt. We define random process P with initial residual error || - S of the solution 8 such that for T' iterations of Algorithm 2 reduces the value of || A'11 by
at least (1 1 with probability 1/1375, and it increases the final value of || A by
25 1)1l - A/e p
It is obvious that [|||AA SSI A' = E[I|4' S$ A } Then, we have
1374
(1
[PP 25((k + 1)IIA' - ALllE + 1|A' SSA--SSTAV Σ
1375
1375
100k)
1=0
137500k log +k+)
(1- 1
<I - SiS A'
+ 25 + 1) - A&ll?
137500k
x | S8t 1
+ 25 + 1)]14' - 1/
(k + 1)!
This implies that [B[[AA' - SSt A'12181 <
-S + 25(k + 1)II - A/ (6+1))
Thus, we obtain
E E|||A' - - A'11/]
Σ
EIIAAA Sst ((P))))PP(S)
$
||A' SASSSAAA 1 (k+ 1)!
Σ Pr(()
+ 25 + 1)]1 - 1/
8
ElIlA' 351 A'
+ 25(k + 1)1AA' -2212
(k: + 1)!
Since I|A' - 551 1 S (k + 1)![[A' A/,1% in expectation, we have B|I[A' SSt ASA.A1 S 26(k + 1)11 11E.
Running Time Analysis. In LSCSS algorithm, the process of constructing the initial solution in the steps 2-11 of Algorithm 1 takes O(udk~) time. In order obtain O(k: 1)-approximate solution, Algorithm requires ( log k) iterations. In each iteration, computing the residual matrix requires O(ndk) time. The steps 4-8 of Algorithm require O(ddk2) time to recalculate the residual error. Therefore, the overall running time of Algorithm is OOddk* log k))
In the following, we analyze the change in residual error caused by replacing the input matrix A with A' = A + D. which leads to the final solution of Algorithm acchiving a 53(k: + -)aappooximation (Detailed proof of Lemma i.10 given in Appendix A.1)
Lemma 3.10. Let A E iaa be an input matrix, and let k be a positive integer. Define D as an x d matrix with elements
||A-S AlLF
ifi=j otherwise
Dij
where S₁ is obtained by executing the first round of steps 3-6 in Algorithm 1 Let A' = A + D. The
solution S2 returned by executing Algorithm 2 for = O(k² log k) iterations satisfies
ElIAA - A.StA'11 < 53 + 1)114 - Ax1
where As is the best rank-k approximation for A.
8

---

Experiments
In this section, we compare our algorithm for the CSS problem with the previous ones. For hardware, all the experiments are conducted on a machine with 72 Intel Xeon Gold 6230 CPUs and 2TB memory.
Datasets. In this paper, we evaluate the performance of our algorithms on total of 22 real-world datasets. In previous studies 2X] D. the CSS problem typically involves datasets with no more than
100,000 rows and 20,000 columns. We include the 14 smaller datasets listed in Table (Appendix A.2). To extend the evaluation to larger datasets, we include additional datasets detailed in Table 2 Six datasets contain between 40,000 and 480,000 columns, and two contain 400,000 and 8 million rows, respectively. All datasets can be found on the website
Algorithms and parameters. In our experimental evaluation, we consider the following five distinct algorithms:
TwoStage. This is a two-stage algorithm from S that combines leverage score sampling and rank-revealing QR factorization.
Greedy. This is an algorithm in 16 1. which uses greedy algorithm to generate solution.
VolumeSampling. This is an algorithm in 13 which uses volume sampling method.
ILS. This is algorithm in 23 which uses heuristic local search method.
LSCSS. This is our algorithm given in Algorithm| which uses the two-step mixed sampling and local search methods.
Methodology We use the error ratio to evaluate the effectiveness of various algorithms, defined
in [23]. The error ratio is given by the formula || Sst A|l /1 - A 1 where it quantifies the discrepancy between the selected columns and the optimal rank-k matrix approximation. A smaller error ratio indicates better algorithm performance. Following [23], we test the TwoStage, VolumeSampling, ILS, and LSCSS algorithms each dataset 10 times to calculate the average ratio and running time. Since the Greedy algorithm is deterministic, it is tested only once per dataset.
Table 2: Summary of the datasets
Datasets
Instances
Features
Condition Monitoring of Hydraulic Systems(CMHSS)
2205
43680
Farm Ads (FAds)
4143
54877
Electricity Load Diagrams (ELD)
370
140256
Gas
180
150000
YaleB
16380
307200
Twin Gas Sensor Arrays (TGas)
640
480000
Epsilon
400000
2000
Mnist8m
8000000
784
Experimental setup. For the CSS problem with the Frobenius norm, we run the TwoStage, Greedy, ILS, and LSCSS algorithms on both the 8 large datasets and 14 small datasets, providing the average results for each method. The ILS and our LSCSS algorithm are based on local search method. For fair comparison, we set the number of iterations to be 2k for ILS and LSCSS. Since the VolumeSampling requires (dkn' n) runtime and (n + d?) memory, cannot handle the large datasets because the algorithm requires more than 48 hours of runtime and over 2TB of memory. However, the other four algorithms generally produce solution within hours and with less than 2TB of memory. Thus, we only include VolumeSSapling in the comparison on the 14 smaller datasets and exclude its results from Tables 3 and
https://archive. ics http:/hhhheee..ec........eeaaaar
cl. cam http://wwwwpp../cc//c/c///////t/

---

Table 3: Comparison results on running time for varying k on datasets. If an algorithm fails to output a solution within 48 hours, the running time set as ">48h". If memory usage exceeds 2TB, the running time is set as "OOM" (Out of Memory).
TwoStage
Greedy
IL.
TwoSiage
Greedy
LSCSS
$52.91
493.49
18.45
2,82
228.66
127.31
143.78
3.40
716.27
54.59
226.53
248.89
498,29
10.58
15
647.34
1045.83
122.49
13.39
219.35
369.95
1032.53
17.65
847.87
1362.44
219.43
30.45
221.97
495.09
1744.18
18.27
CMHS
25
1150.13
1679.30
331.24
43.27
FAds
229.24
624.69
2659.60
22.29
1249.27
1955.13
476.28
$2.82
232.34
749,99
3789.49
22.76
1364.90
2598.43
1321.73
62.36
291.93
1265.93
10363.85
36,04
100
1552.57
7263 06
4457.66
108.98
100
539.00
2738.69
44037 65
95.67
434.60
245.14
25.28
822.75
312.98
154,37
17.15
10 $39.22
436.11
50.98
3.47
10
1205 25
617.40
539.61
30.28
1686.43
960,75
1202.76
ELD
20
940.42
1598.41
148.07
13.93
TGas
20
2295 88
1335.77
2095.39
49.90
1237.54
1710.38
236.48
22.98
2976.99
1767 18
3349.04
61.36
30 1536.68
2307.40
291.32
35,03
30
3818. 48
2230.84
4760.69
77.93
50
1738.76
3649.70
727.45
66.27
7098.36
4419.23
6772.58
114.23
100
2384.16
5946.40
2696,24
89.94
100
9186.20
12439.81
9352.80
243.89
5
404.32
426.89
56.71
5,83
OOM
17214.54
2190..7
175.24
148.36
OOM
21210.58
9855,42
501.67
15
858.04
1162.98
202.17
19.30
15
OOM
3-8hh
12754.29
793.47
428.71
348h
23694.02
1082.21
YaleB
25
1741.95
1977.13
1623,66
130.11
25
OOM
248h
35259.86 86
1756.18
2237.17
4858.71
2-48h
50
4944.07
7852.03
7888.39
386.15
50
OOM
248h
4-48h
7127.35
100
20955.39
12703.14
12190.91
850.01
100
OOM
>48h
2-48h
13865.08
18122.53
5564.12
3255,38
483,02
8916.54
1067.48
283.22
24.85
22216.92
34765.28
21587.49 .49
2991.22
9221.10
2111.57
979.81
38,71
48h
248h
53973.46
3420.13
9426.96
3193.27
2093.51
69.00
Mnist8m
20
25
4-hh
4-hh
248h
3-8h
4-8h
-48h
8485,13
6609. 00
Epsilon
20
10330.94
10928.29 29
4332.60
5570.65
3645.36
5564,
102.46
163.25
30
2-8hh
348h
-48h
9495.18
30
11371.33
6861.29
7727.87
352.39
13236.29
13839,09
12451.47
16939.53
562.20
100
3-8hh
2-48h
3-88h
16910.19
100
15334.64
29352.57
18239.98
1102,80
Results for the CSS problem. Table shows the comparison of rumning time for varying values of k, where the time is measured by seconds. LSCSS is at least 10 times faster than other algorithms across all datasets and at least 15 times faster than the TwoStage and Greedy algorithms. Our algorithm successfully outputs a feasible solution within 5 hours on all datasets, whereas other algorithms fail do so within 48 hours need more than 2TB memory. The comparison of error ratios, reported as ssad with the best results highlighted in bold, is presented in Table in the Appendix A.2 The LSCSS algorithm achieves the best ratios almost all datasets.
Morcover, we compare the runming time and error ratio of five algorithms with varying values on 14 small datasets (Appendix A..)). The experimental results show that the LSCSS algorithm outper- forms other algorithms in terms quality and least times faster than Greedy, VolumeSampling and ILS algorithms all small datasets.
5 Conclusion
In this paper, we propose linear-time approximation algorithm for the CSS problem using local search and two-step mixed sampling methods. Experimental results demonstrate that our framework outperforms previous algorithms for solving the CSS problem with exactly & columns selected. An interesting future direction is how to design multi-swap local search approximation algorithms for handling the CSS problem.
Acknowledgments
This work was supported by National Natural Science Foundation of China (62432016, 62172446), Open Project of Xiangjiang Laboratory (22XJ02002), and Central South University Research Pro- gramme of Advanced Interdisciplinary Studies (2023QYJC023), This work was also carried out part using computing resources at the High Performance Computing Center of Central South University.
10

---

References
[1] Jason M. Altschuler, Aditya Bhaskara, Gang Fu, Vahab S. Mirrokni, Afshin Rostamizadeh, and Morteza Zadimoghaddam. Greedy column subset selection: New bounds and distributed algorithms. In Proceedings of the 33rd International Conference on Machine Learning, pages 2539-2548, 2016.
[2] Hiromasa Arai, Crystal Maung, and Haim Schweitzer. Optimal column subset selection by A-star search. In Proceedings of the 29th AAAI Conference Artificial Intelligence, pages 1079-1085, 2015.
[3] Christian H Bischof and Gregorio Quintana-Orti. Computing rank-revealing QR factorizations of dense matrices. ACM Transactions on Mathematical Software, 24(2)222-253,, 1998.
[4] Christos Boutsidis, Petros Drineas, and Malik Magdon-Ismail, Near optimal column based matrix reconstruction. In Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science, pages 305-3144 2011.
[5] Christos Boutsidis, Michael W Mahoney, and Petros Drineas. An improved approximation algorithm for the column subset selection problem. In Proceedings of the 20th Annual ACM- SIAM Symposium Discrete Algorithms, pages 968-977, 2009.
[6] Tony F Chan and Per Christian Hansen, Some applications of the rank revealing QR factorization. SIAM Journal on Scientific and Statistical Computing, 13(3):727-741, 1992.
[7] Shivkumar Chandrasekaran and Ilse CF Ipsen. On rank-revealing factorisations. SIAM Journal on Matrix Analysis and Applications, 15(2):592-622, 1994.
[8] Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, and David P Woodruff. Algorithms for Êp low-rank approximation. In Proceedings of the 34th International Conference on Machine Learning, pages 806-814, 2017.
[9] Ali Civril. Column subset selection problem is UG-Hard. Journal of Computer and System Sciences, 80(4):849-88) 889,,8599000 2014.
[10] Ali Civril and Malik Magdon-Ismail. Column subset selection via sparse approximation of SVD. Theoretical Computer Science, 421:1-14, 2012.
[11] Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in input sparsity time. In Proceedings of the 45th Annual ACM SIGACT Symposium Theory of Computing, pages 81-90, 2013.
[12] Chen Dan, Hong Wang, Hongyang Zhang, Yuchen Zhou, and Pradeep Ravikumar. Optimal analysis subset-selection based é, low-rank approximation. In Proceedings of the 33rd Conference Neural Information Processing Systems, pages 2541-2552, 2019.
[13] Amit Deshpande and Luis Rademacher. Efficient volume sampling for row/column subset selection. In Proceedings of the 51 IEEE Annual Symposium on Foundations of Computer Science, pages 329-338, 2010.
[14] Amit Deshpande, Luis Rademacher, Santosh S Vempala, and Grant Wang. Matrix approximation and projective clustering via volume sampling. Theory of Computing, 2(1):225-247) 2006.
[15] Amit Deshpande and Santosh Vempala. Adaptive sampling and fast low-rank matrix approxi- mation. In Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 292-303. 2006.
[16] Ahmed K Farahat, Ali Ghodsi, and Mohamed S Kamel. An efficient greedy method for unsuperised feature selection. In Proceedings of the 11th IEEE International Conference on Data Mining, pages 161-170, 2011.
[17] Alan Frieze, Ravi Kannan, and Santosh Vempala. Fast monte-carlo algorithms for finding low-rank approximations, Journal of the ACM, 1044,,,, 2004.
11

---

[18]
Ming Gu and Stanley C Eisenstat. Efficient algorithms for computing a strong rank-revealing QR factorization. SIAM Journal on Scientific Computing, 17(4):848-88) 869, 1996.
[19] Venkatesan Guruswami and Ali Kemal Sinop. Optimal column-based low-rank matrix recon- struction. In Proceedings of the 23rd Annual ACM-SIAM Symposium Discrete Algorithms, pages 1207-1214, 2012.
[20] Nathan Halko, Per-Gunna Martinsson, and Joel A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, 53(2):117-288, 2011.
[21] Arvind V Mahankali and David P Woodruff. Optimal & column subset selection and a fast PTAS for low rank approximation. In Proceedings of the 32nd Annual Symposium on Discrete Algorithms, pages (60-578,20 2021.
[22] Bruno Ordozgoiti, Sandra Gómez Canaval, and Alberto Mozo. A fast iterative algorithm for improved unsupervised feature selection. In Proceedings of the 16th IEEE International Conference Data Mining, pages 390-399, 2016.
[23] Bruno Ordozgoiti, Sandra Gómez Canaval, and Alberto Mozo. Iterative column subset selection. Knowledge and Information Systems, 54(1):65-99) 2018.
[24] Gregorio Quintana-Orti, Xiaobai Sun, and Christian H Bischof. A blas-3 version of the QR factorization with column pivoting. SIAM Journal Scientific Computing, 1965)1148-1144, 1998.
[25] Zhao Song, David P Woodruff, and Peilin Zhong. Low rank approximation with entrywise f--norm error. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 688-701, 2017.
[26] Zhao Song, David P. Woodruff, and Peilin Zhong, Average case column subset selection for entrywise -nom loss. In Proceedings of the 33rd Annual Conference on Neural Information Processing Systems, pages
2019.
[27] Zhao Song, David P. Woodruff, and Peilin Zhong. Towards a zero-one law for column subset selection. In Proceedings of the 33rd Annual Conference on Neural Information Processing Systems, pages 6120-6131, 2019.
[28] Yining Wang and Aarti Singh. Column subset selection with missing data via active sampling. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, pages
2015.
[29] David P. Woodruff and Taisuke Yasuda. New subset selection algorithms for low rank approxi- mation: Offline and online. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1802-1813, 2023.
12

---

A Appendix supplemental material
A.1 Missing Proofs
Lemma 3.2. Let A' E [Rnx be full-rank matrix, and let S be solution on A'. Let I be the set of column indices in S. For we have
7(A', & | A'
Proof. Given a solution S, we demonstrate an equivalent transformation to simplify the expression of the residual error for S:
|| - -5' 1 -r((A'' - SS1 (A (A)
=tr(A' - SS A' A'' + A' (sst) SSTA')
=tr(A' - SST A' +A' ASTA'
=Ir(A' A') tr(A' SSTAY
=tr(A' AT) - tr(A" (SSt) SS
=tr(A' A) ||SSI A/l
where the third equality follows from S Sst St and (SSi)T = SS By the above equality, have
= -IA'' S2((1) St (1) A' - -IIA' Sy
= -1SS-StAA' (15
S &1StStA''1EE
Lemma 3.3. Let A' E B be a full-rank matrix, be a positive integer. and let be the set of column indices of S for the CSS problem on A' In expectation, the following inequality holds:
22 L A
A A'''''''''
Proof. We begin by seeking to bound the Frobenius norm of the matrix product A' Using submultiplicative property of Frobenius norm, we get
I'''Z' < 1A'ZA'L11 IA
Next, by the norm inequality, we have
1'' S 114111 1|A'
Since the matrix A is full rank, which ensured by steps 7-10 of Algorithm Therefore, ||A4 can be reformulated as the maximum eigenvalue of A' A'z. Specifically, we have
I
Amaxx (A' A'z))
Amin (A' A'T)
Substituting this into ||A'z A'112 we get
| |A'=A' (A |'=11 ||
Since the maximum eigenvalue Amax (A' A'z) is bounded above by || obtain
||'' 1 4 < A'zal ||
13

---

Finally, by the expectation E [|]] = 31144111 and |||| = 1. we have
1A''
||
k2
(II + D1
22
k2
(1) 21)
min(2.d)
1.2
के
(211
+2
Σ
22
1.2
|| 1--S5tAA A y2
(211/112
m2min d} 52 min(n n, d) + 1)!
d²
k²
||A11?
(211
d
52(k: + 1)!
1.2
$
(411
de
1.2
d²
where the first equality results from A' = A+ D, and the second inequality follows from the property || + B1 < + for any two matrices A, B E Raxd
Combining the above inequalities, we conclude that
1.2 || 1A''A' A d2 ||
Lemma 3.4. Let A' Rund be full-rank matrix, k be a positive integer, and let be a solution with the set I of column indices in S. Let E = A' SSt A'. The column index p is obtained by In expectation, the the following inequality holds
executing steps 2-3 of Algorithm 2
f(A', (ZuR)) S fulA', opt) + - f(A'
10
where fA(A', opt) denotes the best rank-k solution.
Proof. Let 1 be the probability that each column index j E [d] is sampled. To bound TE
f(A, Aru())) we define random variable x for E [r], E [d]. and / E [z] as follows:
Bi E.y with probability Py- Pj
We denote X; as the random variable that is randomly picked from the C X?....... X.). Therefore, the expected value of X; is given by
E(X))
Pr(I-th picked) (x!)
B(X!)
d
dij E.j
pj
14

---

Uig Eig
j=1
Exi
Evi,
where the second equality follows from the linearity of expectation, and the last second equality results from the linear combination of U/ and E.
Let w, = (SSt A)u; + X; for i E [r]. Therefore, we have B(w;) 0,
Thus, have the equality w; 0304 X; Eug. By calculating its second central moment, we obtain
B(I oruel (2) B(1IX; Ev:l2)
=B(11xa113) -)(())) Evg + EEvll
=.(13x,113) - 11uui112
Next, we seek to bound ((())x,11).
B(I[X,,1)) =
E
11
Pr(I-th is picked) x2
(Pr(I-th is picked) [E( (2) +
Pr(I1-hh and 12-th are picked) B(x x//)
1=1
1sh
2
B(II))
12)
B(X X/2)
2
22
1sh<las
1
B(I 12)
|Ev;
22
The term of 3 Σ Eish < E(X! x = X/e Therefore, we conclude that
2-
Evy follows from the independence of x/: and
E(Ilu; ouu, (22) 2
Era l2-
1=1
For the first term in the above equation, we have
E
E
P
P
L
E 2
1
= ||||
Feggl
| 1 |
< |
| 12
Combining the above inequality, we have
B(Il: [1ll;-o,u1333 < Ev,
15

---

Let = ww/oo for i E [k] and let matrix F EEi= yuuu )A' Therefore, we have
11A AA'Tu()) A Iulpp 1 || Fll By decomposing F along the right singular vectors
(u), we have:
B(IIA' A' A'zu(s) A Zulo
Zu6o) 1lB) S E(IIA' -FI1
E(I - F)
B(llouu wall))
Σ of
i=k+1
S (A' opt) + k J A'z),
where the last second inequality uses that Sa(A',, opt) Ei=kti o7.
Setting the = = 10k, we obtain that
1 A'zupt)) s fa(A', opt) To (A),
Lemma 3.6. Let E Raxd be a full-rank matrix, be a positive integer, and let be the solution the CSS problem on A'. Let I be the set of column indices in S. 50 EnEH f(A', A' ('1A)) Z 21 EiEz f(A', A' (0)) and f(A', S) 25(k + (A', opt), we have
Σ
f(A', ((T))) N
1
Σ 1E
A(A A A'T(A)
125
KEH,b good
Proof. First, we prove that the residual error non-incre.sing. Let Sy. be subset of k columns from A'. Let E A' be a column not in Sk. and define Sk+1 = S U {p). The residual error function is defined as:
f(A', || - sst A 2 = || ||ss A'
Our goal is to show that f(A', 55+1) - St). i.e., the residual error is non-increasing when a column is added Sg.
Since || P is constant, we only need to prove that |S 4'1 2 || For any column u of A', denote
(uu) = ||S++ St k+1 u12 - 11
If p E span(S:), then span(S = span(S:). and thus A(u) = O. Otherwise, if $ span(Ss), define the orthogonal component of p with respect to span(S²) as
P1 Pp-Say SS.S.P
and normalize it as p' Tpi
p
For any u, the projection onto span(S*+1) is S SuStu + (u,"')'' where pu, denotes the inner product. Therefore, [| | + ((, holds, implying that (uu) = Ku, 12 2 0. Summing over all columns of A', we obtain || A'l1?
|| A = -. A (w) 2 0. Thus, the residual error function satisfies
f(A', Sk+1) | || A'I < || 1S -(AA,
This proves that adding column S& does not increase the residual error.
By Lemma
3.2 we have
7(A', A' Zutpp) IU IU A''',
S Al
I A'lla
16

---

Similarly, we have
7(A', - "'''A'''''' f(A', & |
Thus, by Lemma
3.3
we obtain r'A', zu(p) IU ((A (k+1)> |
||
2 -
A where & E H.
de
Next, we have Σnen have
2
21 50
Eier [(A A''''''''', A'z,0)) By Definition 3.5 and Lemma 3.2
E kEH, is not good
f(A', & Σ T(A', + T(A, A' (n), IU
NEW
11k
1
1 [(A',S)
(J(A', A' A'I-V(o-))) + (A',,
10
10
100
2h(A 1)2
11k h22
||A +
|| + f(A' 8*))
10 de
11k + ((A',S)
100
31k-
11k
11k [(A',S)
|| +
"(A', +
10d
10
100
31
|1 + 11h: + +1)
[x(AA, opt) + 11k + 1
S(A',8)
10d2
10
100
11k(k: + 11
11k +
fa +
,(A',S)
10
100
3113
||A||
fo(AA', opt)
10d f(At.opt)
11k((k +
11k +
31k3
Ja (A
8() + 5d22 SA opl),
10
100
where the fourth inequality follows from the fact that S is the optimal solution with exactly columns selected, and f (k (A',
Using (AA 2 25 + (A', opt) and the con-increasing property of residual error, we obtain that
103k
Σ
A'A', A' A'zmN))
S(A',S).
250
hE good
By ky( S Eiez ('',A'''A AzTA)).
Σ
f(A', A'z(1)))=
<
103
Σ
250
he not good
IEI
Thus, have
Σ
f(A', A'A44,'2)))))
A(AA'A''no
125
KEH,h is good
1E
Lemma 3.7. Let A' &Ra be a full-rank matrix. be a positive integer, and let S be a solution for the CSS problem on matrix A', Let I be the set of column indices in S. If If fA', A' 3'z))))) 2 29/50 EieT [(A', (('',,'' A' A'T4)) and [(A', S) 2 25(k: + (Af, opt), we have
Σ
f(A', A' A'rxm)) >
1
Σ TE
f(A', A'r1,))
125
R.Rri good
17

---

Proof. By Lemma
3.3
have =(A', A' Iu(p), IU (1) +7 S (++1)* |
dz ||B
v d²
2(+++) 1
A Pi where E T..
We have EreR R f(A', Arz( 2 29/50 E Liez "'''A''''''''AA A'z Note that |R| S 2| By Definition
3.5 and Lemma 3.2
we have
E
J(A', A' (w1) S 2|4| mellmminTA///// (A + +T A'up)) IU (p)
IEL
rER. good
11k (f(A', A' i ((4,s + 100 f(A',5)
+
10
< Σ (.2,5) A Iu(p); UU (D))(
IEL
11k
10 A'z-(,A'z-100)) 1 ,() + 100 (A',S)
4k(l + 1)2
11k 12
d
||A/11
+
10 T
A | + ((A)
11k + (AA
100
51k(K + 1)²
|A
10d2
11k(k + 1)
11K +1 f(A',S)
fa(A', opt) +
10
100
51A3 ||
10d2 fa(A'', oop)) (A opt)
11k(k + 1)
fu (A', opt) + 11k + 1
[(A',S)
100
1 5d [A' opt) + 11k(k + 1)
31A3
11k +
fu opt) +
,)A
10
100
Using S() 2 25(k + " and the non-increasing property of the residual error (as in the proof of Lemma B.6). we obtain
Σ
143k
,
250
refr is not good
By k)(A S EiEI
we have
Σ
f(A', A' A'z(1)
143
Σ f(A', A'm(1))
250 IE
rER, not good
By combining the previous inequality with the bound 29/50 EieI A'T))) we have Erer, is good A',,,''T()) 125 Eiez
I(A', >
Lemma 3.8. Let A' E Rgd and E Rg be the input matrices for Algorithm where is positive integer and S is the solution to the CSS problem on A'. Suppose that f(A > 25(k + 1)- (A', opt). Then, with probability at least 1/1375, Algorithm 2 returns a new solution S' with f(A', 5') < (1- 1/A
Proof. Let I denote the set of column indices in S. Let S* be the optimal solution with exactly k columns selected, and let I be set of the columns indices in S*. Let p denote the column index obtained by the steps 2-3 of Algorithm 2 Let p" E I' be the column corresponding to index p. as
18

---

determined by the mapping function o(-). According to Lemma good column index is at least
3.6
the probability of sampling
(1/125) Ene good f(A', A' A')()))
1
EiEz [A', A Al))))
125
Let represent an arbitrary good column index. By Lemma 3.4 and the non-increasing property of residual error f()) (as shown the proof Lemma
3.6, we have
)l - fA',', opt) +
10 S))
- f(A', A A(z)))))) 10 (AA'S))
Hence, by the Markov inequality, we obtain
11
1
(' & (((A',A'T'("))) +
10 f(A' ())la e H]
10
11
Combining the above inequalities, the probability that the sampled column index p replaces some good column index h is at least
1
1
1
125
11
1375
Similarly, according to Lemma
3.7 the probability of sampling a good column index at least
(1/125) Ere good A A'z(()))
2 125
ΣIEZ f(A', A'7())
By Lemma 3.4 and the Markov inequality, obtain
11
1 (('', E RJ 17
1
A'zutp) S (S(A' (J'A',A''-'- + 10
10
Thus, the probability that the sampled column index p for some good column index is at least
1
1
1
125
11
1375
By Definition 3.1 we have (AA', A' Dutp), ZU Ma) = A'M,AAoo))))) - A'zu(p)),
and T(A', S, ((g) = f(A', A'zYo)) S).
Now, for the column index g H U R, we can upper bound the updated residual error error (AA, as follows.
f(A',S') ((A",)))((
=S(A', (J(A', - S(A', A' ((14)0(0)))
=S(A', - (J(A''S) - -'A'',, A'Du')))) + f(A', A' A'zu()) - S(A', A' ((QU))))()))
= =f(A', -
-
(I) - -fA'',''uu)))
= =)( - (f(A',I)(g)) - 7(
- -T(A', (()p::((Uup)))()))=d"d...
$((AA' - - ((( - - A'zu() (IU
10 (U((A',''z'' - 14', S)))
11
SAA 100% S)
Thus, by combining the two cases, we obtain that with probability least 1/1375,
S(A', s (1 (/10001))))/(AA'
19

---

Lemma 3.10. Let A E Baxd be an input matrix, and let k. be positive integer. Define D as an d matrix with elements
|A-S
ifi=j
Di
(n.
0,
otherwise
where S1 is obtained by executing the first round of steps 3-6 in Algorithm ! Let A' A + D. The
solution S2 returned by executing Algorithm 2 for = O(k² log k) iterations satisfies
ElllA' - 1 & 53(k: + 1) - Anl
where Ag is the best rank-k approximation for A.
Proof. Let Ag be the best rank-k approximation of A', and Ag be the best rank-k approximation of A. For the initial solution S₁, Deshpande and Vempala [15 provide an approximation ratio of (k+ + 1)!. By Lemma 3.9 we obtain
E|||AA A = 26(A + 1)[lA' A/I
- 26(k + 1)[lA' - Aul
26(k: + 1)]14' A A Axl
52(k + 1) (IIA'- Al1 + +IA Aalli)))
52(k: + 1) (IID11 +
min(n.d)
52(k 1)
||4 As
Σ
D
52 min (n, d3 (k + 1)! )
| - S1S
52(k + 1)
| A min(n,,)) d)
A11
52(k 11)
| A& P
52(k 1)!
||A 1A-AAlli
52(k 1)
(IA [|A-AA113 +
52
53 + 1)
A
where the second inequality holds because || A S || BIB for any n matrix B with rank(B) k, and the third inequality results from the triangle inequality ||A B 2(1 + |BB|3 for any two matrices A, B Baxd
A.2
Complementary Experiments
A.2.1
Experiments on Small Datasets
In this section, we compare our algorithm with four algorithms (TwoStage, Greedy, VolumeSampling, and ILS) introduced in Section 4 Jusing 14 small real-world datasets. Following [2] I. these datasets
are listed in Table 5 and all datasets can be found on the website
We use the same experimental settings as in Section 4 to run these algorithms on 14 datasets. The L.SCSS least 2 times faster than the Greedy,
running time results are presented Tables 7
cs. http::///wa.cccaaaollaaaaaaaaaar
http: http://wwwcccmm myu. httt:///oooiie/taaa.tt...
ntu http://wwwwaaaauuoooooo/oo//////
and hodhttt://ww.cct cl, cam. htt.://www......oo/aaaaaaaaaaaaa
20

---

VolumeSampling, and ILS algorithms. The error ratio, reported as mean + std, with the best results highlighted in bold, shown Tables and LSCSS outperforms all other algorithms in terms of quality across all datasets.
A.2.2 Experiments on QR with Column Pivoting and LSCSS Algorithms
In this section, we present experimental results comparing the performance of our proposed LSCSS algorithm with the QR with Column Pivoting (QRP) algorithm (4 for varying k. The QRP algorithm uses column pivoting to improve the traditional QR decomposition.
To compare our proposed algorithm with the QRP algorithm, we conducted experiments on five datasets: CMHS, ELD, Gas, FAds, and TGas (listed in Table 2). Due to the memory requirement of the QRP algorithm exceeding 2TB for the remaining datasets in Table those datasets were excluded from our comparison. For the QRP algorithm, we followed the procedure outlined [24], first obtaining the permutation matrix P that satisfies AP QR. Then, we selected the top k elements from the diagonal of as the indices C of the columns and computed the error ratio of solution Ac. The detailed results in Table show that our algorithm achieves lower error ratios across all datasets and is faster than the QRP algorithm.
21

---

Table Comparison results on error ratio for varying k on datasets. an algorithm fails to output solution within 48 hours, the enror ratio is marked as ">48h". : If its memory usage exceeds 2TB, the error ratio marked as "OOM" (Out of Memory).
Dataset
TwoStage 56.9579
Greedy
ILS
LSCSS
1.7446
[,2944000492
1..000
10
254.7578::8.3553
1,9111
1.880-10.0380
1.2237:10.084
15
223.9830-28.913
2.1692
1.6455:0.0006
1.613411.0117
20
655, 155.8496113.700
1,9725
1.582210.0120
1.648910.0482
CMHS
25
115.1154+12.772
1.9762
1.7237+000251
1.6652+0.066
30
133.9324+13.1533
1.9109
1.7012+00.081
1.6377
50
1408 5406:t 10.435
1,7384
1.85110.0005
L.225010.0553
100
2009
6568-125.6660 6895
1.5354
1..011
1.504210.0199
11791
1,0807
L066010.0166
L.644810.0194
10
1.2094=0.0172
1.1026
1071910.0002
1.0748
15
1.2007-0.0511
1.1217
L00277000088
1.072610.0114
20
L.2271+0.0088
1.1405
1.117420.0053
1.0815
FAds
25
- 0.00036
1,1477
1.291100.041
L.100-10.009
30
L.2728-0.0055
1.1647
L101110.00455
1.099810.0097
50
L.3320+0.0066
1.2205
1..3440.0331
1.2140=0.0112
100
14565=00.0118
1.3274
13511610.0522
1.262810.0195
2.0409=000028
1.5557
L.6266+0.0108
L1570=200337
10
1.6769
1.2228+0.0090
1.2197=000009
2.7804=-0.1867
1.6912
1.24660.00177
+.2397=000384
1..022
1.9075
1.31160001122
+..300
ELD
4.6062-10.136
1,9911
1.34770.0009
1.114610.0023
30
5.6617=001601
2.1623
L4855=0.0312
1.6671=0.0634
12.0868 1.1241
2,4405
1.6433+0.033
0.0475
100
42.7583+002457
2,9438
18116+000005
1.7935+0.0045
4..402-00.0298
1,4203
1.2041000015
0.6177001100
10.013
1,9085
14812-+0.0388
0..733
0.00530
2.0486
1.6772-0..062
1.0107
25.3236=0.0474
2.2949
1..00010.0220
1.59861000889
TGas
0.0005
2,4922
1.7614+0.036
0.0550
17.0122+000811
2,4077
1.7814+0.0129
1.7690+0.1291
109 0.0506
2.5511
1.0187
100023
125.7642:1000372
2,4501
L.7955
1.0475
1.00635
L5689
1..9200
1.72110.0765
12.1241
1.7191
1.222210.0760
1.0047
19.2035
1.7675
1.7093+000000
1.677910.0048
16.1705
1.7616
16635540.068
1.626310.0023
Gas
34.181320.111
1.7907
1.576610.0365
1..545
0.3999
1.8155
1.544010.0012
1.334610.0119
76.6821+1.8841
1.8207
1674990.0403
1.711710.0082
209 7.07177777
2.0473
L6823-00.116
1.667610.0165
OOM
1.6582
L0.077
1.253
OOM
1.7959
1.5023+0.0315
1.5346-0000448
OOM
24hh
40.864
1.5509
OOM
48h
1613660000163
1.0107
YaleB
OOM
24h
L.422240.087
1.334110.0300
OOM
48h
4-8h
1.67451000335
OOM
48h
448h
1.7484=00.000
OOM
>48h
448h
1.8616=0.0954
2.3392-+0.0009
1.7131
1.1239+0,0094
1.1277+0.0494
10
3.0365+00.0017
1,9146
1.2357+0,01.8
1.1451 +0.0188
>48h
48h
L.2277+0.0269
1.2380+0004490
248h
48hh
448h
1.330010.07300
Mnist8m
>48h
48h
248h
1.3659+0.0700
248h
48h
248h
1.3697+0.0877
248h
48h
48h
161099+000669
100
448h
>48h
44h
1.554=00.0401
E0.0485
1,0203
1..088
E..100
10
1.077410.000 0.0022
1.0243
10.2220
1.0241 1.00141
15
1.880510.000
1.0227
1.0822-1.02229
1.0227 10,0080
20
1.087610.00S1
1.0223
1.081410.0147
1.0220-0.0116
Epsilon
1.8884+0.0002
1.0223
1.8500+0.0094
30
1.0915+0.0079
1.0226
L.742240.012
1.022410.0066
1. 1882910.0004
1.0246
1730-00.0093
1.0242
100
1.082610.0019
1.0298
L0667410.008
0.055410.0467
22

---

Table 5: Summary of 14 Small Datasets
Dataset
Rows
Columns
Dataset
Rows
Columns
sonar
208
60
mediamill
30993
120
Binary AinaryAlpha
1404
320
musk
7074
168
dna
2000
180
arrhythmia
452
279
CTs
53500
386
sEMG
1800
2500
ORL
400
10304
USPS
9298
256
COIL20
1440
1024
ISOLET
7797
617
mnist
10000
784
UMIST
12880
Table 6: Comparison results of running time for varying on small datasets. If an algorithm fails to output solution within 48 hours, the running time is set ">48h".
Dataset
TwoStage
Greedy
VolumeSampling
ILS
LSCSS
1.14
1.70
71.75
0.32
0.02
10
1.13
1.53
146.81
1.10
0.05
15
1.16
2.37
217.47
2.77
0.07
20
1.18
3.32
241.11
5.72
0.14
arrhythmia
25
1.19
4.15
282.61
8.47
0.22
30
1.17
5.02
294.37
10.96
0.28
50
1.23
8.38
482.52
39.51
0.67
100
1.45
18.44
963.81
190.94
1.02
5
1.19
1.09
57.28
0,33
0.04
10
1.26
2.21
112.59
1.78
0.10
15
1.29
3,31
162.58
4,25
0.16
20
1.29
4.68
204.88
7,90
0.28
binaryalpha
25
1.32
5.87
260.07
12.03
0.36
30
1,31
7.89
297.84
15.68
0.51
50
1,38
14.29
487.54
50.88
0.75
100
1.56
27.69
929.32
254.56
1.39
1.37
3.84
1498.82
1.09
0.03
10
1.85
8.34
3050.59
4.26
0.16
15
2.03
13.56
4261.67
9.77
0.28
20
2.07
18.43
6147.76
17.20
0.44
COIL20
25
2.02
24.72
7242.89
28.77
0.49
30
2,03
30.44
9834.91
38.89
0.76
50
2.18
50.90
17081.15
113.82
1.59
100
2.49
89.30
73120.66
502.32
2.37
5
13.18
20.79
5119.43
10.30
0.97
10
15.37
46.10
10639.06
37.18
2.63
15
15.59
72.65
14595.50
81.18
3.74
20
15.42
101.63
23074.20
149.07
6.11
CTS
25
15.45
133.56
26595.60
237.15
7.65
30
15.58
166.70
31913.35
351.73
8.28
50
15.71
317.13
51880.07
1120.75
14.36
100
17.76
841.74
104368. 19
6138.42
38.39
0.41
0.43
23.34
0.57
0.04
10
0.48
1.08
46.23
3.01
0.08
15
0.43
1.67
86.54
6.38
0.17
20
0.53
2.32
101.05
11.31
0.24
dna
25
0.54
3.17
117.49
18.24
0.32
30
0.52
3.88
151.58
26.98
0.49
50
0.67
6.24
25
72.95
0.53
100
0.97
567.23
960.52
400.13
1.07
2.04
10,39
3617.83
3.79
0.35
10
2.29
22.89
5340.22
13.78
0.73
15
2.24
36.11
7067.92
29.61
1.04
20
2.25
49.81
8483.23
51.92
1.32
ISOLET
25
2.23
64.70
18531.69
82.38
1.81
30
2.24
79.76
21504.78
120.58
2.05
50
2.39
145.43
37048.08
343.95
2.28
100
2.62
333,87
52324.39
1512.94
3.92
23

---

Table 7: Comparison results on running time for varying & on 8 small datasets. If an algorithm fails output solution within 48 hours, the running time is set as ">48h".
Dataset
k
TwoStage
Greedy
VolumeSampling
LS
LSCSS
4.75
1739.68
4.93
0.52
10
4.63
10.11
2308.06
18.13
1.06
15
4.51
15.57
2739.37
40.99
1.86
20
6.55
21.39
3658.98
72.93
2,43
mediamill
25
7.54
27.41
4576.99
104.55
3.53
30
10.62
33.53
5481.76
143.93
4.26
50
13.78
60.84
9143.62
467.94
8,85
100
21.23
114.71
17427.80
2727.86
15.41
5
0.19
0.05
0.71
0.02
0.01
10
0.16
0.10
1.06
0.07
0.02
15
0.16
0.14
1.86
0.15
0.03
sonar
20
0.17
0.18
2.55
0.26
0.04
25
0.15
0.22
2.97
0.41
0.07
30
0.16
0.25
3.43
0.63
0.11
50
0.29
0.34
5.39
1.90
0.18
5
0.72
2.02
10.37
1.39
0.10
10
0.75
19.89
5.77
0.15
15
7.28
29.05
14.05
0.22
20
0.79
10.17
39.21
24.34
0.34
musk
25
0.81
13.15
47.87
41.61
0.40
30
0.87
16.27
55.09
57.71
0.68
50
0.83
29.45
90.17
184.35
0.75
100
1.25
60.38
178.53
761.19
1.90
5
4.99
40.26
6390.13
3.28
0,45
10
5.38
81.72
14800.67
10.92
1.04
15
5.98
124.24
31659.17
21.72
1.51
20
7.04
166.41
63172.23
38.54
2.02
sEMG
25
208.73
>48h
$7.43
2.47
30
7.71
253.16
248h
79.04
3,28
50
8.26
446.44
448
221.22
4.52
100
10.83
1003.05
>48h
920.75
8.79
5
2.88
26.40
4670.13
3.37
0.21
10
3.64
53.72
8317.94
8.18
0.27
15
80.43
12421.25
14.23
0.56
20
23.67
108.34
16367.79
21.98
0.78
ORL.
25
33.4
138.25
20450.05
31.43
1.13
30
35.64
168.26
24341.61
43.89
1.25
50
37.32
294.22
45980.34
107.87
2.54
100
47.36
716.27
96733.46
386.42
5
2,47
69.85
10852.31
6.02
0.2
10
2.94
140.38
21398.78
14.37
0.53
15
7.52
212.42
31965.75
25.03
0.90
20
22.61
278.14
44963.09
38.73
1.13
UMIST
25
31.67
328.22
53477.56 56
53.96
1.54
30
404.45
71528.05
69.63
50
33.31
732.53
448h
168.18
4.11
100
39.54
1532.27
448h
428.62
11.97
5
3.32
22.45
2834.30
4.73
0.38
10
47.99
5582.86
17.21
0.8
1.5
71.95
8039.87
37.67
1.33
20
3.49
96.56
10681.44
68.24
1.88
mnist
25
3.45
124.43
13936.23
104.85
2.43
30
3.52
153.30
19584.82
154.39
3.23
50
3.69
267.98
27634.12
435.65
4.71
100
4.16
572.09
58759.88 88
1907.21
7.84
5
0.91
1.15
303.02
2.24
0.12
10
1.14
2.25
628.31
8.11
0.25
15
1.13
3.35
947.55
18.84
0.33
20
1.12
4.60
1307.11
34.29
0.66
USPS
25
6.06
1584.26
54.62
0.82
30
7.59
1899.81
77.41
1.20
50
1.56
15.26
3327.07
241.06
2.37
100
2.21
41.90
6458.70 70
1088.98
6.79

---

Table 8: Comparison results on error ratio for varying on 6 small datasets. If an algorithm fails to output a solution within hours, the running time is set as ">48h".
Dataset
k
TwoStage
Greedy
VolumeSampling
ILS
LSCSS
17.308511.1164
1.1714
1.4125:0.0905
11800-10.0062
1.1682.10.022
10
17.9368
1.2812
1.563410.0785
1.3079=0.0013
1.2658=000208
15
16.9421=0.8017
1.3156
1.5160:10.0340
1.4088=10.0400
1.3688=
20
20. 20.3040=0:4101
1.3452
1.5497=00.013
1.4070=0.0320
1.3777=0.0225
CTS
25
18. 18.304910.3146
1.3677
1.5951=0.0837
L38553=0.006
1.3648
30
13.24433
1,3834
1.6504+000167
1.3929+000009
1.3694 0.0182
1..66110.0712
1.4342
1.452810.0550
1.506=
1.0175
100
1.5302+00.0299
1,5070
1.7487
1.7778+00.096
1.5048 0.0064
5
1,428010.0404
1.1746
1,5812 L.811210,0328
1.201 10.0110.0015
1.1746 0.0855
10
0.4429
1,2872
1.7471++0.058
1.3196+0.0015
1.2803 0.0816
15
1..177
1,4085
1,807 1.0.1319
L4415110.0081
1.3821 0.0546
20
1.7424=0.0380
1,5289
1.8776+0.
0.1103
1.4754
musk
25
1.7630==0.0551
1,5935
1.9104
16437=00000F
1.5439=
30
1..054
1.6808
2.1968
L..55
1.6111
50
2.0740=100139
1,9803
2,4366+t0.390
1.877=000072
1.8673
100
2.0904=0.0254
2,1873
3.1927#00.884
2.0254
1.8991=0.0443
1.2205-0.0306
1.3729
L.73990.0110
1.0000
1.05221
1.0558+0000008
1,4410
L6541++0066
14535+0.0239
1.3909 0.0432
15
1.792.10.0195
1.4766
1.762610.0298
1..000
1.4236 0.0664
20
1.7000
1.5664
18603
1.528510.0108
1,4788 0.0348
sonar
25
1.6245=000008
1,6982
09229
1.628800.0255
1.5287=0.044
30
1..0600
1.8787
2.0096
L.0064
1.623710.0586
2.7235
2.9159
2.4561#0.0 1478
2.7214=0.0215
2.3819
5
2.8072
1,2600
16455510.00
L0.0286
1.2547
10
2.8216=0003599
1,3135
1.,553
1.3544
1.3268=0.0392
15
18911-0.0170
1,3453
1. 1.6232+-00650
1.4237+000091
1.3438-0.0206
20
1.6448++00019
1,3808
-.0055
1.4900+000088
1.3684
ORI.
25
L.5535=00.088
1.4079
100005
1.500410.0049
1.3942
0.5677+0.0003
1.4263
1.7528 0000836
1.5156+000066
1.4241 0.0355
50
1.5957110.0513
1,5325
L.789010.0531
L621441.00033
1.4807 1.0199 0.0192
100
1..025
1,5818
188577100112
1.968
1.5700
5
L.3988
1,2998
L.0072
1.188310.2219
1.1928
1.0053+00.0029
1,5151
1.7870+00.0117
1.5065+0.0214
1.4632+
1..57510.0521
1.6312
2.0675
1..0971
1.5790
20
188655
1.7242
2.0169
1659221.00152
1.6767
USPS
25
1.82181000618
1.7965
2.0815
1.7480=0.0297
1.7356=0.0413
30
1..698
1.8310
2.7416+00.040
1.7546+0.0119
0.0245
50
1.8854+0.0029
2,0011
3.0553+0.0883
2.0407+0.0576
1.9515 0.0399
2..5821000022
2.7733
3.467110.0813
2..15510.0457
2.436110.0307
5
L.573610.0249
I.1986
L.883210.0261
L..663000000
1.1618
10
1.9387+000235
1,2684
1.7408 +0.0712
1.2688+0.008
1.2101
15
2.2904+-00650
1,3649
1.7815=+00045
1.3349+000043
1.3110=0.0678
20
1..9.10..6888
1.3591
L.852210.0069
1.360010.0108
1.341510.0317
arrhythmia
25
3.3725-:023229
1.3759
1.9422+000003
1.022--0.0222
1.3926=
4.0065
1.4424
2.1
L..012
1.4012
50
7.5592
1.6928
2.5196
L6651-50
0.0288
100
49. 49.6032+3.3000 3052
1,4044
2.8522+00:297
1.8034 2081
1.334610.01366
5
1.7082-10.0289
1,2929
1.519
1.2792+0.0064
1.243410.0305
1.721740.0175
1.3793
1.559410.0608
1.3555+0.0044
1.3465
1.7193+0.0121
1.4167
0.0996+
1.1155000004
1.3911+0.0187
20
1.99771000173
1.410
1.811710.0653
14360 0041
1.4172
mnist
25
2.0008
1,4677
1.7307+0.0529
1.442++0.00 0068
1.4475+0.0107
30
2.3759--0.0348
1,4977
1.870++0.0311
1.4957+0.00M6
1.4768
50
20.0550
1,5554
1.6630L0.0184
L.664710.0053
1.525710.0106
3.0237+000055
1.6526
1.9803+0.066
1.6579+0.008S
1.026310.0081
5
0..999
1.1589
1.502410.0115
L2701
1.1598
10
1.4822+00.0556
1.2134
1.6256+0.0071
1.2612+0.00 0046
122126=00035
15
1.4773--0.0078
1,2693
1.8853-000012
1.3133++00434
1.2682 - 0.0327
20
1.5133+000111
1.3294
1.7625
1..0919
1.3169
ISOLET
25
1.6296-0.0152
1.3549
1.80251000015
1.3961+0.0236
1.3415
1.5717+0.0092
1.3784
1.8406+0.0703
1.4217000131
1.3648-0.0458
50
1.336410.0034
1.4751
L..4580
1.928
1.0135
100
1.6996+0.0274
1.6226
1.9499+0000722
1.5936+00.003
1.5788+000226
25

---

Table 9: Comparison results on error ratio for varying on 8 small datasets. If an algorithm fails to output solution within hours, the running time is as ">48h".
Dataset
k
TwoStage
Greedy
VolumeSampling
ILS
LSCSS
1.46971000117
1.3284
1.500311.0003
L.3222-100107
1.2960
10
1.5501=0.0149
1,3169
1.4947=000091
1.3341=0.0032
1.3090=0.0206
15
1.5496:10.0126
1.3630
1.5128:1.0014
1.3833:10.0042
1.3887-0.0107
20
1.5371
1,4275
1.5364=10.0025
1,4570=0.0005
1.4209=0.0125
UMIST
25
1.5090==0.008
1,4742
1.5883=0.004s
1.4927=000058
1.4615-0.0126
30
0.0993
1.5160
0.0083
1.5222++0.0092
1.5043-0.000
1.704810.0232
1.6366
>48h
1.780=10.0045
1.6344=0.0137
100
1.7600+0.0107
1.7321
5-8hh
1.7273+000056
1.7040-0.0084
5
1.351010.0135
1.2534
1.,9910000097
12451110.0184
1.2209-0.0205
10
1.3550+0.008
1.3227
1.4320+00.034
1.3067+000080
1.0026-0.0225
15
1..0011
L.3988
1.544110.0067
1.391510.0020
1.3796-0.0131
1.43931000063
1.4378
10.011
1.336610000822
14336-000022
binaryalpha
25
1. 1.4929=0.0119
1 1,817
1.7525=000600
1.4625+0.0043
1.597=
30
1..0022
1,5118
L.7725-10.008
1.889510.0079
0.0150
50
1. 1.6041
1.6082
1.8562=0.0257
1.5813+0.0008
0.0140
100
1.6710=0.0143
I. 1.6598
0.947
1,647440.001
1.33990000992
3.9687+000615
1.4194
L6815-20.1039
1.428810.0264
1.0455
1.7655+0.0345
1.4854
1.7398+-000277
14537+0.0218
15
1.708110.0139
1,5274
1.745510.0664
1.5532+0.0011
1.5147
20
1.887010.0218
1.6024
18859910.100 1043
1.566610.0196
1.022100.0208
COIL20
25
1.9023+0.0104
1.6271
2.0515+000062
1.0066+0.0141
1.5638-0.0118
30
1.884110.0119
1.6389
2.0710_10.181
1.300-10.01300
1.5964-0.0167
2.0020
1.6892
2.02044
16.47710.0140
1.6066
100
1. 0.836
1,8014
3.5690=10.2333
1.7837+0.012
1.7498=0.0110
5
1. 0.1010
1,0818
1.129410.0011
108000
1.0878=0.0166
10
0.0996
1.1029
1,0042
1.1060+1.0020
1.1025 0.0085
1,0005
15
0..055
1.1235
1.0138
1.0200
1.1213 0.0043
1.1643=0.0971
1.1434
1.173810.0046
L.1453+0.0007
1.0055
dna
25
1.1801
1.1645
1.1857-0.0092
1.1649+000016
1.1603-0.003 0.0038
30
1.2006
1.1851
1.2179-0.0108
1.183410.0000
1.1776=0.0078
50
1.283910.0934
1.2766
1.309510,0055
1.2692110.00D
1.2617-0.0034
100
1. 1.6617+0.0656
1. 1.6688
1.7365+000815
1.6383+0.0021
6.0066000115
0.070
1,6583
2.1393-0.1273
1..110
1.4173-0.1028
10
1. 1.8658+0.0083
1,7480
2.4754-002760
1.6673+0.0309
1.5602=0.1459
15
2.0647
1.8526
2.6652-0..078
1.728
1.312-0.1055
20
1.9377=00.091
1.9888
2.7980=10.124 1245
1.8633 0.0002
0.0988
mediamill
25
2.0098
2.0537
2.8292-L0.0740
1.4453+0.0329
188944-0.11
30
2.3301 +..0015
2.0571
2.9513-
0..0550
1.8636 0.1155
2.257410.0269
2.1938
3.038410.1871
2.0635+10.5882
1.949
2. 2.7410+0.0133
2.6013
3.3817-0.1266
2.3854+0.0023
2.06446
5
+0.0003
T.0231
L,0277-0.0006
L.252+00.0000
T.0217
10
1.4477+0.000
1.0322
1.0452+000024
1.338-+0.003
1.0343+0.0094
15
1.080-10.0033
1.0411
1.00050
10444510.0031
1.043010.0022
20
1. 0.886+000001
1,0995
1.1043=000032
1.0502+0.0053
1.0494-000055
sEMG
25
1.107910.0003
1.0572
48h
L..57510.0075
1.0572 0.0049
30
1.138610.0001
1.0447
48h
1.0691 106911000001
1065571.000
50
1.1117+0.0006
1.0922
448
10925=+0.0016
0.0004
100
1..496+0.0011
1.1450
448h
1.3360+0.0008
1.1332 0.0054
26

---

Table 10: Comparison results on error ratio and running time for QRP and LSCSS algorithms
QRP
LSCSS
Dataset
k
ratio
time
ratio
time
4.9384
1289.86
1.1348=0.0202
2.82
10
3.3580
1289.87
1.2237=:0.894
5.17
15
5.7633
1289.87
1.613420.017
13.39
20
3.5838
1289.90
1.6489+10.0482
30.45
CMHS
3.7979
1289.88
1.6652+000028
43.27
30
4.0852
1289.91
1.6377+000136
52.82
50
4.0925
1289.93
1.6250=0.0553
62.36
100
4.6109
1289.98
L.5042-0.0199
108.98
1.968I
124.93
1.1570
2.18
10
2.5603
124.93
1.2197
3,47
15
2.6873
124.94
1.2397
5.36
20
2.8871
124.94
L.
13.93
ELD
25
3,4399
124.94
1.0022
22.98
30
3.5369
124.95
1.6014
35.03
50
4.3966
124.97
1.5475
66.27
100
4.8920
125.03
1.793550.0445
89.94
2.2778
913.83
L4721
5.83
10
2.1567
913.60
1.6015
11.67
15
2.5804
913.60
1.6779
19.3
20
2.4450
913.62
1.6263+0.0263
47.9
Gas
25
2.7521
913.60
1.6545=000031
130.11
30
2.8961
913.62
1.634610.0199
322.92
50
2.8465
913.63
1.6717+000082
386.15
100
3.6717
913.65
1.6166+
850.01
1.1361
6487.57
L.0011
3.4
10
1.1805
6487.52
1.024810.0208
10.58
15
1.2055
6487.52
1.0726+0.0114
17.65
20
1.2224
6487.54
1.0815+0.0126
18.27
FAds
1.2383
6487.55
1.1020=00.000
22.29
30
1.2531
6487.65
1.0099
22.76
1.2886
6487.62
1.2140+0.0112
36.04
100
1.3430
6487.74
1.2628+0.0199 +00199
95.67
2,7632
1239.08
1.1657+0.110
17.15
10
4.0830
1239.06
0..033
30.28
15
6.4080
1239.07
1..107
36.99
20
7.1182
1239.07
L.00869
49.9
TGas
25
9.3027
1239.08
L0.0850
61.36
30
10.4892
1239.10
1.7680
77.93
50
18,9009
1239.16
1.7628
114.23
100
23.9558
1239.42
1.7873
243.89
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract reflect the paper's 's primary contributions and scope. In this paper, an approximation algorithm with running time linear in both n and d is proposed for the Column Subset Selection problem, which selects exactly &o columns.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
Justification:
This paper has no limitation.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
28

---

Answer:
[Yes]
Justification:
All the theorems, formulas, and proofs are clearly stated in the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The information required to reproduce the main experimental results is pro- vided in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
29

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The datasets can found via the link provided in the paper, and the codes are available upon request via email.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ https/cccppbllcgggudeeeeeeeeeeee Coaee//ddeeSSbbmmmma ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental settings have been clearly stated in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In the experiment comparison results, each algorithm is executed 10 times on each dataset, and the average results reported as the final results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
30

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative еттоr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: For each experiment, the paper provides details on the computer resources required to reproduce the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
The research presented in the paper complies with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We present linear time local search algorithm for the CSS problem with actly & columns selected, which we expect to be beneficial for handling other dimensionality reduction tasks. The primary purpose offer algorithmic insights for obtaining linear time algorithm, where we do not foresee any societal consequences specifically related to the proposed method.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
31

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks about safeguards.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper poses no such risks about safeguards.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
32

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does not involve corwdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
33

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "QMOsDy7bdb", "reviewer": "Reviewer_6BV1", "summary": "The paper addresses the classical CSS problem, and describes significant\nimprovements over the current state of the art.\nThe main idea is to run the randomized\nadaptive sampling algorithm for selecting k columns,\nand follow it by several iterations of swapping (local search),\nthat further increase the accuracy. The swapping replaces one of the selected\ncolumns with another unselected column when such swapping reduces the error.", "questions": "* Why is there no comparison with the QRP?\n* How good is your accuracy compared to the optimal of worst case of (k+1)?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main novelty is in the design of the local search.\nThe algorithm first selects 10k top norm candidates, and then selects uniformly\nat random among those. Even though the analysis does not show their algorithm\nto be the most accurate, the experimental results clearly demonstrate\nthe superiority of this approach.", "weaknesses": "* There is no experimental comparison with the QRP (QR with Pivoting) method, \n  which is known to show very good results in practice.\n  It is significantly faster than your algorithm, as it takes:\n\n  4knd - 2 k^2(d+n) + 4 k^3/3\n\n* The running time of the proposed algorithm is \n\nO(nd k^3 log k)\n\nI do not consider it fast. There are other algorithms that run much faster\n(eg Frieze, Kannan and Vempala, JACM 2004, and the above mentioned QRP).\n\nI am also not that impressed by the relative bound of 110(k+1),\nas there are other algorithms with 100 times better bounds (specifically k+1).\nWhat is most surprising here is your experimental results.\n\n\nSome notes:\n\nline 41. CSS is known to be NP-hard. \nSee \"Column subset selection is NP-complete\" by Shitov, 2021.\n\nline 42. The comment is incorrect wrt reference 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive rating and the thoughtful comments. In the following we address the concerns.\n\n**Question 1. Why is there no comparison with the QRP (QR with Pivoting) method?**\n\nResponse: The main reason that QRP is not compared with our CSS method is because they select columns for different purposes. In the QR decomposition process, QRP chooses the most influence column at each step to maximize the numerical stability (i.e., it selects the column with the largest norm as the pivot column and swaps it with the current one), while CSS selects columns to best represent the input matrix. Many CSS algorithms identify the most representative columns (for dimension reduction) by using objective functions or volume sampling to measure column importance. Even though both QRP and CSS choose a subset of columns, they use them for different objectives. Thus, we have focused our comparisons on those  methods that solve CSS.\n\nSince the subset of columns obtained by QRP can also be viewed as the solution of dimension reduction. For completeness, in the following, we compare our proposed algorithm with the subset of columns obtained by QRP. We conducted experiments on 5 datasets: CMHS, ELD, Gas, FAds, and TGas (listed in Table 2 of our submission). For the QRP method, we first call the algorithm in [2] to obtain the permutation matrix $P$ that satisfies $AP=QR$. Then, we select the top $k$ elements of the diagonal of $P$ as the indices $C$ of the $k$ columns and compute the error ratio of the solution formed by $C$ as mentioned in line 290. The detailed results in Table 1 show that our method achieves the lowest error ratios across all datasets and is faster than the QRP method.\n\n| Dataset | k   | QRP Ratio | QRP Time | LSCSS Ratio          | LSCSS Time |\n| ------- | --- | --------- | -------- | -------------------- | ---------- |\n| CMHS    | 10  | 3.3580    | 1289.87  | 1.1478 $\\pm$ 0.1094  | 5.17       |\n| CMHS    | 20  | 3.5838    | 1289.90  | 1.1815 $\\pm$ 0.0586  | 30.45      |\n| CMHS    | 30  | 4.0852    | 1289.91  | 1.1988 $\\pm$ 0.0772  | 52.82      |\n| CMHS    | 50  | 4.0925    | 1289.93  | 1.2535 $\\pm$ 0.0560  | 62.36      |\n| CMHS    | 100 | 4.6109    | 1289.98  | 1.3334 $\\pm$ 0.0194  | 108.98     |\n| ELD     | 10  | 2.5603    | 124.93   | 1.2929 $\\pm$ 0.0652  | 3.47       |\n| ELD     | 20  | 2.8871    | 124.94   | 1.3656 $\\pm$ 0.0225  | 13.93      |\n| ELD     | 30  | 3.5369    | 124.95   | 1.4834 $\\pm$ 0.0761  | 35.03      |\n| ELD     | 50  | 4.3966    | 124.97   | 1.4946 $\\pm$  0.1086 | 66.27      |\n| ELD     | 100 | 4.8920    | 125.03   | 1.7470 $\\pm$ 0.0692  | 89.94      |\n| Gas     | 10  | 2.1567    | 913.60   | 1.6315 $\\pm$ 0.0747  | 11.67      |\n| Gas     | 20  | 2.4450    | 913.62   | 1.7466 $\\pm$ 0.0542  | 47.90      |\n| Gas     | 30  | 2.8961    | 913.62   | 1.6915 $\\pm$ 0.0372  | 322.92     |\n| Gas     | 50  | 2.8465    | 913.63   | 1.8173 $\\pm$ 0.0287  | 386.15     |\n| Gas     | 100 | 3.6717    | 913.65   | 1.9362 $\\pm$ 0.0344  | 850.01     |\n| FAds    | 10  | 1.1805    | 6487.52  | 1.0748 $\\pm$ 0.0208  | 10.58      |\n| FAds    | 20  | 1.2224    | 6487.54  | 1.0815 $\\pm$ 0.0126  | 18.27      |\n| FAds    | 30  | 1.2531    | 6487.65  | 1.0898 $\\pm$ 0.0097  | 22.76      |\n| FAds    | 50  | 1.2886    | 6487.62  | 1.0853 $\\pm$ 0.0087  | 36.04      |\n| FAds    | 100 | 1.3430    | 6487.74  | 1.1334 $\\pm$ 0.0085  | 95.67      |\n| TGas    | 10  | 4.0830    | 1239.06  | 1.3696 $\\pm$ 0.0731  | 30.28      |\n| TGas    | 20  | 7.1182    | 1239.07  | 1.7932 $\\pm$ 0.0764  | 49.90      |\n| TGas    | 30  | 10.4892   | 1239.10  | 1.8677 $\\pm$ 0.1050  | 77.93      |\n| TGas    | 50  | 18.9009   | 1239.16  | 2.0565 $\\pm$ 0.1475  | 114.23     |\n| TGas    | 100 | 23.9558   | 1239.42  | 2.1499 $\\pm$ 0.0883  | 243.89     |\n*Table 1: Comparison results of QRP and LSCSS algorithms*\n\n[1] Quintana-Ortí, Gregorio, Xiaobai Sun, and Christian H. Bischof. A BLAS-3 version of the QR factorization with column pivoting. SIAM Journal on Scientific Computing 19.5 (1998): 1486-1494.\n\n**Question 2. How good is your accuracy compared to the optimal of worst case of (k+1)?**\n\nResponse: We thank the reviewer for asking this question. Chierichetti et al. [1] proposed an algorithm to obtain the (k+1) ratio by enumerating all $k$-column subsets in the worst case, with exponential time complexity ($n^k$ subsets), which makes it hard to handle large-scale datasets. Theoretically, our proposed LSCSS achieves a $110(k+1)$-approximation.\n\nTo compare the accuracy of our proposed LSCSS with the enumeration algorithm in [1], we follow the setting in [2] and construct a synthetic dataset consisting of a $1000 \\times 20$ random matrix $A$, where $A_{i,j}$ are i.i.d. from a normal distribution. We provide additional results comparing our LSCSS algorithm with the enumeration algorithm on synthetic dataset. The detailed results show that the error of our method is only $0.05\\\\%$ higher than that of the enumeration algorithm.\n\n| k   | Enumeration | LSCSS                |\n| --- | ----------- | -------------------- |\n| 5   | 1.0421      | 1.0421 $\\pm$ 0.0002  |\n| 10  | 1.0892      | 1.0898 $\\pm$ 0.0001  |\n| 15  | 1.1379      | 1.1390 $\\pm$  0.0007 |\n*Table 2: Error ratio of the Enumeration algorithm and LSCSS on a synthetic dataset* \n\n[1] Chierichetti Flavio, et al. Algorithms for $\\ell_p $ low-rank approximation. Proceedings of the 34th International Conference on Machine Learning, pages 806-814, 2017.\n\n[2] Paul Saurabh, et al. Column selection via adaptive sampling. Advances in neural information processing systems 28, pages 406-414, 2015.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ogm8HZIZ6N", "reviewer": "Reviewer_oKb7", "summary": "This paper studies column subset selection. Given a matrix A n*d, how to select a matrix A_S of k columns, which preserves the substance in A? That is, reconstruction error ||A - (A_S A_S#) A||_F should be minimized, where A_S# is the psuedo-inverse of A_S. There are many approximation algorithms for this problem, and it is widely studied in theoretical ML/CS literature. There is a plethora of running-time vs approximation factor guarantee in the literature.\n\nThis paper tries to match the SoTA approx. factor with faster running time. Indeed, SoTA algorithm has (k+1)-factor approximation with running time O(n d^2 k). If we wanted linear in n and d, best known algorithm had approx. factor (k+1)! with O(n d k^2) running time. This paper's main contribution is 110 (k+1)-approximation with running time O( n d k^3).\n\nTechnically, the main innovation is to show that a constrained version of local search works. Local search is a good algorithm where we initialize a decent solution say the (k+1)! approx. solution, and iteratively swap out a column in the current solution with one not in. This step is expensive, having k*d possible combinations and we need to see which is the best! Multiplying this with # of rounds will yield large running times not-linear in d. \n\nThis paper overcomes this by showng that not all swaps are needed to be tried. Indeed, they sample O(10k) possible columns based on some form of random sampling (by looking at the residual importance of various columns), and further uniformly sample one of them at random to swap in. Now, the complexity of testing swaps is only O(k)! The challenge is now to show that the algorithm will not get stuck in bad local optima.\n\nFor this authors present a set of \"test swaps\" based on optimal set of columns and algo set of columns, and show that we will end up sampling one such pair with decent chance, if the current soln is far from optimal.\n\nFinally they run experiments comparing with prior art and show better running time AND quality. Overall solid piece of work and worthy of NeurIPS. The randomized local search idea is good, and the backing with empirical evals is also welcome.", "questions": "Are there practical use-cases of the CSS (where the interpretabiltiy is crucial? as opposed to SVD). \nIn typical use-cases, do we sample rows (from n like a coreset) or columns (from d like dimension reduction)? \n\nThe obj. function f doesn't appear to be defined where it is first used.\nCan your algo give better guarantees when allowed to pick more than k columns? How does this compare to prior SoTA in this regime?\n\nWhere is the randomness captured in Thm 3.9? Is it in expectation? WHP? The proof has some details but the formal statement should also have it.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Writing is good. Comparion with prior art is also nicely done. The algo is clean and elegant, the idea of randomized local search to improve running time is novel (at least to me, authors should mention if similar ideas appear in other uses of local search). \n\nGood of you to run experiments and validate the niceness of algo!", "weaknesses": "The problem is important, though it would be nice for authors to present why \"subset\" selection is significant as opposed to top-k-SVD. It is a bit unfair to expect a full motivation because this is standard problem, but a bit more explanation for the importance of the problem would be nice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive rating and the thoughtful comments. In the following we address the concerns.\n\n**Question 1. Are there practical use-cases of the CSS (where the interpretabiltiy is crucial? as opposed to SVD). In typical use-cases, do we sample rows (from n like a coreset) or columns (from d like dimension reduction)?**\n\nResponse: We thank the reviewer for bringing up this issue. Although both SVD and CSS can be used for dimensionality reduction, they adopt quite different strategies. Specifically, SVD achieves dimensionality reduction by decomposing the matrix into $U\\Sigma V^\\top$, aiming to capture the low-rank structure of the input matrix. The SVD method generates new features as linear combinations of the original features, resulting in lower interpretability. In contrast, CSS focuses more on the interpretability of the solution, and selects columns based on their importance in performing specific tasks. Since it retains the original columns, CSS often offers better interpretability.\n\nA practical application of CSS is as follows. In remote sensing image classification, as given in  [1], CSS selects a subset of the original features, which have clear physical meanings in the context of remote sensing images. As pointed out in [1], the aim of column subset selection is to find the most informative and distinctive features, which provide better interpretability for specific applications.\n\nSaurabh et al. [2] used sampling method for column selection. Greedy method was applied in [1] for the remote sensing image classification, and Jason et al. [3] also applied greedy method. Sampling methods were used in [4, 5] to deal with both row and column selection. Our proposed LSCSS is a local search method used for dimension reduction, and has advantages over the state-of-the-art methods for accuracy and time, which have potentials for many applications.\n\t\n[1] Benqin Song, et al. New feature selection methods using sparse representation for one-class classification of remote sensing images. IEEE Geoscience and Remote Sensing Letters 18(10):1761-1765, 2020.\n\n[2] Paul Saurabh, et al. Column selection via adaptive sampling. Advances in neural information processing systems 28, pages 406-414, 2015.\n\n[3] Altschuler Jason, et al. Greedy column subset selection: New bounds and distributed algorithms. Proceedings of the 33rd International Conference on Machine Learning, pages 2539-2548, 2016.\n\n[4] Deshpande Amit, and Luis Rademacher. Efficient volume sampling for row/column subset selection. Proceedings 51th Annual Symposium on Foundations of Computer Science, pages 329-338, 2010.\n\n[5] Frieze Alan, et al. Fast Monte-Carlo algorithms for finding low-rank approximations. Journal of the ACM 51(6):1025-1041, 2004.\n\n**Question 2. The obj. function f doesn't appear to be defined where it is first used. Can your algorithm give better guarantees when allowed to pick more than k columns? How does this compare to prior SoTA in this regime?**\n\nResponse: We thank the reviewer for raising the question. The objective function $f$ is defined in line 131 (Section 2). In the revised version, we will make the definition of $f$ clearer. \n\nFor the CSS problem, selecting more columns can potentially improve the approximation guarantees. Theoretically, we can prove that selecting more than $k$ columns can lead to a decrease in the objective function value, as follows. Let $S_k$ be the solution with $k$ columns, and let $S_{k+1} = S_k \\cup v$ be the solution with one additional column $v$. According to line 422 of this paper, $f(S,A) = \\text{tr}(A^\\top A) - \\Vert S S^\\dagger A \\Vert_F^2$. Therefore, $f(S_{k+1},A) - f(S_k, A) = \\Vert S_k S_k^\\dagger A \\Vert_F^2 - \\Vert S_{k+1} S_{k+1}^\\dagger A \\Vert_F^2$. From Lemma 1 in [1], we have $\\Vert S_k S_k^\\dagger A \\Vert_F^2 - \\Vert S_{k+1} S_{k+1}^\\dagger A \\Vert_F^2 \\le 0$. This implies that the function $f(A,S)$ is monotonically non-increasing. Thus, if the local search outputs a solution $S_k$ with $k$ columns, then by adding a column to form $S_{k+1}$, we can at least guarantee that $f(S_{k+1},A) \\le f(S_k, A)$.\n\nTo demonstrate that the objective function value decreases as the number of columns selected is larger, we conduct experiments using our proposed LSCSS with varying $k$ values on 8 datasets (listed in paper). We use the objective function $f(S,A) = \\Vert A - SS^\\dagger A \\Vert_F^2$ to measure this property. The detailed results, shown in Figure 1 of the attached PDF, suggest that the objective function value indeed decreases as the number of selected columns increases.\n\nComparing two algorithms on the same dataset with different numbers of selected columns is unfair. When the same number of columns is selected, the algorithm can be compared with the SoTA.\n\n[1] Altschuler Jason, et al. Greedy column subset selection: New bounds and distributed algorithms. Proceedings of the 33rd International Conference on Machine Learning, pages 2539-2548, 2016.\n\n**Question 3. Where is the randomness captured in Thm 3.9? Is it in expectation? WHP? The proof has some details but the formal statement should also have it.**\n\nResponse: We apologize for not clearly describing the role of randomness in our submission. In Theorem 3.9, the solution $S$ returned by Algorithm 1 satisfies $\\Vert A-SS^\\dagger A\\Vert_F^2 \\le 110(k+1)\\Vert A -A_k\\Vert_F^2$ in expectation. In the revised version of the paper, we will make it clearer.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EwcYkMdpmt", "reviewer": "Reviewer_ANHu", "summary": "The Column Subset Selection (CSS) problem aims to select a sub-matrix with $k$ columns from a matrix to minimize the residual error. Previous algorithms often have non-linear running times or higher approximation ratios. This paper proposes a local search-based algorithm with linear running time, utilizing a two-step mixed sampling method to reduce enumerations and a matched swap pair construction to maintain approximation quality. Empirical experiments demonstrate superior performance in quality and speed compared to existing methods, particularly in large datasets.", "questions": "- Algorithm 2 (line 2): How would the numerical performance change if $10k$ columns were replaced with a different number of columns (e.g., $2k$ or even a constant [1])?\n\n- Using the objective function to guide which column to swap out shares a similar spirit with recent advanced algorithms for best-subset selection under linear regression for sparsity-constrained optimization [2, 3]. It would be interesting to discuss these works. \n\n- How should $k$ be selected in practice?\n\n- Table 9: The error ratio of TwoStage on the ComCri dataset is weird. It is exceptionally large when $k=50$ but suddenly reduces to a comparable result when $k=100$.\n\n### Reference\n\n[1] Bahmani, Sohail, Bhiksha Raj, and Petros T. Boufounos. \"Greedy sparsity-constrained optimization.\" The Journal of Machine Learning Research 14.1 (2013): 807-841.\n\n[2] Wang, Zezhi, et al. \"Sparsity-Constraint Optimization via Splicing Iteration.\" arXiv preprint arXiv:2406.12017 (2024).\n\n[3] Zhu, Junxian, et al. \"A polynomial algorithm for best-subset selection problem.\" Proceedings of the National Academy of Sciences 117.52 (2020): 33117-33123.", "limitations": "The authors have discussed the limitations in the end of this paper.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The proposed new iterative algorithm for column subset selection is simple and sound. \n\n- The theoretical analysis of the algorithm appears novel and solid. \n\n- In experiments, the proposal is generally the fastest one together with competitively small errors.", "weaknesses": "- Line 41: What is UG?\n\n- Line 132: Is Lemma 2.1 necessary for the main text?\n\n- Algorithms 1 and 2: It would be better to give the full name of the algorithms.\n\n- Section 3 does not clearly discuss the algorithmic distinction beyond ILS and Greedy.\n\n- The theoretical results of the algorithm are mixed with the algorithmic details, making the paper poorly structured. Additionally, the assumptions are not explicitly listed and lack sufficient discussion.\n\n- Table 4: The standard error of Greedy hasn’t been reported. Besides, it would be better to put Table 4 into the main text and discuss why LSCSS achieves superior approximation compared to the competitors.\n\n- Lines 320 and 321 are repetitive.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive rating and the thoughtful comments. In the following we address the concerns.\n\n**Weakness 1. Line 41: What is UG?**\n\nResponse: We thank the reviewer for this question. ``UG-hard\" refers to problems that are as hard as the Unique Games problem, based on the Unique Games Conjecture (UGC). If a problem is UG-hard, it means that there is no efficient algorithm to approximate the problem beyond a certain factor, assuming the UGC is true. This suggests the problem is very difficult to solve unless P=NP or the UGC is disproven.\n\n**Weakness 2. Is Lemma 2.1 necessary for the main text?**\n\nResponse: We apologize for the confusion. Lemma 2.1 is used in the proof of Lemma 3.2 to ensure that the third inequality (line 417) holds. Thus, it is necessary.\n\n**Question 1. How would the numerical performance change if $10k$ columns were replaced with a different number of $2k$ columns (e.g., or even a constant [1])?**\n\nResponse: We thank the reviewer for asking this question. The choice of selecting $10k$ columns is based on ensuring the probability of sampling a good column in each iteration. If we change it to $2k$ columns, it would lower the probability of successfully finding a good column.\n\nIn the following, we provide additional results comparing the selection of $10k$ columns and $2k$ columns for our LSCSS algorithm with varying $k$ values on the 8 datasets (listed in paper). The detailed results, shown in Figure 2 and 3 of the attached PDF, indicate that the accuracy of LSCSS is better with the selection of $10k$ columns than with the selection of $2k$ columns.\n\n**Question 2. Using the objective function to guide which column to swap out shares a similar spirit with recent advanced algorithms for best-subset selection under linear regression for sparsity-constrained optimization [2, 3]. It would be interesting to discuss these works.**\n\nResponse: We thank the reviewer for asking this question. For best-subset selection in regression, Wang et al. [2] proposed the ABESS algorithm using the splicing technique. The method uses backward sacrifice and forward sacrifice operations to decide which variables should be swapped. The splicing technique improves the quality of subset selection by minimizing the sum of residual squares and continuously optimizes the objective function value.\n\nFor the sparsity-constrained optimization problem, Zhu et al. [3] proposed the SCOPE algorithm. This algorithm generates new candidate sets through local coordinate exchanges and uses the objective value to guide these exchanges, ensuring that the objective value decreases in each iteration.\n\nWe use a local search algorithm based on two-step mixed sampling to achieve linear-time solutions for the CSS problem. To avoid $O(dk)$ enumerations of swap pairs, we designed the two-step mixed sampling technique, using the objective function to guide which column to swap out, reducing the enumeration of swap pairs from $O(dk)$ to $k$. This leads to the running time of a single local search to $O(ndk^2)$. By analyzing the sampling probability designed based on the objective function, we can provide theoretical guarantees of the local search.\n\nIn summary, both our algorithm and those in [2,3] use some form of objective or loss function to guide the selection and swapping of variables. However, our algorithm differs from the ones in [2, 3]. The methods in [2, 3] use the objective function to guide the swapping process, identifying columns that improve the objective function value. Our algorithm uses the objective function to design the sampling probability, which guides the swapping process to accelerate the running time of local search step. Additionally, we can establish a theoretical relationship between the solution generated by this swapping strategy and the optimal one. Using the strategies from [2, 3] might make it difficult to establish this kind of approximate relationship between solutions.\n\n**Question 3. How should $k$ be selected in practice?**\n\nResponse: We thank the reviewer for asking this subtle question. As pointed out in [1,2], the value of $k$ is often treated as a constant input, and the choice of $k$ typically ranges between 1 and 500 in experiments. For all the values between 1 and 500, which one is the best is often hard to decide.\n\nFor the medical data analysis application of CSS, Shanab et al. [3] gave that the selection of $k$ is related to the objective function value and correlation measures. However, Shanab et al. [3] did not give the procedure to find an appropriate $k$.\n\nAs far as we know, there is no relevant result deciding the choice of $k$ in practice. How to determine the appropriate $k$ value is an interesting problem, and deserves further study.\n\n[1] Christos Boutsidis et al. An improved approximation algorithm for the column subset selection problem. In Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 968-977, 2009.\n\n[2] Venkatesan Guruswami and Ali Kemal Sinop. Optimal column-based low-rank matrix reconstruction. In Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1207-1214, 2012.\n\n[3] Shanab, S., et al. Stable bagging feature selection on medical data. Journal of Big Data, 8(1):1-18, 2021.\n\n**Question 4. Table 9: The error ratio of TwoStage on the ComCri dataset is weird. It is exceptionally large when $k=50$ but suddenly reduces to a comparable result when $k = 100$.**\n\nResponse: We thank the reviewer for this question. The TwoStage algorithm involves sampling a subset of columns to construct a candidate solution. The ComCri dataset contains 123 columns. When $k = 50$, the algorithm samples a candidate set of 89 columns. Under this case, the accuracy is exceptionally large. When $k = 100$, following the method in [1], the sampled size is larger than 123. Then, the algorithm selects all 123 columns, which makes the subsequent process easier. Thus, the accuracy in such cases reduces to a comparable result.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4wIHBMu5Ax", "reviewer": "Reviewer_MkHx", "summary": "This paper proposes a new algorithm for the column subset selection problem which combines a local search-type strategy with adaptive sampling techniques to obtain an algorithm running in time linear in $nd$ (i.e. the size of the input matrix) for constant $k$. The resulting solution selects exactly $k$ columns and achieves an approximation ratio at most $O(k)$ against the optimal rank $k$ solution given by the SVD, which is comparable to the best known approximation ratio of $(k+1)$. The main idea is that each iteration of the local search can be made to run in linear time by reducing the number of candidates considered via adaptive sampling.", "questions": "Questions\n\n- For the problem of row sampling for $\\ell_p$ subspace approximation, obtaining tight bounds on the number of rows required for a (1+eps) approximation is an open problem under active research (see, e.g., https://dl.acm.org/doi/10.1145/1250790.1250884). Can the combination of local search and adaptive sampling be used to obtain state of the art results for this problem?\n\nMinor comments\n\n- It would be helpful to move the main theorem Theorem 3.9 earlier so that the formal main result can be seen earlier. In particular, the notion of approximation ratio should be clarified before Table 1, since otherwise it is confusing whether the approximation ratio compares against the best rank k solution or the best subset of k columns.\n- The wording of Lemmas 3.7 and 3.8 could be unified for sake of consistency.\n- You can remove the section 7 header.", "limitations": "The authors have addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This work achieves a new point in the trade-off between running time and approximation ratio for the problem of column subset selection. Column subset selection is an important and heavily studied problem and thus this work should be of interest to many researchers, especially those working in numerical linear algebra.", "weaknesses": "The analysis of the algorithm is highly reminiscent of the adaptive sampling analyses from works such as\n\nhttps://faculty.cc.gatech.edu/~vempala/papers/relative.pdf \n\nhttps://dl.acm.org/doi/10.1145/1250790.1250884 \n\nThis includes, for example, the idea of relating the cost difference from the optimum to a bound on the success probability of adaptive sampling (Lemma 3.8) and then boosting with repetition. The only new point here seems to be to use similar ideas to throw away “bad” columns (i.e. use local search) so that the solution size stays at $k$ rather than growing with each iteration. However, this is still a nice and new idea and requires delicate work to make this go through.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive rating and the thoughtful comments. In the following we address the concerns.\n\n**Question 1. For the problem of row sampling for $\\ell_p$ subspace approximation, obtaining tight bounds on the number of rows required for a (1+eps) approximation is an open problem under active research (see, e.g., https://dl.acm.org/ doi/10.1145/1250790.1250884). Can the combination of local search and adaptive sampling be used to obtain state of the art results for this problem?**\n\nResponse: We thank the reviewer for raising this interesting question. For the CSS problem, we utilize a linear-time local search method, overcoming the difficulty of enumerating swap pairs in each local search step. However, we have only provided local search solutions for the CSS problem with the Frobenius norm. For the CSS problem with the $\\ell_p$ norm, it is much more challenging to use local search than the Frobenius norm with the following reasons: (1) Lemma 3.3 becomes invalid because its inequality does not hold for the $\\ell_p$ norm. (2) Lemma 3.4 becomes invalid because it constructs an approximate relationship between the current solution and the SVD.\n\nAs given in [1, 2, 3], $\\ell_p$ norm CSS problem is a special type of $\\ell_p$ norm subspace approximation. Consequently, using local search for $\\ell_p$ subspace approximation has the following difficulties: (1) For the $\\ell_p$ subspace approximation problem, how to analyze the relationship between the solution after adding or removing a column and the optimal solution is challenging. (2) How to get a high-quality initial solution is difficult. The above two difficulties are two major obstacles to design an approximation algorithm for $\\ell_p$ norm subspace approximation by local search. Thus, designing a (1+eps) approximation algorithm for the subspace approximation is much more challenging, which deserves further study.\n\n[1] Deshpande Amit, and Rameshwar Pratap. On Subspace Approximation and Subset Selection in Fewer Passes by MCMC Sampling. arXiv preprint arXiv:2103.11107 (2021).\n\t\t\n[2] Deshpande Amit, and Rameshwar Pratap. One-Pass Additive-Error Subset Selection for $\\ell_p$ Subspace Approximation and $(k, p)$-Clustering.\" Algorithmica 85.10 (2023): 3144-3167.\n\t\n[3]Mahankali  Arvind V., and David P. Woodruff. Optimal $\\ell_1$ column subset selection and a fast PTAS for low rank approximation. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 560-578, 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "i6CDWJuI5u", "reviewer": "Reviewer_wwuR", "summary": "This paper considers the Column Subset Selection (CSS) problem. In this problem the input is an arbitrary $A\\in \\mathbb{R}^{n\\times d}$ and a positive integer $k$ ($k$ is thought to be much smaller than $\\min\\{n,d\\}$). The goal is to output a subset of $k$ columns of $A$ denoted by $S\\in \\mathbb{R}^{n\\times k}$ such that the residual error $\\|A- SS^{\\dagger}\\|_F^2$ is minimized (here $S^{\\dagger}$ is the pseudoinverse of $S$). Previously all except one algorithms for this problem ran in time $\\Omega(\\min\\{nd^2,n^2d\\})$ time with $O(k^2)$ approximation factors. One algorithm of Deshpande and Vempala did run in linear time, i.e. $O(nd)$ time but had $(k+1)!\\sim k^k$ approximation factor. The contribution of this paper is to design an algorithm that achieves linear $O(nd)$ runtime and has $100(k+1)$ approximation ratio.", "questions": "Can the authors please share the experimental details and parameter settings that are used for implementing the algorithms.", "limitations": "Authors have addressed limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper has many strengths. The first is dramatically improving the previous best approximation ratio which was practically infeasible to a reasonable one for small values of $k$. The second is that the authors show the practical feasibility of the algorithm by demonstrating that it is at least 10 times faster than other algorithms across all datasets they consider.", "weaknesses": "I dont see any major weaknesses. One minor weakness is that the experimental section lacks a discussion regarding the parameter settings and experimental setup for the baseline algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive rating and the thoughtful comments. In the following we address the concerns.\n\n**Question 1. Can the authors please share the experimental details and parameter settings that are used for implementing the algorithms.**\n\nResponse: We thank the reviewer for raising this question and apologize for not making it clearer in the paper. Below are the experimental details and parameter settings used in our implementations:\n\n- Algorithm Implementation: The algorithms are implemented using Matlab. For randomized algorithms, we ensured reproducibility by setting random seeds. The implementation details, including the source code, will be made available in a public repository for transparency and reproducibility.\n\n- Algorithms and Parameter Settings: In our experimental evaluation, we consider five distinct algorithms as the following summary:\n  1. The TwoStage algorithm involves two processes: in the first stage, $\\Theta(k\\log k)$ columns are sampled according to the properties of the top-$k$ right singular vectors of the input matrix. In the second stage, exactly $k$ columns are selected via an RRQR factorization of the subset matrix formed by $\\Theta(k\\log k)$ columns. The algorithm includes an oversampling parameter $c$ that controls the constant in $\\Theta(k\\log k)$. We test all integer values of $c$ from 1 to 50 to find the solution with the lowest error. Due to the algorithm involving randomness, we construct 40 submatrices by sampling in the first stage, and then run the RRQR factorization to obtain a solution for each submatrix. Finally, we select the best result from 40 solutions.\n  2. The Greedy algorithm is a deterministic algorithm. The core idea is to iteratively find the column $v$ that minimizes $f(S \\cup v, A)$ for the current solution $S$ until $S$ contains exactly $k$ columns. We run the algorithm once for each varying $k$ value and return the solution.\n  3. The VolumeSampling algorithm is a randomized algorithm. It uses a sampling probability proportional to the volume of the parallelepiped spanned by the $k$-column subset. In VolumeSampling, we use an algorithm for computing the characteristic polynomial of an $n \\times n$ matrix as described in Section 16.6 of [1].\n  4. The ILS algorithm is a heuristic algorithm. It starts by uniformly selecting $k$ columns to construct an initial solution and then improves the quality of the current solution using a heuristic local search operator. We set the number of iterations to $2k$.\n  5. The LSCSS algorithm, given in Algorithm 1 of this paper, uses two-step mixed sampling and local search methods. We set the number of iterations to $2k$, as in the ILS algorithm.\n\n- Experimental Environment: Experiments are conducted on a machine with 72 Intel Xeon Gold 6230 CPUs and 4TB memory. The operating system is Ubuntu 16.04 LTS. The implementation is done in Matlab 2015, with necessary compatibility settings applied.\n\n- Evaluation Metrics: We used the error ratio $\\Vert A - SS^\\dagger A \\Vert_F^2 / \\Vert A - A_k \\Vert_F^2$ to evaluate the performance of the algorithms, where $A_k$ is the best rank-$k$ approximation of $A$. The execution time of each algorithm is recorded to compare computational efficiency.\n\n- Experimental Procedure: We test the TwoStage, VolumeSampling, ILS, and LSCSS algorithms on each dataset 10 times to calculate the average error ratio and running time. Since the Greedy algorithm is deterministic, it is tested only once per dataset, with both its error ratio and running time recorded.\n\n- Experimental Results: We divide the experimental results into two parts. The first part, presented in Tables 3 and 4, contains the error ratios and running times for 8 large datasets. The second part, presented in Tables 6 to 12, contains the detailed results for 16 smaller datasets. The experimental results show that our algorithm is at least 10 times faster than other algorithms on large datasets, achieving the best accuracy on most datasets. Additionally, on small datasets, our algorithm is at least 2 times faster than other algorithms and achieves the best accuracy in most cases.\n\nWe will include these experimental details and parameter settings in the revised version of the paper.\n\n[1] Bürgisser Peter, et al. Algebraic complexity theory, volume 315 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for the positive ratings and thoughtful comments.

Meta-review: This paper provides a new computationally efficient local search method for column subset selection, a central problem in machine learning and randomized numerical linear algebra. It provides an O(k) factor approximation using exactly k column, improving on prior work that either returned more columns (i.e., gave a bicriteria approximation) or obtained a much worse approximation factor. All reviewers felt the paper made progress on this longstanding problem, so should be accepted to the conference. We recommend that the reviewers strengthen their experimental evaluation by  including the comparison to pivoted QR that they ran during the rebuttal period. We would also recommend comparing against the recent “Randomly pivoted Cholesky” method by Chen et al.
Decision: Accept (poster)