PaperlayerView exact revision on arXiv

Source-linked AI summary

Literature survey on low rank approximation of matrices

N. Kishore Kumar, Jan Shneider

arXiv:1606.06511v1math.NA

TL;DR

Constructing low-rank approximations is costly for very large matrices because classical methods require O(n^3) operations and randomized methods are not linear in n. This paper reviews deterministic, randomized, and cross/skeleton techniques, highlighting cross/skeleton methods' linear complexity in n.

  • Problem

    Low-rank approximation methods can be prohibitively expensive for large matrices, motivating techniques with lower or linear complexity in n.

  • Method

    The paper surveys classical deterministic algorithms, randomized algorithms, and cross/skeleton approximation techniques, with references to many methods.

  • Results

    Cross/skeleton approximation techniques provide low-rank approximations with complexity linear in n, including an algorithm with O(k^2n) complexity when k ≪ n.

  • Takeaways & Limitations

    Cross/skeleton methods are presented as practical alternatives for handling really large data because they can achieve linear complexity in n.

  • Takeaways & Limitations

    Cross/skeleton accuracy depends on choosing a well-conditioned intersection submatrix, while finding a maximum-volume submatrix is NP-complex and infeasible even for moderate dimensions.

Abstract

from arXiv · show

Low rank approximation of matrices has been well studied in literature. Singular value decomposition, QR decomposition with column pivoting, rank revealing QR factorization (RRQR), Interpolative decomposition etc are classical deterministic algorithms for low rank approximation. But these techniques are very expensive $(O(n^{3})$ operations are required for $n\times n$ matrices). There are several randomized algorithms available in the literature which are not so expensive as the classical techniques (but the complexity is not linear in n). So, it is very expensive to construct the low rank approximation of a matrix if the dimension of the matrix is very large. There are alternative techniques like Cross/Skeleton approximation which gives the low-rank approximation with linear complexity in n . In this article we review low rank approximation techniques briefly and give extensive references of many techniques.

1 Introduction

Low-rank approximation seeks compact matrix representations while controlling information loss. The survey reviews deterministic, randomized, and cross/skeleton techniques, emphasizing methods suited to very large data.

  • Low-rank approximation represents a matrix with lower rank to obtain a more compact representation with limited information loss.
  • Classical methods such as SVD, pivoted QR, RRQR, and interpolative decomposition require O(mnk) operations and at least k passes through the input matrix.
  • Randomized algorithms reduce data-access requirements to one or two passes by constructing an approximate range basis from sampled rows or columns and projecting the matrix onto it.
  • Cross/skeleton methods construct rank-k approximations using O(k^2(m + n)) operations and only k(m + n) matrix entries.
  • The survey presents classical deterministic algorithms, randomized algorithms, and cross/skeleton techniques, whose computational complexity is derived as linear in n.
  • Frobenius and spectral norms provide error measures used to assess matrix approximations.

2.1 Singular value decomposition

Singular value decomposition factors a rectangular matrix into orthogonal factors and ordered singular values. Truncating the decomposition yields a rank-k approximation using the leading singular components.

  • SVD factors A ∈ R^m×n into U, S, and V^T without requiring a square matrix.
  • U and V are orthogonal, while S is rectangular diagonal with singular values ordered as σ1 ≥ σ2 ≥ ··· ≥ σn ≥ 0.
  • The rank of A equals its number of nonzero singular values, and truncation forms a rank-k approximation by retaining the leading singular components.
  • The truncated approximation Ak is the projection of A onto the space spanned by its top k singular vectors.

Theorem: Eckart-Young theorem

The Eckart–Young result establishes that SVD truncation gives the closest rank-k approximation in Frobenius and spectral norms. Computing a full SVD remains expensive, motivating partial and alternative methods.

  • SVD truncation produces the closest rank-k matrix to A.
  • The Frobenius-norm error equals the Euclidean norm of the singular values discarded during truncation.
  • The spectral-norm error of the best rank-k approximation equals σk+1.
  • Computing a full SVD costs O(mn^2), or O(n^3) flops for an n × n matrix.
  • Partial SVD can be obtained through partial QR factorization in O(kmn) flops, with Krylov methods also applicable to certain sparse matrices.
  • SVD is expensive for very large matrices, and some applications instead seek bases consisting of matrix rows or columns.

2.2 Pivoted QR decomposition

Pivoted QR decomposes a permuted matrix into orthogonal and triangular factors, then forms rank-k approximations by retaining the leading blocks. It is cheaper than SVD but can fail on some matrices, motivating RRQR.

  • Pivoted QR factorization writes AP = QR, with P a permutation matrix, Q orthonormal, and R upper triangular.
  • O(kmn) flops are required for the described column-pivoted QR algorithm.
  • Column-pivoted QR is cheaper than SVD, but its behavior is poorly understood and it can fail on some matrices.
  • Rank revealing QR factorization: RRQR uses a block upper-triangular factorization with singular-value guarantees controlled by a polynomial p(k, n).Its algorithms have complexity slightly larger than standard QR, while truncated RRQR approximations are reported as almost as good as truncated SVD approximations.
  • Conventional SVD and pivoted QR algorithms are unsuitable for large sparse matrices because transformations quickly destroy sparsity.

2.3 Interpolative decomposition

