Faster Subset Selection for Matrices and Applications

1. Introduction.

• Subset selection chooses at most k columns that preserve rank while minimizing the sampled matrix’s pseudo-inverse norm, in either the spectral or Frobenius norm.The goal is to retain a spectrum comparable to the original matrix despite singular values decreasing when columns are removed.Source: §1 · p. 1
• The problem arises in column-based low-rank approximation [10] [12], feature selection in k-means, experiment design, regression, and sensor selection.The introduction also lists multipoint boundary value problems and rank-deficient linear and nonlinear least squares.Source: §1 · pp. 1–2
• Finding a low-stretch spanning tree in an undirected graph corresponds to the Frobenius-norm version of subset selection.The authors identify this correspondence as new and potentially of independent interest.Source: §1 · p. 2
• The paper studies three aspects of subset selection: algorithms, lower bounds, and applications.The stated initial motivation is the low-stretch spanning-tree connection.Source: §1 · p. 2

1.1.1. Algorithms.

• The five proposed algorithms are considerably faster than previously known algorithms and achieve the same or tighter approximation bounds.The most efficient choice depends on m, n, and k.Source: §1.1.1 · p. 2
• The first two deterministic algorithms greedily remove columns and are especially fast when k is close to m.Algorithm 1 targets the Frobenius norm; Algorithm 2 targets the spectral norm. Their operation counts improve on prior greedy algorithms by a factor of n or, in some cases, n^2, and they avoid the prior restriction that all column subsets of size k or larger be nonsingular.Source: §1.1.1 · p. 2
• 1 + 10α(m − n + 1)^−1 is the approximation bound when k = m − α for the stated range of α.This bound is given for Algorithm 1, which targets the Frobenius norm.Source: §1.1.1 · p. 2
• For k = Ω(n log n), Algorithm 4 uses random column sampling with bounds independent of the matrix’s numerical properties.Its operation count is O(mn^2 + k log k), or O(mn + k log k) when X has orthonormal rows.Source: §1.1.1 · pp. 3–4
• Algorithm 5 uses volume sampling for k = n, with a deterministic approximation bound and a probabilistic operation-count bound.The stated probability guarantee for the operation count is 1 − δ.Source: §1.1.1 · p. 4

1.1.2. Lower Bounds.

• The lower bounds show that some upper bounds of the authors and of de Hoog and Mattheij are optimal up to constant factors, resolving an open question.The lower bounds are developed by relating subset selection to column-based matrix reconstruction and applying existing lower bounds for that problem.Source: §1.1.2 · p. 4

1.1.3. Applications.

• For an undirected graph, the stretch of a tree equals the squared Frobenius norm of the pseudo-inverse of a sampled matrix built from an orthonormal basis for the incidence matrix’s row space.Sampling columns corresponds to sampling graph edges; the resulting tree algorithms are worse than available state of the art.Source: §1.1.3 · p. 5
• The paper applies its subset-selection algorithms to column-based low-rank matrix reconstruction, sparse least-squares solutions, and feature selection in k-means clustering.Source: §1.1.3 · p. 5

1.2.1. Greedy Algorithms.

• The proposed greedy algorithms are at least n times faster than [20] (and n^2 times faster in some cases) and handle any full-rank X by detecting and avoiding rank-deficient removals.The method retains the greedy-removal strategy but selects columns differently from [20].Source: §1.2.1 · pp. 5–6

1.2.2. Rank Revealing Factorizations.

• Rank-revealing approaches provide bounds on the nonzero singular values for subsets of size k ≤ n, while extending them to arbitrary k ≥ n is not obvious.The cited Strong RRQR result is stated for k = n in this discussion.Source: §1.2.2 · p. 6

1.2.3. Incoherent Subset Selection.

• Random column sampling gives competitive bounds for matrices with low coherence, as shown by Gittens [30].Source: §1.2.3 · p. 6

1.2.5. Maximum-volume Subsets.

