PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient volume sampling for row/column subset selection

Amit Deshpande, Luis Rademacher

arXiv:1004.4057v1cs.DS

TL;DR

The paper addresses the lack of efficient algorithms for volume sampling, which selects row subsets according to squared geometric volumes and supports low-rank approximation. It develops exact and approximate sampling algorithms, including deterministic row selection, with exact sampling in O(kmn^ω log n) arithmetic operations and a faster near-input-linear variant for small k. These methods provide approximation and lower-bound results for row/column subset selection, while SVD-based acceleration remains limited by inexactness and unclear error propagation.

  • Problem

    Before this work, no efficient algorithm was known for exact volume sampling, an open problem connected to row-subset selection and low-rank approximation.

  • Method

    The paper develops polynomial-time exact volume sampling, a faster (1 + ε)-approximate variant, and conditional-expectations derandomization for row-subset selection.

  • Results

    Exact volume sampling runs in O(kmn^ω log n) arithmetic operations, while the approximate variant has the stated near-input-linear complexity for small k and supports low-rank approximation results.

  • Takeaways & Limitations

    Efficient volume sampling yields algorithmic row selection with the paper’s Frobenius-norm guarantee in expectation and deterministically through conditional expectations.

  • Takeaways & Limitations

    The SVD-based practical alternative cannot be computed exactly, and the paper does not establish how its errors propagate through the many SVD computations used by the algorithm.

Abstract

from arXiv · show

We give efficient algorithms for volume sampling, i.e., for picking $k$-subsets of the rows of any given matrix with probabilities proportional to the squared volumes of the simplices defined by them and the origin (or the squared volumes of the parallelepipeds defined by these subsets of rows). This solves an open problem from the monograph on spectral algorithms by Kannan and Vempala. Our first algorithm for volume sampling $k$-subsets of rows from an $m$-by-$n$ matrix runs in $O(kmn^ω \log n)$ arithmetic operations and a second variant of it for $(1+ε)$-approximate volume sampling runs in $O(mn \log m \cdot k^{2}/ε^{2} + m \log^ω m \cdot k^{2ω+1}/ε^{2ω} \cdot \log(k ε^{-1} \log m))$ arithmetic operations, which is almost linear in the size of the input (i.e., the number of entries) for small $k$. Our efficient volume sampling algorithms imply several interesting results for low-rank matrix approximation.

1 Introduction

Volume sampling selects row subsets according to their geometric volume and connects this selection strategy to low-rank approximation and feature selection in large datasets. It addresses settings where users need a small subset of informative features rather than dense linear combinations.

  • Volume sampling: Volume sampling picks k-row subsets with probabilities proportional to the squared volumes of the simplices they define with the origin.It is equivalent to sampling subsets according to corresponding k-by-k principal minors of a positive semidefinite matrix.
  • Applications: Row/column-subset selection seeks small subsets of features or rows that capture dominant structure in large data matrices.Applications include search, microarray experiments, computer vision, and data mining.
  • Motivation: PCA and random projection typically output singular or random vectors that are linear combinations of many feature vectors, rather than selecting individual features.This motivates subset-selection methods for applications such as identifying genes associated with a disease.

2 Row/column-subset selection and volume sampling

The section introduces row-subset selection and volume sampling as a route to low-rank approximation, then presents efficient exact, approximate, and deterministic algorithms. It also states associated approximation guarantees, a near-matching spectral-norm lower bound, and practical limitations of SVD-based acceleration.

  • Row/column-subset selection: Row-subset selection asks whether k rows can span a projection nearly as good as the best rank-k singular-vector subspace.The target comparison is projection onto span(v_i : 1 ≤ i ≤ k), where the v_i are right singular vectors.
  • Volume sampling: Volume sampling selects k-row subsets with probabilities proportional to their volume-based weights, and projection onto the selected-row span gives a (k + 1)-approximation to the nearest rank-k matrix in Frobenius norm.The projected matrix is formed by projecting every row onto span(a_i : i ∈ S).
  • Prior gap: Before this work, no efficient exact volume-sampling algorithm was known; the prior k!-approximate method could provide only a (k + 1)! guarantee through the existing theorem.Finding an efficient algorithm was identified as an open problem in Kannan and Vempala’s monograph.
  • Our results: The main result is a polynomial-time exact volume-sampling algorithm using O(kmn^ω log n) arithmetic operations.The randomized algorithm outputs a random k-subset according to volume sampling for 1 ≤ k ≤ rank(A).
  • Practical limitation: SVD-based characteristic-polynomial updates offer a nearly-exact practical alternative, but SVD computation is inexact and its error propagation through repeated computations is unknown.If an m-by-n SVD costs T_svd, the resulting algorithm takes O(kT_svd + kmn^2) arithmetic operations.
  • Our results: Conditional expectations derandomize the sampling-based selection guarantee, yielding a deterministic row-subset algorithm with the same O(kmn^ω log n) complexity.The guarantee is established first in expectation for efficient volume sampling and then made deterministic.
  • Bounds: The spectral-norm lower bound almost matches the upper bound’s dependence on n, while Theorem 2’s row-subset result has a matching lower bound and is existential before algorithmic selection.The section explicitly identifies Theorem 2’s guarantee as best possible and presents a separate almost-matching spectral-norm lower bound.

3 Preliminaries and notation

