PaperlayerView exact revision on arXiv

Source-linked AI summary

Revisiting the Nystrom Method for Improved Large-Scale Machine Learning

Alex Gittens, Michael W. Mahoney

arXiv:1303.1849v2cs.LGcs.DSmath.NA

TL;DR

The paper studies how randomized sampling and projection methods approximate SPSD matrices in realistic machine-learning and data-analysis settings. It combines empirical comparisons with improved worst-case theory, finding complementary practical roles and qualitatively stronger bounds than existing analyses.

  • Problem

    Existing Nyström theory is modest, while empirical evidence is needed to understand sampling and projection methods on realistic SPSD matrices.

  • Method

    The paper evaluates sampling and projection methods empirically on diverse SPSD matrices and develops worst-case bounds for random sampling and projection algorithms.

  • Results

    Sampling and projection methods offer complementary approaches with roughly comparable running times under suitable parameters, while improved bounds cover spectral, Frobenius, and trace norm errors.

  • Takeaways & Limitations

    Approximate leverage scores can make sampling faster than exact leverage-score computation and soften its bias toward the best rank-k approximation in many cases.

  • Takeaways & Limitations

    The empirical results are illustrative case studies rather than comprehensive evaluations, and general-matrix methods do not generally preserve SPSD structure.

Abstract

from arXiv · show

We reconsider randomized algorithms for the low-rank approximation of symmetric positive semi-definite (SPSD) matrices such as Laplacian and kernel matrices that arise in data analysis and machine learning applications. Our main results consist of an empirical evaluation of the performance quality and running time of sampling and projection methods on a diverse suite of SPSD matrices. Our results highlight complementary aspects of sampling versus projection methods; they characterize the effects of common data preprocessing steps on the performance of these algorithms; and they point to important differences between uniform sampling and nonuniform sampling methods based on leverage scores. In addition, our empirical results illustrate that existing theory is so weak that it does not provide even a qualitative guide to practice. Thus, we complement our empirical results with a suite of worst-case theoretical bounds for both random sampling and random projection methods. These bounds are qualitatively superior to existing bounds---e.g. improved additive-error bounds for spectral and Frobenius norm error and relative-error bounds for trace norm error---and they point to future directions to make these algorithms useful in even larger-scale machine learning applications.

1. INTRODUCTION

The paper combines empirical evaluation and worst-case analysis to clarify when sampling and projection methods provide high-quality SPSD low-rank approximations in realistic applications.

  • Scope: The results are illustrative rather than comprehensive, covering a broad range of realistic machine-learning and data-analysis applications.The paper presents the experiments as representative case studies rather than exhaustive evidence.
  • Empirical evaluation: The study empirically compares data-independent random projections with data-dependent random sampling across diverse dense and sparse SPSD matrices.The matrices come from machine learning and broader data-analysis applications.
  • Empirical evaluation: Sampling and projection methods have complementary strengths and weaknesses that depend on parameter settings, norm, and dataset.The evaluation considers spectral, Frobenius, and trace-norm reconstruction error.
  • Empirical evaluation: The paper examines both approximation quality and the running time of high-quality sampling and projection algorithms.For sampling methods, exact or approximate leverage-score computation is typically a computational bottleneck.
  • Theoretical perspective: The paper unifies sampling and projection analysis and identifies deterministic structural nonuniformities associated with high-quality low-rank approximation.These structural properties are used to connect worst-case analysis with empirical behavior.
  • Motivation: Existing Nyström theory is weak relative to theory for least-squares regression and general low-rank approximation, while other bounds require strong coherence assumptions.The paper motivates improved analysis for realistic SPSD applications.

2. NOTATION, PRELIMINARIES, AND RELATED PRIOR WORK

