Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness

DOI10.4230/LIPICS.ITCS.2018.8zbMATH Open1462.68082arXiv1704.04163MaRDI QIDQ4993271FDOQ4993271

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

Publication date: 15 June 2021

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.

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

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

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)

Cites Work

• Functions of Matrices
• Principal component analysis.
• Sparse inverse covariance estimation with the graphical lasso
• Title not available (Why is that?)
• Numerical methods for large eigenvalue problems
• Title not available (Why is that?)
• The complexity of partial derivatives
• Title not available (Why is that?)
• Multiplying matrices faster than coppersmith-winograd
• Lower bounds on the error of query sets under the differentially-private matrix mechanism
• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Title not available (Why is that?)
• A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines
• Improved bounds on sample size for implicit matrix trace estimators
• Feature selection with SVD entropy: some modification and extension
• Low-rank matrix completion using alternating minimization
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Hierarchical probing for estimating the trace of the matrix inverse on toroidal lattices
• Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
• Title not available (Why is that?)
• Advanced Lectures on Machine Learning
• Sketching and embedding are equivalent for norms
• 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
• Approximating spectral densities of large matrices
• Title not available (Why is that?)
• Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
• Metric and kernel learning using a linear transformation
• Algorithms and hardness for subspace approximation
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Sketching as a tool for numerical linear algebra
• Title not available (Why is that?)
• Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations
• Minimization of the number of arithmetic operations in the solution of linear algebraic systems of equations
• Efficient estimation of eigenvalue counts in an interval.
• Spectrum estimation from samples
• Fast estimation of \(\mathrm{tr}(f(A))\) via stochastic Lanczos quadrature
• A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix
• On approximating functions of the singular values in a stream
• On Sketching Matrix Norms and the Top Singular Vector
• Fast generation of random spanning trees and the effective resistance metric
• Embeddings of Schatten Norms with Applications to Data Streams
• Minimization of numerical algorithms for solving arbitrary systems of linear equations

Cited In (8)

• Estimating Leverage Scores via Rank Revealing Methods and Randomization
• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Title not available (Why is that?)
• Fast Algorithms for the Approximation of the Pseudospectral Abscissa and Pseudospectral Radius of a Matrix
• Efficient $\widetilde{O}(n/\epsilon)$ Spectral Sketches for the Laplacian and its Pseudoinverse
• Title not available (Why is that?)
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• Monte Carlo estimators for the Schatten \(p\)-norm of symmetric positive semidefinite matrices

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)