pith. machine review for the scientific record. sign in

arxiv: 1605.08194 · v1 · submitted 2016-05-26 · 💻 cs.DS

Recognition: unknown

Analysis of Resparsification

Jakub Pachocki
Authors on Pith no claims yet
classification 💻 cs.DS
keywords analysisclassicformalgivesguaranteesiterativelykelnerlevin
0
0 comments X
read the original abstract

We show that schemes for sparsifying matrices based on iteratively resampling rows yield guarantees matching classic 'offline' sparsifiers (see e.g. Spielman and Srivastava [STOC 2008]). In particular, this gives a formal analysis of a scheme very similar to the one proposed by Kelner and Levin [TCS 2013].

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Analysis of Nystrom method with sequential ridge leverage scores

    cs.LG 2026-04 unverdicted novelty 7.0

    INK-ESTIMATE incrementally estimates ridge leverage scores via a fixed-size sketch for sequential Nystrom approximation in kernel ridge regression, delivering single-pass computation and guarantees on matrix approxima...