The paper develops a unified view of SPSD low-rank approximation, comparing sampling and projection sketches through structural properties, empirical behavior, and theoretical error bounds.

  • Notation: Leverage scores quantify row-wise nonuniformity in the top-k eigenspace and guide importance sampling for low-rank approximation.For a rank-k approximation, leverage scores are squared row norms of U1.
  • Notation: The approximation error is measured as additional error beyond the best rank-k approximation, including spectral, Frobenius, and trace norm errors.Additive-error bounds seek to minimize the scale multiplying ε beyond the base error.
  • Related prior work: Nyström approximations can use uniform or leverage-based column sampling, while projection methods construct approximate invariant-subspace bases from sketches.Uniform sampling is effective for some matrices, whereas nonuniform sampling can improve reconstruction error for a fixed sample count.
  • Preliminaries: SPSD matrices are approximated using either column-sampling Nyström extensions or projection-based sketches formed from random linear combinations of columns.The sketching distribution distinguishes the two approximation classes.
  • Theoretical bounds: The paper's bounds improve prior guarantees, including smaller-scale spectral additive-error bounds for nonuniform sketches and matching worst-case bounds for uniform Nyström extensions.Theoretical guarantees depend on structural quantities such as coherence and leverage scores.
  • Empirical and theoretical behavior: Empirically, sketches with ℓ=O(k ln n) have average errors within 1 + ε of optimal rank-k errors, and leverage-based sketches consistently have lower average errors.Gaussian-based bounds closely track practice, while leverage- and Fourier-based Frobenius and trace guarantees often reflect empirical behavior better than prior Nyström bounds.

3. EMPIRICAL ASPECTS OF SPSD LOW-RANK APPROXIMATION

The empirical study evaluates sampling and projection methods across diverse SPSD matrices, examining approximation quality, running time, and data-set structure. The data sets span sparse Laplacians, linear kernels, dense and sparse RBF kernels, with substantial variation in spectral decay, rank structure, and leverage-score heterogeneity.

  • Experimental design: The evaluation compares two random sampling and two random projection procedures on diverse SPSD matrices, assessing solution quality, running time, and preprocessing effects.The study uses illustrative case studies rather than claiming comprehensive coverage.
  • Interpretation: The empirical results are intended to expose tradeoffs among sampling and projection methods across realistic applications rather than establish a comprehensive benchmark.The experiments use data sets representative of several machine-learning application classes.
  • Data sets: The data sets include sparse graph Laplacians, dense Linear Kernels, dense Gaussian RBFK matrices, and Sparse RBF Kernels.For Laplacians, n denotes graph nodes; for kernel matrices, the data include feature dimensions and varying sparsity.
  • Data-set structure: Laplacian Kernels are extremely sparse and exhibit very slow spectral decay, with relatively little Frobenius norm captured by their best rank-k approximations.These properties make the Laplacian matrices less well suited to moderately low-rank approximation than the denser kernel classes.
  • Data-set structure: Linear and dense RBF Kernels are denser and better approximated by moderately to very low-rank matrices, whereas sparsifying RBF Kernels reduces low-rank approximability and increases leverage-score nonuniformity.For AbaloneD, the captured Frobenius fraction decreases from 97.8 to 42.1 as the matrix is altered; the scaled kth-largest leverage score increases from 2.44 to 18.11.

3.2. SPSD Sketching Algorithms.

The study constructs SPSD sketches using uniform sampling, leverage-score sampling, Gaussian projections, and SRFT projections. Leverage-based sketches sample according to rank-k leverage scores and rescale selected columns, while projection sketches use Gaussian or Fourier-based matrices.

  • Sampling methods: Sampling-based sketches use either uniform column sampling with replacement or probabilities based on leverage scores relative to the best rank-k approximation.The sketching matrix for uniform sampling consists of selected columns, while leverage-based sampling uses a more complicated distribution.
  • Sampling methods: Leverage scores are squared row norms of the n × k matrix U1 and form a probability distribution over the columns of A.The method samples columns with replacement from this distribution.
  • Sampling methods: Leverage-based sketches construct S = RD, where R selects sampled columns and D diagonally rescales them according to the sampling probabilities.The selection matrix records which columns are chosen, and the rescaling matrix adjusts the sampled sketch.
  • Sampling methods: Exact leverage-score computation can be expensive, so the study evaluates sketches based on several approximate leverage-score algorithms.These approximations retain the same sketching form and differ only in the distribution used to select columns.
  • Projection methods: The projection sketches use i.i.d. Gaussian matrices or subsampled randomized Fourier transform matrices.For SRFT sketches, S uses a diagonal Rademacher matrix, the real Fourier transform, and column restriction.

3.3. Effects of Data Analysis Preprocessing Decisions.

The paper examines how whitening, rank selection, and the RBF scale parameter affect SPSD sketching and leverage scores. These choices can alter leverage-score homogeneity, effective rank, spectral gaps, and matrix approximability.

  • Design implications: The behavior of leverage scores across k and σ matters because recomputing them during cross-validation can be expensive.The paper studies these dependencies using observations from a diverse range of data sets rather than worst-case matrices.
  • Whitening: Whitening centers each feature and rescales columns to unit norm before sketching.In the authors’ experience, whitening often makes leverage scores somewhat more homogeneous while changing fixed-rank scores by no more than a factor of 2.
  • Whitening: Whitening tends to decrease effective rank and often shrinks spectral gaps, which are structural properties relevant to matrix reconstruction.The paper emphasizes these effects as more important than the modest leverage-score changes.
  • Rank selection: The rank parameter k is commonly selected by an external model-selection criterion that does not explicitly account for the spectrum or leverage-score structure.Because leverage scores are defined relative to rank-k spaces, changing k changes the sampling distribution.
  • RBF scale: As the Gaussian RBF scale σ increases, leverage scores become increasingly uniform, while as σ decreases the matrix approaches the identity and can exhibit greater column nonuniformity.For some data sets, decreasing σ stabilizes the leverage scores and identifies the same influential columns across a range of scales.

3.4. Reconstruction Accuracy of Sampling and Projection Algorithms.

The experiments compare uniform sampling, leverage-score sampling, and projection sketches across diverse SPSD matrices and reconstruction norms. Performance depends strongly on data structure: leverage-score sampling is especially advantageous for heterogeneous, less low-rank data, while uniform sampling performs well on low-rank data with uniform leverage scores.

  • Experimental setup: The study compares uniform and leverage-score column sampling with Gaussian and SRFT projection mixtures using spectral, Frobenius, and trace norm reconstruction errors.Both non-rank-restricted and rank-restricted approximations are evaluated across multiple SPSD data sets.
  • Graph Laplacians: For graph Laplacians, errors show complicated behavior as the sample count ℓ increases, with non-rank-restricted errors generally decreasing more than rank-restricted errors.At ℓ = k, the two formulations coincide; for ℓ > k, rank-restricted errors are bounded below by unity.
  • Overall accuracy: All sketches often achieve accurate approximations with only k column samples or k linear combinations, substantially outperforming existing worst-case bounds.The reported results are relative to optimal rank-k approximation factors and prior theoretical bounds.
  • Linear Kernels: Linear-kernel methods perform similarly because these matrices are relatively low-rank and have fairly uniform leverage scores, making uniform sampling a practical choice.For these data, alternatives offer little advantage while costing more.
  • RBF Kernels: Leverage-score sampling tends to outperform uniform sampling and projections for dense RBF kernels with smaller σ and sparse RBF kernels.These settings are less well approximated by low-rank matrices and have more heterogeneous leverage scores.
  • Running time: Approximate leverage-score computation can make sampling runtimes comparable to random projections for certain parameter settings while preserving useful approximation quality.Exact leverage-score sampling is otherwise computationally more expensive than competing methods.

3.5. Reconstruction Accuracy of Leverage Score Approximation Algorithms.

The study compares leverage-score approximation algorithms by reconstruction quality and running time, finding strong dependence on matrix structure and approximation parameters. Approximate methods can substantially reduce leverage-score computation costs, but their quality and runtime trade-offs vary across datasets and norms.

  • Fast approximation algorithm: Algorithm 1 runs in roughly O(nd ln d) under d = Ω(ln n), avoiding the O(nd^2) cost of a QR decomposition or thin SVD for tall matrices.For rectangular matrices, its runtime is faster than QR and comparable to applying an SRFT, while outperforming the other approximate leverage-score algorithms.
  • Running time: Uniform sampling is always less expensive and typically much less expensive than the other methods, whereas exact leverage-score sampling is generally the most expensive.SRFT costs can approach exact leverage-score sampling, especially for very sparse graph Laplacian Kernels because SRFT does not respect sparsity.
  • Running time: Approximate leverage-score algorithms can be orders of magnitude faster than exact computation, but some spectral approximations can be slower when power iterations are not prespecified.The Frobenius-oriented approximation has running time comparable to the random projection used within the approximation algorithm.
  • Reconstruction accuracy: Approximate leverage-score methods produce dataset- and setting-dependent reconstruction quality, with “power” and “spec levscore” substantially outperforming uniform sampling for Laplacian Kernels.For Linear Kernels, methods perform similarly in the non-rank-restricted case, while approximate scores often parallel exact-score results in rank-restricted settings.
  • Reconstruction accuracy: Spectral gaps explain differences among approximate leverage-score methods: larger λ_k/λ_{k+1} generally yields more accurate approximations.Power iterations converge more rapidly when the spectral gap is larger, improving the resulting approximate leverage scores.
  • Summary: Random projections support SPSD approximation both directly and indirectly through approximate leverage-score computation, revealing complementary uses of projection methods.The paper evaluates these approaches empirically across reconstruction quality and computational cost.

