170 citations · 528 across the 46 of their papers we have counts for
5 papers · 1 filter
Random Projections for Linear Support Vector Machines
Saurabh Paul, Christos Boutsidis, Malik Magdon-Ismail +1
Let X be a data matrix of rank ρ, whose rows represent n points in d-dimensional space. The linear support vector machine constructs a hyperplane separator that maximizes the 1-nor…
Spreading Processes and Large Components in Ordered, Directed Random Graphs
Paul Horn, Malik Magdon-Ismail
Order the vertices of a directed random graph \math{v_1,...,v_n}; edge \math{(v_i,v_j)} for \math{i<j} exists independently with probability \math{p}. This random graph model is re…
The Fast Cauchy Transform and Faster Robust Linear Regression
Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail +3
We provide fast algorithms for overconstrained regression and related problems: for an input matrix and vector , in time we…
Near-Optimal Target Learning With Stochastic Binary Signals
Mithun Chakraborty, Sanmay Das, Malik Magdon-Ismail
We study learning in a noisy bisection model: specifically, Bayesian algorithms to learn a target value V given access only to noisy realizations of whether V is less than or great…
Near-optimal Coresets For Least-Squares Regression
Christos Boutsidis, Petros Drineas, Malik Magdon-Ismail
We study (constrained) least-squares regression as well as multiple response least-squares regression and ask the question of whether a subset of the data, a coreset, suffices to c…