Interpolative decomposition represents a matrix using a subset of its columns and interpolation coefficients. Its column selection seeks informative, well-conditioned columns, and related CUR methods use selected rows and columns.

  • Interpolative decomposition uses selected columns of A and a coefficient matrix P to represent low-rank matrices through linear combinations.The decomposition is also called CX decomposition and relies completely on column subset selection.
  • Subset selection seeks k linearly independent columns that represent the matrix well and remain far from rank deficient.
  • The selected column matrix A1 is chosen to be well conditioned, while redundant columns A2 are represented through a coefficient matrix Z.The approximation error is bounded between σk+1(A) and γ σk+1(A).
  • ID requires selected columns of P to form an identity matrix, bounds every entry of P by 1, and provides singular-value and approximation guarantees.
  • Randomized ID algorithms can reduce the computational cost, with one cited algorithm requiring O(kmnlog(n)) complexity.
  • CUR and skeleton decompositions: Two IDs can be combined into CUR decomposition, where C and R contain selected columns and rows and U makes CUR close to A.The construction is also called skeleton decomposition; selected intersections may be required to be nonsingular or chosen by maximum volume.

2.4 Randomized algorithms

Randomized low-rank methods sample rows or columns or use random projections to build lower-dimensional representations and approximate bases. They reduce cost and passes over the matrix, but accuracy can require many samples or suffer from additive-error limitations.

  • Randomized algorithms construct a lower-dimensional matrix from sampled rows or columns, then obtain an approximate basis and project A onto it.The projection is ẼA = QQ^TA, where Q approximates the range of the sampled matrix.
  • Column subset selection problem: CSSP is difficult because finding the best k columns requires O(nk) time per candidate evaluation, making exhaustive optimization prohibitively slow for large data.The NP-hardness of CSSP, assuming k depends on n, is stated as an open problem.
  • Column subset selection problem: Any RRQR algorithm with provable guarantees also provides provable guarantees for column subset selection.
  • Column subset selection problem: One sampling method has additive error ǫ∥A∥2F that can be arbitrarily large, so it may perform poorly in some cases.
  • Column subset selection problem: Adaptive sampling and volume-sampling approaches improve additive-error guarantees and can achieve (1 + ǫ) relative approximation.
  • Randomised CUR: O(klog(1/δ)ǫ−4) columns and O(kδ−2ǫ−2) rows yield an additive-error CUR bound with probability at least 1−δ.The associated complexity is linear in m and n, but the method needs a very large number of sampled rows and columns for good accuracy.
  • Random projection: Random projection methods can require two data passes and have cost O(Mk/ǫ+(m+n)k2/ǫ2), where M is the number of nonzero entries.Structured random matrices can reduce multiplication cost to O(mn logs).

2.5 Some other techniques

The section surveys several low-rank approximation techniques, including NMF, SDD, and Nyström methods, together with their representations, applications, computational costs, and limitations.

  • Nonnegative matrix factorization: NMF approximates a nonnegative matrix A with nonnegative factors W and H, using an inner dimension k smaller than m and n.Exact equality A = WH is generally unavailable, so NMF is formulated as an approximation problem.
  • Nonnegative matrix factorization: NMF optimization is convex in either W or H separately but not jointly, so algorithms may guarantee only convergence to a local minimum.The factorization is also non-unique, allowing different algorithms to produce different factors.
  • Semidiscrete decomposition: SDD represents a matrix as a weighted sum of outer products whose vector entries lie in {−1, 0, 1}.The coefficients are positive scalars, and the factor vectors need not be linearly independent.
  • Semidiscrete decomposition: SDD uses less storage than truncated SVD but may require a large k for accurate approximation, with applications in image compression and data mining.Its factors can include repeated columns, which contributes to its flexible representation.
  • Nyström approximation: Nyström approximation targets symmetric positive semidefinite matrices using sampled columns, with approximation quality dependent on column selection.For rank k, the method uses W_k, the best rank k approximation of the sampled submatrix W, together with its pseudoinverse.
  • Nyström approximation: Nyström methods use uniform, non-uniform, adaptive, and ensemble sampling variants, with theoretical error estimates developed for different sampling strategies.One cited result selects O(k/ε^4) columns and provides error estimates relative to the best rank k approximation.

3 Cross/Skeleton approximation techniques

Cross/skeleton methods construct rank-k approximations from selected rows and columns, offering compact representations with complexity linear in matrix dimensions when k is small. Their accuracy depends on selecting a well-conditioned intersection submatrix, while adaptive, maximal-volume, and pseudoskeleton variants address selection and stability.

  • Cross/skeleton construction: Cross/skeleton approximation represents A approximately as CGR using k selected columns, k selected rows, and an intersection matrix M.In the standard construction, G=M^-1 when M is nonsingular.
  • Selection and stability: If M is singular or ill conditioned, CM^-1R fails to approximate A, making the choice of intersection submatrix central to accuracy and numerical stability.Maximum-volume selection is theoretically attractive but NP-complex, so practical methods use adaptive cross approximation, suboptimal maximal-volume selection, or pseudoskeleton decomposition.
  • Cross/skeleton construction: The algorithm selects columns, applies maxvol to choose corresponding rows, forms R, and constructs the skeleton decomposition from C, G, and R.The selected intersection matrix is chosen to have almost maximal volume.
  • Accuracy: Skeleton approximation with a maximal-volume M satisfies the quasioptimal sup-norm bound ||A-CGR||∞ ≤ (k + 1)^2 min_rank B ≤ k ||A-B||∞.The sup-norm is defined as the largest absolute matrix entry.
  • Complexity: O(k^3 + rk(m + n) + mr^2) is the stated cost of the pseudoskeleton algorithm, and the review identifies O(k^3) as its dominant term.Because k ≪ m,n and r ≪ k, the overall complexity is described as linear in m and n.
  • Complexity: O(k^2(m + n)) operations and k(m + n) storage are required for a rank-k approximation, using only k(m + n) original entries.These costs are linear in m and n for fixed small k.
Loading 1606.06511v1…