• Determinant-based sampling preserves earlier bounds in expectation, and polynomial-time implementations yield efficient algorithms with only slightly larger bounds.The cited implementations use O(mn^3) operations and achieve their bounds with high probability.Source: §1.2.5 · p. 7

1.2.6. Computational Complexity of Subset Selection.

• Maximum-volume subset selection is NP-hard, and related large-simplex formulations have been shown NP-hard and exponentially inapproximable.Source: §1.2.5 · p. 7, §1.2.6 · p. 7

1.2.7. Variants of the Subset Selection Problem.

• Related variants allow rescaled columns or linear combinations, with cited spectral-norm methods offering better bounds than this paper’s Problem 1.1; subset selection also appears in regression, low-rank approximation, graph sparsification, and clustering.Source: §1.2.6 · p. 7, §1.2.7 · p. 7

1.2.8. Restricted Invertibility.

• Restricted invertibility selects fewer than n columns to maximize the smallest nonzero singular value, unlike Problem 1.1, which selects at least n columns while maintaining full rank.Polynomial randomized and deterministic algorithms for restricted invertibility are cited.Source: §1.2.8 · pp. 7–8

2.1. Basic Notation; 2.2. Sampling Columns.

• The notation defines X's columns, index sets, and X_S as the columns selected by S, ordered as in X.Source: §2.1 · p. 8, §2.2 · p. 8

2.3. Singular Value Decomposition.

• The thin SVD represents X using its singular values and left and right singular vectors, with the right singular vectors also written as columns of Y = V^T.Source: §2.3 · p. 8

2.4. Moore-Penrose Pseudo-inverse.

• The Moore-Penrose pseudo-inverse is defined from the SVD as X† = VΣ^-1U^T.The section also states identities for pseudo-inverses of matrix products.Source: §2.4 · p. 8

2.5. Column Exchanges and Cramer’s rule.

• The column-exchange notation replaces one column of a matrix, and the section recalls Cramer’s rule for expressing entries of a linear-system solution through determinants.Source: §2.5 · p. 9

2.6. Volume Sampling.

• Volume sampling assigns subsets probabilities based on the determinant of X_S X_S^T, which represents the squared volume associated with the selected rows.The distribution is invariant under left multiplication by a square nonsingular matrix.Source: §2.6 · p. 9

2.7. Other Known Results.

• The preliminaries invoke Cauchy-Binet and an eigenvalue identity expressing the kth elementary symmetric function as a sum of principal minors.Source: §2.7 · p. 10

• The algorithm follows the greedy removal strategy of but accelerates it by exploiting the SVD and efficient updates.Source: §3 · p. 10
• It detects removals that would make the matrix rank deficient and avoids them.Source: §3 · p. 10
• The algorithm achieves the same approximation bounds as, whose proof does not apply because it implicitly assumes every single-column removal preserves rank.Source: §3 · p. 10

3.1. Deterministic Greedy Removal (Frobenius norm).

• Starting from all m columns, the algorithm performs m-k removals and maintains an SVD of each current subset.It needs only the singular-value matrix and right singular vectors for the update.Source: §3.1 · pp. 10–11
• At each step it removes a column minimizing the pseudo-inverse Frobenius norm among single-column removals that preserve rank.Source: §3.1 · pp. 11, 12, 14
• Under inexact arithmetic, the test ∥y_h∥2 < 1 can hold even when deleting that column makes the system rank deficient, so the implementation uses a threshold τ.Source: §3.1 · p. 12
• For full-rank X and n ≤ k ≤ m, Theorem 3.1 deterministically constructs a subset of cardinality k with a norm bound.Source: §3.1 · p. 12
• With orthonormal rows, the deterministic greedy algorithm runs in O(mn(m-k)) operations.Source: §3.1 · pp. 12, 14
• Algorithm 2 applies Algorithm 1 to V^T, where V contains X’s top n right singular vectors, trading a slightly worse Frobenius bound for a slightly better spectral bound.Source: §3.1 · p. 14

3.2. Deterministic Greedy Removal (spectral norm).

