Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
DOI10.4230/LIPIcs.ITCS.2018.8zbMath1462.68082arXiv1704.04163MaRDI QIDQ4993271
Aaron Sidford, Cameron Musco, Praneeth Netrapalli, Shashanka Ubaru, David P. Woodruff
Publication date: 15 June 2021
Full work available at URL: https://arxiv.org/abs/1704.04163
Analysis of algorithms and problem complexity (68Q25) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Graph theory (including graph drawing) in computer science (68R10) Eigenvalues, singular values, and eigenvectors (15A18) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Numerical computation of matrix norms, conditioning, scaling (65F35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (5)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparse inverse covariance estimation with the graphical lasso
- Lower bounds on the error of query sets under the differentially-private matrix mechanism
- Feature selection with SVD entropy: some modification and extension
- Improved bounds on sample size for implicit matrix trace estimators
- The complexity of partial derivatives
- Spectrum estimation from samples
- Principal component analysis.
- A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix
- Minimization of numerical algorithms for solving arbitrary systems of linear equations
- Approximating Spectral Densities of Large Matrices
- Hierarchical Probing for Estimating the Trace of the Matrix Inverse on Toroidal Lattices
- Computational Advertising: Techniques for Targeting Relevant Ads
- Sketching and Embedding are Equivalent for Norms
- Efficient estimation of eigenvalue counts in an interval
- Uniform Sampling for Matrix Approximation
- Numerical Methods for Large Eigenvalue Problems
- 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
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Fast Estimation of $tr(f(A))$ via Stochastic Lanczos Quadrature
- Weighted Schatten <inline-formula> <tex-math notation="LaTeX">$p$ </tex-math> </inline-formula>-Norm Minimization for Image Denoising and Background Subtraction
- Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
- Embeddings of Schatten Norms with Applications to Data Streams
- Approximating Spectral Sums of Large-Scale Matrices using Stochastic Chebyshev Approximations
- On approximating functions of the singular values in a stream
- Fast Generation of Random Spanning Trees and the Effective Resistance Metric
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- On Sketching Matrix Norms and the Top Singular Vector
- Multiplying matrices faster than coppersmith-winograd
- Advanced Lectures on Machine Learning
- Functions of Matrices
- Low-rank matrix completion using alternating minimization
- Minimization of the number of arithmetic operations in the solution of linear algebraic systems of equations
- Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
- A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
This page was built for publication: Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
