688 citations · 1.5k across the 49 of their papers we have counts for
7 papers · 1 filter
Optimal Sketching for Kronecker Product Regression and Low Rank Approximation
Huaian Diao, Rajesh Jayaram, Zhao Song +2
We study the Kronecker product regression problem, in which the design matrix is a Kronecker product of two or more matrices. Given for $i=1,2…
Total Least Squares Regression in Input Sparsity Time
Huaian Diao, Zhao Song, David P. Woodruff +1
In the total least squares problem, one is given an matrix , and an matrix , and one seeks to "correct" both and , obtaining matrices $\hat{A…
(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
Vasileios Nakos, Zhao Song, Zhengyu Wang
In this paper, we consider the extensively studied problem of computing a -sparse approximation to the -dimensional Fourier transform of a length signal. Our algorithm us…
Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
Yin Tat Lee, Zhao Song, Qiuyi Zhang
Many convex problems in machine learning and computer science share the same form: \begin{align*} \min_{x} \sum_{i} f_i( A_i x + b_i), \end{align*} where are convex functions…
Reducing approximate Longest Common Subsequence to approximate Edit Distance
Aviad Rubinstein, Zhao Song
Given a pair of strings, the problems of computing their Longest Common Subsequence and Edit Distance have been extensively studied for decades. For exact algorithms, LCS and Edit…
Stronger L2/L2 Compressed Sensing; Without Iterating
Vasileios Nakos, Zhao Song
We consider the extensively studied problem of compressed sensing. The main contribution of our work is an improvement over [Gilbert, Li, Porat and Strauss, STOC 20…
The Limitations of Adversarial Training and the Blind-Spot Attack
Huan Zhang, Hongge Chen, Zhao Song +3
The adversarial training procedure proposed by Madry et al. (2018) is one of the most effective methods to defend against adversarial examples in deep neural networks (DNNs). In ou…