PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Column-Based Low-Rank Matrix Reconstruction

Venkatesan Guruswami, Ali Kemal Sinop

arXiv:1104.1732v4cs.DSmath.SP

TL;DR

The paper asks how many columns are needed for their span to approximate a best rank-k approximation of a matrix. It establishes a near-optimal dependence between the number of columns and the approximation bound, with deterministic and faster randomized algorithms for selecting them.

  • Problem

    The paper studies how to select r columns whose span approximates a best rank-k approximation, with the dependence between r and k as a central question.

    Source: §1 · p. 1

  • Method

    The paper bounds column reconstruction using volume sampling and gives deterministic and randomized algorithms for selecting columns.

    Source: §1 · pp. 1–2, §1.2 · p. 3

  • Results

    The dependence between r and k is tight up to lower-order terms for r = o(n), and the paper gives an efficient deterministic algorithm and a faster exact volume-sampling algorithm.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    The stated trade-off between the number of selected columns and approximation quality is optimal up to lower-order terms in the stated regime.

    Source: §1 · pp. 1–2

    The running-time analysis assumes each elementary arithmetic operation takes unit time.

    Source: §5 · p. 6

Abstract

from arXiv · show

We prove that for any real-valued matrix $X \in \R^{m \times n}$, and positive integers $r \ge k$, there is a subset of $r$ columns of $X$ such that projecting $X$ onto their span gives a $\sqrt{\frac{r+1}{r-k+1}}$-approximation to best rank-$k$ approximation of $X$ in Frobenius norm. We show that the trade-off we achieve between the number of columns and the approximation ratio is optimal up to lower order terms. Furthermore, there is a deterministic algorithm to find such a subset of columns that runs in $O(r n m^{\omega} \log m)$ arithmetic operations where $\omega$ is the exponent of matrix multiplication. We also give a faster randomized algorithm that runs in $O(r n m^2)$ arithmetic operations.

1 Introduction

The paper studies how many columns are needed for their span to approximate a best rank-k approximation, and gives near-optimal bounds with deterministic and faster randomized algorithms. Its techniques combine volume sampling, spectral inequalities, and a lower-bound construction.

1 Introduction

  • The paper obtains the best-known dependence between r and k, with the trade-off tight up to lower-order terms when r = o(n).The introduction describes this as resolving an open question and states that the bound is tight up to lower-order terms for r = o(n).Source: §1 · pp. 1–2
  • A deterministic algorithm selects r columns in O(r n m^ω log m) arithmetic operations while attaining the paper's reconstruction bound.The theorem states this running time for positive integers k ≤ r.Source: §1 · pp. 1–2

1.1 Relation to previous work

  • The paper's column-span guarantee and the result in [1] are incomparable because [1] restricts the rank-k approximation to the chosen columns' span, whereas this paper uses the full span.The introduction also extends the lower bound in to the full-column-span model, requiring r = k/ε columns for a (1 + ε − o(1)) approximation.Source: §1.1 · p. 2
  • The paper gives an asymptotically faster exact volume-sampling algorithm, using binary search for a sampled column and recursion on the remaining r − 1 columns.The cited prior exact volume-sampling algorithm used O(r n m^ω log m) arithmetic operations.Source: §1.1 · p. 2

1.2 Our Techniques

  • Schur-concavity of S_{r+1} and majorization yield a spectral inequality used to establish the approximation bound.The lower-bound analysis also shows that the construction in retains its lower bound when the full span of the selected columns is allowed.Source: §1.2 · p. 3

2 Preliminaries and Notation

The preliminaries establish notation for indexed columns and projection matrices, then introduce majorization, Schur-concavity, and symmetric polynomials used in the analysis.

2 Preliminaries and Notation

  • [n] denotes the positive integers at most n; X_C is the matrix of columns indexed by C, and X_Π and X_⊥ project onto the range and null space of X.The text also defines determinant, trace, and σ_i(A) as the i-th largest eigenvalue of A.Source: §2 · pp. 3–4
  • A vector a majorizes b when its ordered partial sums dominate b's and their total sums agree; Schur-concavity reverses that ordering for function values.The preliminaries define a function F as Schur-concave when a ≻ b implies F(a) ≤ F(b).Source: §2 · p. 3
  • S_r(σ) is the r-th symmetric polynomial of a vector, and S_r(A) is defined from the corresponding principal minors of a square matrix.For a matrix A with eigenvalues σ_i, the text states S_r(A) = S_r(σ).Source: §2 · p. 3

3 Bound on ratio of symmetric functions

This section establishes a symmetric-function bound using Schur-concavity and a flow-based proof.

  • The proof constructs a bipartite-graph flow to establish the needed inequality.Source: §3 · p. 4
  • Schur-concavity is used to prove the upper bound on S_{r+1}(σ).Source: §3 · p. 5
  • Lemma 3.1 gives a bound for nonnegative vectors when r ≥ k.Source: §3 · p. 5

4 Bounds on column reconstruction

The section bounds r-column reconstruction error relative to the best rank-k Frobenius error and shows the bound is tight up to lower-order terms when r=o(n).

  • Theorem 4.1 bounds the best r-column reconstruction error relative to the best rank-k approximation error in Frobenius norm.Source: §4 · p. 5
  • For r=o(n), the bound is tight up to lower-order terms in the number of columns chosen.Source: §4 · p. 5
  • The upper bound follows by applying Lemma 3.1 to the eigenvalues of X^T X.Source: §4 · p. 5

5 Fast volume sampling algorithm

The section describes and analyzes Volume-Sample, the sampling algorithm used to prove Theorem 1.2. It details its matrix updates and the per-column selection cost.

  • Theorem 5.1 analyzes Volume-Sample for matrices with m ≤ n and an integer r.Source: §5 · p. 5
  • The algorithm initializes outer-product matrices and updates them after each selected column, with each update taking O(m^2 n) time.Source: §5 · p. 6
  • Choosing one column takes O(m^ω log m log n) time given the table of outer products.Source: §5 · p. 6
  • Theorem 1.2's column-selection performance guarantee follows from the reconstruction upper bound.Source: §5 · p. 6

6 Lower bound for column-selection

This section constructs matrices showing that the upper bound in Theorem 4.1 is nearly tight. The lower-bound construction follows Deshpande and Vempala [6].

6 Lower bound for column-selection

  • Each M(m,δ) has largest eigenvalue m+δ, while its remaining eigenvalues all equal δ.Source: §6 · p. 7
  • The construction makes X^T X block diagonal, with k copies of M(n0,δ) on its diagonal.Here n=n0·k and n0≥r+1.Source: §6 · p. 7
  • For r=o(n) and δ=o(1), the construction gives a lower bound for every r-column choice, even when approximations may use the full chosen-column span.The result is stated for an n×n matrix and r≥k.Source: §6 · pp. 7–8
Loading 1104.1732v4…