The paper establishes notation for row submatrices, projections, singular values, characteristic polynomials, and determinant coefficients. It assumes m ≥ n and uses fast characteristic-polynomial computation as an algorithmic ingredient.

  • For A ∈ R^m×n, a_i denotes row i, A_S the submatrix indexed by S, and π_S(A) projects every row onto span(S).
  • The residual A − π_S(A) projects every row orthogonally to span(S).
  • The analysis assumes m ≥ n, partly to justify working with A^T A and because random projection can make n small.
  • Singular values are the positive square roots of the eigenvalues of A A^T, equivalently A^T A up to zero values.
  • For k ≤ n, characteristic-polynomial coefficients of A A^T can be replaced by corresponding coefficients of A^T A.
  • An n-by-n characteristic polynomial can be computed in O(n^ω log n) arithmetic operations.

S ) det(DT DT

The determinant identity is proved by reducing to the rows indexed by S ∪ T and separating singular and invertible cases for the S block.

  • If the S block is singular, both sides of the determinant equality are zero.
  • If the S block is invertible, block Gaussian elimination transforms the expression into a block-triangular determinant factorization.

S ) det(CT CT

This section invokes projection formulas and the matrix determinant lemma to support determinant manipulations under rank-1 updates.

  • Projecting the rows of K onto the row-space of L can be expressed algebraically through a projection formula.
  • The determinant argument is completed after applying the projection representation to the relevant matrices.
  • The matrix determinant lemma describes how determinants change under a rank-1 update for invertible M and vectors u, v.

4 Efficient volume sampling algorithms

The paper develops exact and approximate volume-sampling algorithms by expressing conditional probabilities through characteristic-polynomial coefficients, then accelerates them using Gram matrices, rank-1 updates, random projection, or SVD.

  • Algorithm outline: The basic algorithm iteratively computes row weights, samples one row proportionally, and projects the remaining matrix orthogonally to that row.
  • Algorithm outline: Conditional probabilities in extended volume sampling are represented using norms and characteristic-polynomial coefficients of residual matrices.
  • Exact sampling: The iterative algorithm samples each k-subset with probability proportional to its determinant and, in its initial implementation, costs O(km^3n + km^{ω+1} log m).
  • Exact sampling: Using B^T B and rank-1 updates computes all marginal probabilities in O(mn^ω log n) per round, yielding O(kmn^ω log n) exact volume sampling.
  • SVD-based sampling: An SVD-based subroutine uses rank-1 characteristic-polynomial updates to obtain nearly-exact volume sampling in O(kT_svd + kmn^2).
  • Approximate sampling: Random projection reduces dimension before volume sampling, producing (1 + ε)-approximate volume sampling with the stated projection and implementation costs.

5 Derandomized row/column-subset selection

The paper derandomizes volume sampling for row/column-subset selection using conditional expectations, producing a deterministic algorithm with the same approximation guarantee and efficient running time.

  • 5 Derandomized row/column-subset selection: Conditional expectations convert volume sampling into a deterministic row-subset selection algorithm.At each step, the algorithm computes conditional expectations for candidate rows and selects the row minimizing that expectation.
  • 5 Derandomized row/column-subset selection: Characteristic polynomials provide an efficient way to compute the conditional expectations needed for derandomization.The conditional expectations correspond to coefficients of characteristic polynomials associated with projected matrices.
  • 5 Derandomized row/column-subset selection: The algorithm outputs a subset S of k rows from A for 1 ≤ k ≤ rank(A).It initializes S as empty and iteratively adds one selected row while projecting the remaining matrix orthogonally.
  • 5 Derandomized row/column-subset selection: O(kmn^ω log n) arithmetic operations give the deterministic algorithm’s running time.The theorem states this complexity for producing the selected k-row subset.
  • 5 Derandomized row/column-subset selection: The spectral-norm guarantee follows from the Frobenius-norm guarantee using norm relations and rank(A − A_k) ≤ n − k.The proof transfers the approximation guarantee between norms rather than establishing the spectral case independently.

6 Lower bound for rank-1 spectral approximation using one row

The paper constructs a matrix showing that selecting one row can be intrinsically weak for spectral-norm rank-1 approximation, establishing an almost matching lower bound.

  • 6 Lower bound for rank-1 spectral approximation using one row: A matrix A ∈ R^{n×(n+1)} is constructed to lower-bound row/column-subset selection using one row.The construction evaluates the best rank-1 approximation whose rows lie in the span of a fixed row.
  • 6 Lower bound for rank-1 spectral approximation using one row: Projecting rows onto the span of any single row yields only an Ω(√n)-approximation in spectral norm.The bound applies to the nearest rank-1 matrix to A under the one-row span restriction.
  • 6 Lower bound for rank-1 spectral approximation using one row: The Ω(√n) lower bound extends to general k using a matrix with k block-diagonal copies of the rank-1 construction.The paper states that the rank-1 example can be generalized through block-diagonal replication.
  • 6 Lower bound for rank-1 spectral approximation using one row: The best rank-1 approximation to A has spectral residual σ2(A) = ε.The construction’s singular-value analysis identifies ε as the error of the unrestricted nearest rank-1 approximation.

7 Discussion

The discussion identifies practical algorithm design and connections to determinantal sampling as directions for future work, while noting that numerical stability remains unanalyzed.

  • 7 Discussion: The paper proposes exploring relationships between its algorithmic ideas, determinantal sampling, and random spanning-tree generation.This is presented as a future investigation rather than an established equivalence.
  • 7 Discussion: Practical counterparts of the presented algorithms remain an open direction because their numerical stability is not analyzed.The discussion specifically calls for practical versions and identifies numerical stability as missing analysis.
  • 7 Discussion: The discussion also asks whether random walks can yield an efficient volume-sampling algorithm.The question is motivated by MCMC and random-walk methods for generating random spanning trees.
Loading 1004.4057v1…