3.6. Projection-based Sketches.

Projection-based SPSD sketches include standard, pinched, and prolonged variants evaluated across spectral, Frobenius, and trace norm errors. Prolonged sketches are generally most accurate, especially in spectral norm and for RBF Kernel datasets, because powering increases top-subspace bias.

  • Empirical comparison: Figure 15 plots spectral, Frobenius, and trace norm errors against the number of sampled columns ℓ across several datasets and SPSD sketch variants.Pinched and prolonged sketches are compared with standard sketches using uniform sampling, Gaussian column mixtures, and SRFT-based column mixtures.
  • Theoretical connection: The prolonged sketch is exactly the sketch obtained by applying the power method with q = 2, so the paper’s power-method bounds also apply to it.This equivalence follows from considering the choices X = AS and X = Q in the SPSD sketch representation.
  • Empirical comparison: Prolonged sketches are considerably more accurate than pinched and standard sketches in spectral norm for every dataset considered.Prolonged Gaussian and SRFT column-mixture sketches are uniformly the most accurate spectrally, while prolonged uniform sampling is nearly as accurate only for the Dexter Linear Kernel.
  • Empirical comparison: The benefits of pinched and prolonged sketches are most prominent for spectral-norm error or RBF Kernel datasets, with limited additional accuracy in Frobenius and trace norms.The paper reports no significant Frobenius- or trace-norm improvement for any dataset considered.
  • Pinched and prolonged sketches: Pinched sketches generally improve accuracy less than prolonged sketches.The paper attributes this difference to prolonged sketches projecting onto the range of A^3/2S rather than AS.
  • Pinched and prolonged sketches: Powering increases spectral decay, making the range of A^3/2S more biased toward A’s top k-dimensional invariant subspace than the range of AS.This produces a more accurate approximate square root for constructing prolonged sketches.

4. THEORETICAL ASPECTS OF SPSD LOW-RANK APPROXIMATION

The theoretical section develops deterministic SPSD approximation bounds and then uses them to analyze random sampling and projection methods. The bounds apply to any sketching matrix and connect approximation quality to subspace geometry and spectral structure.

  • Overview: The paper presents deterministic structural conditions for spectral, Frobenius, and trace norm errors before deriving bounds for random sampling and random projection procedures.These results were motivated by empirical performance substantially exceeding previous worst-case bounds.
  • Overview: The three error theorems apply to any deterministic or randomized sketching matrix S, enabling a posteriori quality checks for sketches without an established a priori bound.The same results are then used to derive a priori bounds for common random sampling and projection algorithms.
  • Geometric framework: The analysis represents SPSD Sketching Model approximations as projections onto subspaces contained in the range of the approximated matrix’s square root.This representation underlies the connection between SPSD approximation and column sketching from the square root of A.
  • Geometric interpretation: A smaller sketching interaction norm ||Ω_2Ω_1†|| improves effectiveness, and with orthonormal S it equals the tangent of the largest angle between range(S) and the top-eigenspace span(U_1).This gives the spectral bound a geometric interpretation in terms of subspace alignment.

1 SSTU1

The passage develops the subspace-angle interpretation used in the SPSD approximation analysis. It relates the interaction between the sketch and the dominant eigenspace to how well the sketch captures that eigenspace.

  • Subspace geometry: When U_1 and S have orthonormal columns and U_1^T S has full row rank, the resulting interaction quantity characterizes alignment between the sketch space and the dominant eigenspace.This is the geometric ingredient used to interpret the spectral approximation bound.

1 S)(UT 1 S)† 2

The deterministic bounds relate SPSD approximation error to how the sketch interacts with dominant eigenspaces, with power iterations improving errors when spectral decay is present.

  • Assumptions: The full-row-rank assumption on Ω1 is nontrivial and can fail for common sketching methods, including uniform sampling in worst cases.The associated condition is equivalently that tan(S,U1) is finite.
  • Power iterations: The multiplicative eigengap γ = λ_k+1(A)/λ_k(A) predicts power-method improvement, with additional errors reduced by a factor of γ^(q−1).This improvement applies when comparing sketches constructed using C = A^qS with those using C = AS.

