PaperlayerView exact revision on arXiv

Source-linked AI summary

A DEIM Induced CUR Factorization

D. C. Sorensen, M. Embree

arXiv:1407.5516v2math.NA

TL;DR

The paper addresses how to construct accurate, data-representative CUR approximations for large nearly low-rank matrices. It selects rows and columns with DEIM, analyzes the resulting error relative to the best rank-k approximation, and proposes a one-pass incremental QR approach for large-scale singular-vector computation. The method is deterministic and its accuracy is controlled by the neglected singular value and conditioning of selected singular-vector submatrices.

  • Problem

    CUR approximations should provide low-rank representations while retaining representative rows and columns, especially for large nearly low-rank data.

  • Method

    DEIM independently selects CUR rows and columns from approximate leading singular vectors, while U is constructed through projection-based CUR formulas.

  • Results

    The accuracy of DEIM-CUR is bounded relative to the best rank-k approximation, with factors governed by σk+1 and conditioning constants ηp and ηq.

  • Takeaways & Limitations

    The resulting CUR procedure is deterministic, uses few parameters, and can exploit a one-pass incremental QR approximation for large-scale problems.

  • Takeaways & Limitations

    DEIM may select only one index among several nearly equal residual entries, and incremental QR is proposed for rapidly decaying singular values.

Abstract

from arXiv · show

We derive a CUR matrix factorization based on the Discrete Empirical Interpolation Method (DEIM). For a given matrix $A$, such a factorization provides a low rank approximate decomposition of the form $A \approx C U R$, where $C$ and $R$ are subsets of the columns and rows of $A$, and $U$ is constructed to make $CUR$ a good approximation. Given a low-rank singular value decomposition $A \approx V S W^T$, the DEIM procedure uses $V$ and $W$ to select the columns and rows of $A$ that form $C$ and $R$. Through an error analysis applicable to a general class of CUR factorizations, we show that the accuracy tracks the optimal approximation error within a factor that depends on the conditioning of submatrices of $V$ and $W$. For large-scale problems, $V$ and $W$ can be approximated using an incremental QR algorithm that makes one pass through $A$. Numerical examples illustrate the favorable performance of the DEIM-CUR method, compared to CUR approximations based on leverage scores.

1 Introduction

The paper introduces a deterministic DEIM-based CUR factorization that selects representative columns and rows from a low-rank SVD. It analyzes accuracy relative to the best rank-k approximation and proposes scalable singular-vector approximation for large matrices.

  • DEIM-CUR construction: DEIM selects CUR columns and rows independently from the leading left and right singular vectors of A.The resulting factorization uses C=A(:,q), R=A(p,:), and a constructed k×k matrix U.
  • Motivation: CUR preserves sparse and representative data structure because C and R are actual columns and rows of A.This contrasts with dense singular-vector factors and retains properties such as sparsity, nonnegativity, or integer values.
  • Motivation: The DEIM-CUR columns better represent the two-distribution example than the first two singular vectors.The singular vectors fail to reflect the data’s different principal axes, whereas the selected columns provide a better overall representation.
  • Related work: Leverage-score sampling can be unstable when small singular values make singular vectors sensitive to perturbations.Choosing how many leading singular vectors to use for leverage scores can therefore be somewhat ad hoc.
  • Contributions: The method is deterministic, uses few parameters, and is supported by an error analysis applicable to a broad class of CUR factorizations.The analysis improves bounds involving the row and column selection constants ηp and ηq.
  • Extensions: DEIM can also select only columns or only rows for interpolatory decompositions with potentially better-conditioned central factors.These alternatives are useful when applications care primarily about key columns or rows rather than an explicit CUR factorization.

2 CUR Factorization

