6 citations · 12 across the 5 of their papers we have counts for
6 papers
Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
Shabarish Chenakkod, Michał Dereziński
The power method is one of the most fundamental tools for extracting top principal components from data through low-rank matrix approximation. Yet, when the target rank is large, t…
Well-Conditioned Oblivious Perturbations in Linear Space
Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong +1
Perturbing a deterministic -dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms [Spielman and Teng, JACM 2004], as it reduces the co…
Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors
Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong
We give a proof of the conjecture of Nelson and Nguyen [FOCS 2013] on the optimal dimension and sparsity of oblivious subspace embeddings, up to sub-polylogarithmic factors: For an…
Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity
Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong
An oblivious subspace embedding is a random matrix such that, for any -dimensional subspace, with high probability preserves the norms of all vectors in that…
Optimal Embedding Dimension for Sparse Subspace Embeddings
Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong +1
A random matrix is an oblivious subspace embedding (OSE) with parameters , and , if for any -dimensional subspace $W\subseteq R…
Translation surfaces and periods of meromorphic differentials
Shabarish Chenakkod, Gianluca Faraco, Subhojoy Gupta
Let be an oriented surface of genus and punctures. The periods of any meromorphic differential on , with respect to a choice of complex structure, determine a repres…