• The analysis treats log₂ ε as constant, noting machine precision is typically about 10⁻¹⁶.This simplification is used in discussing the operation count.Source: §3.2 · p. 14
• For X ∈ R^{n×m} with m>n and rank(X)=n, and n≤k≤m, Algorithm 2 deterministically returns S⊆[m] of size k after computing the top n right singular vectors and running Algorithm 1 on V^T.Source: §3.2 · p. 15
• For X with orthonormal rows, the operation count is O(mn(m −k)).Source: §3.2 · p. 15

3.3. Deterministic Greedy Selection.

• The construction builds the set iteratively from the empty set using a deterministic algorithm generalized from earlier work [10, 4].Source: §3.3 · p. 15
• The dual-set procedure uses two equal-cardinality decompositions of identity matrices and produces nonnegative weights, at most k of them nonzero.Source: §3.3 · p. 15
• DualSet controls the smallest singular value for sampled vectors from one set and the largest singular value for the second set simultaneously.The algorithm applies it to the right singular vectors of X and the standard basis, then returns indices with nonzero weights.Source: §3.3 · p. 16
• Algorithm 3 deterministically constructs a subset of at most k columns with bounds for both the Frobenius and spectral norms.The supplied theorem passages do not expose the bound values or operation count.Source: §3.3 · p. 16

3.4. Randomized Selection.

• Computing the sampling probabilities by SVD or QR takes cubic time, while sub-cubic approximations are proposed as possible future improvements with a small increase in the approximation bound.Source: §3.4 · p. 17
• The method independently samples k indices with replacement, using non-uniform probabilities related to column leverage scores.The probabilities are adjusted so that no column receives a probability that is too small.Source: §3.4 · pp. 17–18
• With probability at least 1 − δ, Algorithm 4 returns at most k columns with bounds for both the Frobenius and spectral norms.The theorem gives operation count O(mn² + k log k), with the sample-size condition k ≥ min(⌈32n ln(2n/δ)⌉, m).Source: §3.4 · p. 18
• When X has orthonormal rows, the operation count is O(mn + k log k).Source: §3.4 · p. 18

3.5.1. Subset Selection and Determinants.

• For a full-rank selected subset, Lemma 3.8 connects the Frobenius norm of the pseudoinverse to determinants of X_S X_Sᵀ and row-deleted matrices.When the selected subset has exactly n columns, the passage also gives a determinant-based inequality involving column replacements.Source: §3.5.1 · p. 20

3.5.2. Random Subsets Chosen via Volume Sampling.

• Finding a maximum-volume subset is NP-hard and exponentially hard to approximate, motivating the use of randomization.Source: §3.5.2 · p. 22
• Volume sampling yields expected pseudo-inverse norm bounds, while subsets with rank-deficient selected columns receive zero sampling probability.The cited result treats subsets sampled with probability proportional to their volume.Source: §3.5.2 · pp. 22, 25

3.5.3. Volume Sampling Subset Selection.

• The described efficient determinant-based sampler draws n columns using O(n³m) operations, but the authors leave efficient volume sampling for arbitrary k ≥ n as an open question.Source: §3.5.3 · p. 25
• For X ∈ R^{n×m} with m ≥ n and rank(X)=n, and η>0, Algorithm 5 outputs a set S of cardinality n; for every 0<δ<1, it terminates after O operations with probability at least 1−δ.Source: §3.5.3 · p. 26

4. Lower Bounds.

• The section establishes worst-case lower bounds for subset selection under both the spectral and Frobenius norms.The bounds apply to full-rank matrices and eligible subsets of k columns.Source: §4 · p. 26, §4.1 · p. 27, §4.2 · p. 28

4.1. Lower bound for the spectral norm version of the subset selection problem.

• As α → 0, the spectral-norm lower bound is m/k − 1; the deterministic upper bound matches asymptotically when k = (1 + Ω(1))n, but a gap remains when k = (1 + o(1))n.The other listed algorithmic upper bounds are asymptotically slightly worse in the stated matching regime.Source: §4.1 · p. 27