The CUR construction selects columns and rows, then forms U so successive projections onto their column and row spaces approximate A. Orthogonal-projector choices make both projection steps optimal in 2-norm error, supporting strong approximation properties.

  • Selection: For nearly low-rank A, the method extracts k columns C and k rows R using index vectors q and p.The selected indices are guided by the leading rank-k singular vectors or an approximation to them.
  • Exact-rank construction: For exact rank-k A with full-rank C and R, any Y and Z satisfying Y^T C=RZ=I produce U=Y^T AZ and exactly recover A.Different valid choices of Y and Z can yield different central factors U.
  • Interpolatory construction: The interpolatory construction chooses Y^T=(P^T C)^-1P^T and Z=Q(RQ)^-1 when the selected intersection is invertible.This choice makes CUR match the selected columns and rows of A.
  • Orthogonal projection: Using left and right inverses of C and R makes CY^T and (ZR)^T orthogonal projectors.The resulting CUR approximation first projects A onto Ran(C), then projects the result onto the row space of R.
  • Orthogonal projection: Both projection steps are optimal in 2-norm error, which is the primary source of the approach’s approximation quality.This orthogonal-projection construction improves the theoretical approximation properties compared with simpler CUR choices.
  • Complexity: Given the leading k singular vectors, DEIM index selection costs mk and nk, while constructing the rank-k SVD dominates overall complexity.The singular values are represented by S=diag(σ1,σ2,…,σk).

3 DEIM

DEIM selects row and column indices independently by processing singular vectors sequentially and choosing interpolation points from residuals. The resulting interpolatory projectors match vectors at selected entries and yield distinct, nonduplicated indices under full-rank assumptions.

  • Selection procedure: DEIM applies the point-selection procedure independently to the singular-vector matrices V and W, producing row indices p and column indices q.The procedure is a discrete variant of the Empirical Interpolation Method.
  • Interpolatory projectors: The interpolatory projector P = V(P^T V)^-1P^T reproduces any vector’s entries at the selected indices.For any x, the projected vector Px satisfies (Px)(p) = x(p).
  • Selection procedure: At each step, DEIM removes the current singular vector’s interpolatory projection and selects the largest remaining-magnitude residual entry.The first index is the largest-magnitude entry of v1; later indices are selected from residuals after projection onto earlier vectors.
  • Relation to LU: DEIM’s sequential selection is equivalent to index selection in partially pivoted LU, but it retains the original singular-vector basis.Unlike traditional LU, DEIM uses no explicit row interchanges and does not replace basis vectors with residuals.
  • Limitation: A potential limitation is that only one index is chosen when several residual entries have nearly equal magnitudes.Large entries omitted at one step may never be selected if they are not prominent in later residual vectors.
  • Selection guarantees: Full column rank of V guarantees that the selected submatrices P_j^T V_j are nonsingular at every step.This ensures the interpolatory projectors exist throughout the sequential selection process.

4 CUR Approximation Properties

The CUR analysis bounds approximation error using interpolatory projections associated with selected rows and columns. CUR is within a conditioning-dependent factor of the optimal rank-k approximation, and the analysis also extends to broader CUR schemes and approximate singular vectors.

  • General CUR analysis: The analysis applies to any CUR factorization with full-rank C and R when U = C^†AR, not only DEIM-CUR.Thus the error framework can assess multiple row and column selection procedures.
  • Projection bounds: The interpolatory projectors P and Q operate on the left and right of A using selected rows and columns and the dominant singular vectors.Their error constants depend on the inverses of the sampled singular-vector submatrices.
  • Projection bounds: ηq σk+1 and ηp σk+1 bound the orthogonal projection errors onto the selected column and row spaces.These bounds transfer the interpolatory projection estimates to the orthogonal projections associated with C and R.
  • CUR error theorem: Theorem 4.1 sets U = C^†AR and bounds CUR error by a factor ηp + ηq times the optimal rank-k error.The conditioning of the selected k rows of the dominant singular vectors controls the approximation quality.
  • Error assessment: The same framework supports an a posteriori O(k^3) computation of ηp and ηq when the relevant singular vectors are available.These constants can guide adjustment of k or the point-selection process.
  • Approximate singular vectors: With approximate orthonormal singular vectors, the optimal-error term is replaced by the corresponding approximate-SVD projection errors.The conditioning factors are computed using the approximate V and W; probabilistic selection bounds can also be inserted into the theorem.
  • Empirical behavior: Numerical examples report that DEIM error constants are often modest, although worst-case bounds may grow substantially with k.The examples compare DEIM-CUR with several leverage-score-based factorizations.

5 Incremental QR Factorization

