3 papers
cs.DS2026
Lazy Kronecker Product
Zhao Song
In this paper, we show how to generalize the lazy update regime from dynamic matrix product [Cohen, Lee, Song STOC 2019, JACM 2021] to dynamic kronecker product. We provide an algo…
cs.DS2024
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…
cs.DS2022
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 …