62 citations · 151 across the 25 of their papers we have counts for
8 papers · 1 filter
Hit-and-Run Mixes as Fast as the Ball Walk
Ruizhe Zhang
Let be an isotropic convex body. We prove that the hit-and-run walk, started from any -warm distribution, reaches total-variation distance f…
Optimal Extrapolation Bounds for Sparse Fourier Sums
Ruizhe Zhang
We prove a sharp extrapolation bound for -sparse Fourier sums with arbitrary real frequencies and no separation assumption. For every with $λ_j\…
Quantum Speedup for Spectral Approximation of Kronecker Products
Yeqi Gao, Zhao Song, Ruizhe Zhang
Given its widespread application in machine learning and optimization, the Kronecker product emerges as a pivotal linear algebra operator. However, its computational demands render…
A General Algorithm for Solving Rank-one Matrix Sensing
Lianke Qin, Zhao Song, Ruizhe Zhang
Matrix sensing has many real-world applications in science and engineering, such as system control, distance embedding, and computer vision. The goal of matrix sensing is to recove…
Quartic Samples Suffice for Fourier Interpolation
Zhao Song, Baocheng Sun, Omri Weinstein +1
We study the problem of interpolating a noisy Fourier-sparse signal in the time duration from noisy samples in the same range, where the ground truth signal can be any …
Fast Distance Oracles for Any Symmetric Norm
Yichuan Deng, Zhao Song, Omri Weinstein +1
In the Distance Oracle problem, the goal is to preprocess vectors in a -dimensional metric space into a cheap data st…
Improved Reconstruction for Fourier-Sparse Signals
Yeqi Gao, Zhao Song, Baocheng Sun +2
We revisit the classical problem of Fourier-sparse signal reconstruction -- a variant of the \emph{Set Query} problem -- which asks to efficiently reconstruct (a subset of) a -d…
A Dynamic Low-Rank Fast Gaussian Transform
Baihe Huang, Zhao Song, Omri Weinstein +3
The \emph{Fast Gaussian Transform} (FGT) enables subquadratic-time multiplication of an Gaussian kernel matrix with…