4 citations · 14 across the 15 of their papers we have counts for
15 papers
Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basis
Xiang Chen, Zhao Song, Baocheng Sun +2
Many machine learning algorithms require large numbers of labeled data to deliver state-of-the-art results. In applications such as medical diagnosis and fraud detection, though th…
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…
A Nearly-Optimal Bound for Fast Regression with Guarantee
Zhao Song, Mingquan Ye, Junze Yin +1
Given a matrix and a vector , we consider the regression problem with guarantees: finding a vector $x'\in \mathbb{R}^…
Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations
Lianke Qin, Aravind Reddy, Zhao Song +2
In this paper, we propose Adam-Hash: an adaptive and dynamic multi-resolution hashing data-structure for fast pairwise summation estimation. Given a data-set $X \subset \mathbb{R}^…
Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance
Zhao Song, Xin Yang, Yuanyuan Yang +1
Projection maintenance is one of the core data structure tasks. Efficient data structures for projection maintenance have led to recent breakthroughs in many convex programming alg…
Dynamic Tensor Product Regression
Aravind Reddy, Zhao Song, Lichen Zhang
In this work, we initiate the study of \emph{Dynamic Tensor Product Regression}. One has matrices and a…
An Time Fourier Set Query Algorithm
Yeqi Gao, Zhao Song, Baocheng Sun
Fourier transformation is an extensively studied problem in many research fields. It has many applications in machine learning, signal processing, compressed sensing, and so on. In…
Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory
Jiehao Liang, Zhao Song, Zhaozhuo Xu +2
Kernel density estimation (KDE) stands out as a challenging task in machine learning. The problem is defined in the following way: given a kernel function and a set of poi…
Accelerating Frank-Wolfe Algorithm using Low-Dimensional and Adaptive Data Structures
Zhao Song, Zhaozhuo Xu, Yuanyuan Yang +1
In this paper, we study the problem of speeding up a type of optimization algorithms called Frank-Wolfe, a conditional gradient method. We develop and employ two novel inner produc…
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…
Speeding Up Sparsification using Inner Product Search Data Structures
Zhao Song, Zhaozhuo Xu, Lichen Zhang
We present a general framework that utilizes different efficient data structures to improve various sparsification problems involving an iterative process. We also provide insights…
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…
Super-resolution and Robust Sparse Continuous Fourier Transform in Any Constant Dimension: Nearly Linear Time and Sample Complexity
Yaonan Jin, Daogao Liu, Zhao Song
The ability to resolve detail in the object that is being imaged, named by resolution, is the core parameter of an imaging system. Super-resolution is a class of techniques that ca…
PREMIER - PRobabilistic Error-correction using Markov Inference in Errored Reads
Xin Yin, Zhao Song, Karin Dorman +1
In this work we present a flexible, probabilistic and reference-free method of error correction for high throughput DNA sequencing data. The key is to exploit the high coverage of…
A Max-Product EM Algorithm for Reconstructing Markov-tree Sparse Signals from Compressive Samples
Zhao Song, Aleksandar Dogandzic
We propose a Bayesian expectation-maximization (EM) algorithm for reconstructing Markov-tree sparse signals via belief propagation. The measurements follow an underdetermined linea…