1 FTFΣ1/2

The Frobenius-norm analysis gives a geometric interpretation of sketch quality: the relevant interaction measures how well the sketch captures the dominant eigenspace.

  • Geometric interpretation: Theorem-2 error quality depends on interaction quantities reflecting the sketch's alignment with A's eigenspaces.Different sketching procedures can yield different bounds on these quantities.
  • Power iterations: Larger gaps between the k and k + 1 eigenvalues lead to smaller errors when the power method is used.The power method is effective only when spectral decay is present.
  • Geometric interpretation: The Frobenius norm of the spectral interaction matrix equals the sum of squared tangents of principal angles between the sketch and dominant eigenspace.This makes the quantity a more stringent measure of eigenspace capture than a single largest-angle measure.

1 S)(UT 1 S)†Š

The analysis extends to trace-norm error and shows that power iterations improve additional error according to the eigengap, while flat residual spectra yield especially tight Frobenius behavior.

  • Frobenius consequence: When the residual spectrum is flat, λ_k+1(A) = ··· = λ_n(A), the additional Frobenius error is on the scale of the optimal error.The passage states that equality holds in this case.
  • Trace-norm bound: The trace-norm residual bound is derived using a proof strategy analogous to the spectral- and Frobenius-norm analyses.The result is presented as a separate theorem for the SPSD sketching model.
  • Power iterations: The additional trace-norm error decreases by a factor of γ^(2(q−1)) when sketches use C = A^qS instead of C = AS.Here γ = λ_k+1(A)/λ_k(A) is the multiplicative eigengap.

1 FTFΣ1/2

The structural results are deterministic, but their practical guarantees depend on sketch–eigenspace interaction and assumptions such as full row rank; leverage-based sampling and projections address these issues differently.

  • Deterministic framework: The deterministic theorems can evaluate both deterministic and randomized sketching matrices, with randomness entering only through S.For randomized sketches, the full-row-rank condition must hold with high probability.
  • Deterministic framework: The results can also support a posteriori quality checks for sketching methods lacking an a priori bound.This use is identified as beyond the paper's detailed scope.
  • Sampling and projection: Random projections effectively rotate data so leverage scores become approximately uniform, making uniform sampling appropriate in the rotated basis.This explains a complementary relationship between projection methods and leverage-based sampling.
  • Computational considerations: Using an explicitly known matrix square root typically costs Ω(n^2), whereas this approach uses the square root only implicitly and avoids that cost.The implicit use occurs in the analysis rather than the algorithm statement.
  • Leverage-based sampling: Leverage-based sampling probabilities expose structural data properties more finely than prior probabilities, improving spectral and Frobenius additive scales at extra computational expense.The relevant condition includes ensuring Ω1 has full row rank.
  • Random projections: Gaussian projection bounds expose parameter dependence and can yield a trace-norm multiplicative factor of 1 + ε with suitable parameters.The corresponding Frobenius bound combines terms depending on Frobenius- and trace-norm errors.
  • Uniform sampling: Uniform-sampling bounds are much weaker because sampling complexity depends on input coherence, although they become similar to leverage-based bounds when coherence is small.Coherence can be computed in roughly the time required for a random projection.

5. DISCUSSION AND CONCLUSION

The paper unifies low-rank approximation of Laplacian and kernel matrices, combining improved worst-case theory with empirical analysis of practical performance. Its evaluation finds that approximation quality depends on spectral decay, leverage scores, and eigenvalue gaps, while the theory separates algorithmic randomness from structural heterogeneity.

  • The paper presents a unified approach to low-rank approximations of Laplacian and kernel matrices, with qualitatively improved worst-case theory and practical performance analysis.
  • Approximation quality depends in complicated ways on spectral decay, leverage score structure, and eigenvalue gaps, although the evaluated sketches remain reasonably effective across varied matrices.
  • For eigenspace approximation, small spectral-norm error and few samples are both desirable because they support accurate capture of the top k-dimensional eigenspace.
  • The theoretical analysis decouples algorithmic randomness from structural heterogeneities that can cause poor performance for uniform sampling.
Loading 1303.1849v2…