6 citations · 9 across the 7 of their papers we have counts for
11 papers · 1 filter
A Near-Optimal Lower Bound for -Subspace Embeddings,
Yi Li
For , and , let be the smallest integer such that for every integer and every , there exists a matrix $Φ\i…
Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings
Yi Li, David P. Woodruff
We consider the following oblivious sketching problem: given and , design a distribution over and a function $…
Single Pass Entrywise-Transformed Low Rank Approximation
Yifei Jiang, Yi Li, Yiming Sun +2
In applications such as natural language processing or computer vision, one is given a large matrix and would like to compute a matrix decomposition, e…
Exponentially Improved Dimensionality Reduction for : Subspace Embeddings and Independence Testing
Yi Li, David P. Woodruff, Taisuke Yasuda
Despite many applications, dimensionality reduction in the -norm is much less understood than in the Euclidean norm. We give two new oblivious dimensionality reduction tech…
Streaming Complexity of SVMs
Alexandr Andoni, Collin Burns, Yi Li +2
We study the space complexity of solving the bias-regularized SVM problem in the streaming model. This is a classic supervised learning problem that has drawn lots of attention, in…
Nearly Linear Row Sampling Algorithm for Quantile Regression
Yi Li, Ruosong Wang, Lin Yang +1
We give a row sampling algorithm for the quantile loss function with sample complexity nearly linear in the dimensionality of the data, improving upon the previous best algorithm w…