scientific article; zbMATH DE number 7330811

DOI10.4086/toc.2020.v016a015zbMath1477.68536OpenAlexW3116092193MaRDI QIDQ5857607

Cameron Musco, Michael B. Cohen, Jakub W. Pachocki

Publication date: 1 April 2021

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2020.v016a015

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

online algorithmsspectral sparsificationmatrix approximationleverage scores

Mathematics Subject Classification ID

Approximation algorithms (68W25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cites Work

• Unnamed Item
• Freedman's inequality for matrix martingales
• Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Single Pass Spectral Sparsification in Dynamic Streams
• Optimal CUR Matrix Decompositions
• Uniform Sampling for Matrix Approximation
• Low-Rank Approximation and Regression in Input Sparsity Time
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
• An Algorithm for Online K-Means Clustering
• Online Principal Components Analysis
• Approaching Optimality for Solving SDD Linear Systems
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
• Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix
• Graph Sparsification by Effective Resistances

This page was built for publication: