6 citations · 12 across the 5 of their papers we have counts for
4 papers · 1 filter
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…