An incremental QR algorithm approximates the leading singular vectors for large matrices while making one pass through A. It controls rank through internal pivoting and deletion of low-contribution factors, with an associated approximation-error analysis.

  • Motivation and construction: For large-scale matrices, the method uses an incremental QR approximation to obtain leading singular vectors instead of forming a full SVD.The approach targets settings where dense economy-sized SVDs are unsuitable.
  • Approximate SVD: Taking the dense SVD of the triangular factor R and setting V = Q V̂ produces an approximate SVD basis for A.The resulting approximate singular vectors can be used in the CUR analysis.
  • Rank control: The retained rank grows when no deflation occurs and is reduced when the minimum-norm row satisfies the truncation criterion.The procedure tracks row norms of R to decide whether deflation is required.
  • Algorithm: Internal pivoting and threshold truncation enable the incremental QR method to make one pass through A.This distinguishes it from approaches using column pivoting and connects it to earlier one-pass algorithms.
  • Algorithm: The algorithm orthogonalizes columns sequentially and maintains A ≈ QR while controlling factor rank through update-and-delete steps.A row of R and the corresponding column of Q are deleted when their contribution is sufficiently small.
  • Error analysis: The resulting QR approximation has an inductive Frobenius-error bound that accounts for the number of deletions and the tolerance.The analysis follows the factorization through each update and deletion.
  • Extensions: The approximate QR factorization can also support leverage-score approximation, with its tolerance affecting leverage-score accuracy.The algorithm may additionally stop based on the residual factor norm or process only sampled columns.

6 Computational Examples

Computational examples show that DEIM-CUR generally produces more accurate approximations than leverage-score-based CUR, often closely tracking the optimal error, while remaining robust to approximate singular vectors. Across sparse random, text, and genetics examples, DEIM-CUR also yields useful row and column selections, with QR-CUR offering similar accuracy but less consistent error constants.

  • Sparse nonnegative matrix (6.1): DEIM-CUR has better interpolation constants and more accurate approximations than leverage-score selection for matrix (6.1).Using only ten singular vectors improves leverage-score interpolation constants and approximation accuracy relative to using all singular vectors.
  • Sparse nonnegative matrix (6.1): Random leverage-score sampling performs similarly to deterministic LS (10) across ten trials, but remains worse than DEIM-CUR.The trials select 30 rows and columns using probabilities derived from the leading ten singular vectors.
  • Approximate singular vectors: Approximate singular vectors preserve DEIM-CUR accuracy: Incremental QR changes the relative error by at most 9.27%, while one randomized-SVD application changes it by at most 10.45%.Incremental QR selects at most 3 different rows and 2 different columns for k = 1, ..., 30; one randomized-SVD application can change 20 of 30 row indices and 3 of 30 column indices at k = 30.
  • Approximate singular vectors: Two randomized-SVD applications make the DEIM indices nearly identical to the exact choices and limit the maximum relative discrepancy to 2.21%.At k = 30, no row indices and 2 of 30 column indices differ from the exact selections.
  • DEIM-CUR versus QR-CUR: Across 100 sparse random matrices, DEIM-CUR and QR-CUR have similar approximation errors, but DEIM-CUR produces smaller and more consistent η_p values.The η_q values are qualitatively similar and about an order of magnitude smaller for both methods.
  • Sparse nonnegative matrix (6.2): For matrix (6.2), DEIM-CUR again delivers excellent approximations, whereas highest-leverage-score selection performs substantially worse.The LS (10) error constant η_q shows significant jumps where the normalized approximation error is large.
  • TechTC data: On the TechTC data, DEIM-CUR is typically more accurate than leverage-score selection, although all methods produce errors roughly twice σ_k+1.DEIM-selected columns include geographic terms such as “evansville,” “florida,” “miami,” and “indiana.”

7 Conclusions

The paper presents DEIM-CUR as a deterministic CUR approach with an error bound tied to the best rank-k approximation and favorable numerical performance against leverage-score selection.

  • DEIM provides simple, deterministic index selection for constructing CUR factorizations.
  • The resulting rank-k CUR error can be bounded using σ_k+1, the error of the best rank-k approximation to A.
  • The 2-norm analysis applies to CUR approximations using the optimal central factor U = C^†AR.
  • An incremental approximate QR method can compute dominant singular vectors efficiently in one pass for data sets with rapidly decaying singular values.
  • Numerical examples show that DEIM-CUR can deliver very good low-rank approximations compared with row selection based on dominant leverage scores.
Loading 1407.5516v2…