4.2. Lower bound for the Frobenius norm version of the subset selec-

• As α → 0 with k = O(n), the Frobenius-norm lower bound is m/k − O(1); upper bounds match asymptotically when k = (1 + Ω(1))n, but gaps remain near n and for k = ω(n).The authors suspect the k = ω(n) gap reflects looseness in the lower bound, but were unable to prove a tighter one.Source: §4.2 · p. 28

5. Low-stretch Spanning Trees and Subset Selection.

• For a spanning tree T, its stretch equals the squared Frobenius norm of the pseudoinverse of the corresponding sampled matrix; full-rank subsets of n − 1 columns correspond to spanning trees.This connects minimizing tree stretch to Frobenius-norm subset selection.Source: §5 · pp. 29–30

5.1. Low-stretch spanning trees via the greedy removal algorithm.

• Greedy removal yields an O(n)-edge subgraph with pseudoinverse Frobenius norm O(m), although some O(n)-edge subgraphs have stretch Ω(m log(n)).Experiments on complete graphs with 10–50 vertices found stretch about 0.6m log2 n with equal weights and about 0.3m log2 n with random weights; the authors describe them as preliminary and not exhaustive.Source: §5.1 · p. 31

5.2. Maximum weight spanning trees and maximum volume subsets.

• A maximum-volume column subset corresponds to a maximum-weight spanning tree, whose stretch is bounded by (n − 1)(m − n + 2).The paper notes that a maximum-weight spanning-tree algorithm can efficiently find the maximum-volume subset for edge-incidence matrices.Source: §5.2 · p. 31

5.3. Low-stretch spanning trees via volume sampling.

• Volume sampling corresponds to sampling trees with probability proportional to the product of their edge weights, but the resulting stretch bound is strict because not every subgraph is a tree.The authors conjecture that the bound is pessimistic and leave its refinement for future work.Source: §5.3 · p. 32, §5.2 · p. 32

5.4. Towards better bounds for low-stretch spanning trees.

• For the considered orthonormal-row matrices, the Frobenius-norm quantity equals the number of full-rank bases reachable by replacing one column; singular subsets can make the universal bound loose.In complete graphs, most n − 1-edge subsets do not form a tree or yield a full-rank sampled matrix.Source: §5.4 · pp. 32–33

6.1. Column-Based Low-Rank Matrix Reconstruction.

• For column-based reconstruction, the method selects k columns using the top r right singular vectors of A and the algorithm of Corollary 3.3.The resulting subset is used to construct the approximation within the selected columns’ span.Source: §6.1 · p. 33
• The column-based reconstruction algorithm is deterministic, with an operation count of TSV D + O(mr(m −k)); its approximation bound is slightly worse than [10] but can require fewer operations.The operation-count advantage depends on the input matrix size.Source: §6.1 · p. 33

6.2. Sparse Solutions to Least-squares Regression Problems.

• The sparse least-squares application compares a k-sparse solution with the truncated-SVD regularized solution for r ≤k.The motivation notes that least-squares minimizers may be non-unique or have large norm, motivating regularization.Source: §6.2 · pp. 33–34
• For sparse least squares, the deterministic method uses Corollary 3.3 to select k coordinates and forms a solution with at most k nonzeros.Its bound replaces the Frobenius residual term in with a term involving m −k and σr+1(A); it may be better when k approaches m.Source: §6.2 · p. 34

6.3. Feature Selection in k-Means Clustering.

• For k-means feature selection, Corollary 3.3 yields a deterministic unsupervised algorithm that selects features without rescaling, with an approximation bound comparable to.The paper omits the algorithmic details.Source: §6.3 · p. 34

• Open questions include whether Frobenius-norm subset selection is NP-hard, whether upper and lower bounds can be brought closer, and whether existing methods extend to arbitrary k or can be derandomized.The questions concern Strong Rank Revealing QR, polynomial volume sampling for short-fat matrices, and the algorithm of Theorem 3.11.Source: §7 · p. 34