Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness

DOI10.4230/LIPICS.ITCS.2018.8MaRDI QIDQ4993271zbMATHFDO

Authors Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, David P. Woodruff

Publication date 15 June 2021

Full work available at URL https://arxiv.org/abs/1704.04163

zbMATH Keywords

linear algebraspectrum approximationfine-grained complexitymatrix norm computation

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Numerical computation of matrix norms, conditioning, scaling (65F35) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60)

Abstract: Understanding the singular value spectrum of a matrix $Ainmathbb{R}^{nimesn}$ is a fundamental task in countless applications. In matrix multiplication time, it is possible to perform a full SVD and directly compute the singular values $sigm{a}_1,\mathrm{...},sigm{a}_n$. However, little is known about algorithms that break this runtime barrier. Using tools from stochastic trace estimation, polynomial approximation, and fast system solvers, we show how to efficiently isolate different ranges of $A$'s spectrum and approximate the number of singular values in these ranges. We thus effectively compute a histogram of the spectrum, which can stand in for the true singular values in many applications. We use this primitive to give the first algorithms for approximating a wide class of symmetric matrix norms in faster than matrix multiplication time. For example, we give a $(1+epsilon)$ approximation algorithm for the Schatten-$1$ norm (the nuclear norm) running in just $ildeO((nnz(A)n^{1/3}+n^2)epsilo{n}^{-3})$ time for $A$ with uniform row sparsity or $ildeO(n^{2.18}epsilo{n}^{-3})$ time for dense matrices. The runtime scales smoothly for general Schatten-$p$ norms, notably becoming $ildeO(pcdotnnz(A)epsilo{n}^{-3})$ for any $pge2$. At the same time, we show that the complexity of spectrum approximation is inherently tied to fast matrix multiplication in the small $epsilon$ regime. We prove that achieving milder $epsilon$ dependencies in our algorithms would imply faster than matrix multiplication time triangle detection for general graphs. This further implies that highly accurate algorithms running in subcubic time yield subcubic time matrix multiplication. As an application of our bounds, we show that precisely computing all effective resistances in a graph in less than matrix multiplication time is likely difficult, barring a major algorithmic breakthrough.

Recommendations

• Fast algorithms for spectral differentiation matrices
• On approximate spectral factorization of matrix functions
• Faster spectral sparsification and numerical algorithms for SDD matrices
• scientific article; zbMATH DE number 3951889
• Two classes of matrices with fast computable spectra
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• Approximating spectral densities of large matrices
• On the Algorithmic Solvability of Spectral Factorization and Applications
• Efficient Calculation of Bounds on Spectra of Hessian Matrices
• Fast Algorithms for the Approximation of the Pseudospectral Abscissa and Pseudospectral Radius of a Matrix

Cites work

• scientific article; zbMATH DE number 1618184 (Why is no real title available?)
• scientific article; zbMATH DE number 3688713 (Why is no real title available?)
• scientific article; zbMATH DE number 1012640 (Why is no real title available?)
• scientific article; zbMATH DE number 1049353 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• scientific article; zbMATH DE number 5485569 (Why is no real title available?)
• A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix
• A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines
• Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
• Advanced Lectures on Machine Learning
• Algorithms and hardness for subspace approximation
• Approximating spectral densities of large matrices
• Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations
• Efficient estimation of eigenvalue counts in an interval.
• Embeddings of Schatten norms with applications to data streams
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Fast estimation of \(\mathrm{tr}(f(A))\) via stochastic Lanczos quadrature
• Fast generation of random spanning trees and the effective resistance metric
• Feature selection with SVD entropy: some modification and extension
• Functions of Matrices
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Hierarchical probing for estimating the trace of the matrix inverse on toroidal lattices
• Improved bounds on sample size for implicit matrix trace estimators
• Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
• Low-rank matrix completion using alternating minimization
• Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
• Lower bounds on the error of query sets under the differentially-private matrix mechanism
• Metric and kernel learning using a linear transformation
• Minimization of numerical algorithms for solving arbitrary systems of linear equations
• Minimization of the number of arithmetic operations in the solution of linear algebraic systems of equations
• Multiplying matrices faster than coppersmith-winograd
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• Numerical methods for large eigenvalue problems
• On approximating functions of the singular values in a stream
• On sketching matrix norms and the top singular vector
• Principal component analysis.
• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• Sketching and embedding are equivalent for norms
• Sketching as a tool for numerical linear algebra
• Sparse inverse covariance estimation with the graphical lasso
• Spectrum estimation from samples
• The complexity of partial derivatives
• Uniform sampling for matrix approximation
• Weighted Schatten <inline-formula> <tex-math notation="LaTeX">$p$ </tex-math> </inline-formula>-Norm Minimization for Image Denoising and Background Subtraction

Cited in

(9)

• Fast Algorithms for the Approximation of the Pseudospectral Abscissa and Pseudospectral Radius of a Matrix
• scientific article; zbMATH DE number 7378710 (Why is no real title available?)
• Estimating Leverage Scores via Rank Revealing Methods and Randomization
• Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time
• Monte Carlo estimators for the Schatten \(p\)-norm of symmetric positive semidefinite matrices
• Efficient $\widetilde{O}(n/\epsilon)$ Spectral Sketches for the Laplacian and its Pseudoinverse
• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• On sketching the \(q\) to \(p\) norms
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity

Describes a project that uses

Uses Software

• glasso
• mftoolbox

This page was built for publication: Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993271)