170 citations · 909 across the 66 of their papers we have counts for
9 papers · 1 filter
Randomized Learning of the Second-Moment Matrix of a Smooth Function
Armin Eftekhari, Michael B. Wakin, Ping Li +1
Consider an open set , equipped with a probability measure . An important characteristic of a smooth function $f:\mathbb{D}\rightarrow\mathbb{R}…
A polynomial-time relaxation of the Gromov-Hausdorff distance
Soledad Villar, Afonso S. Bandeira, Andrew J. Blumberg +1
The Gromov-Hausdorff distance provides a metric on the set of isometry classes of compact metric spaces. Unfortunately, computing this metric directly is believed to be computation…
Improved bounds for sparse recovery from subsampled random convolutions
Shahar Mendelson, Holger Rauhut, Rachel Ward
We study the recovery of sparse vectors from subsampled random convolutions via -minimization. We consider the setup in which both the subsampling locations as well as the…
MC^2: A Two-Phase Algorithm for Leveraged Matrix Completion
Armin Eftekhari, Michael B. Wakin, Rachel A. Ward
Leverage scores, loosely speaking, reflect the importance of the rows and columns of a matrix. Ideally, given the leverage scores of a rank- matrix ,…
Batched Stochastic Gradient Descent with Weighted Sampling
Deanna Needell, Rachel Ward
We analyze a batched variant of Stochastic Gradient Descent (SGD) with weighted sampling distribution for smooth and non-smooth objective functions. We show that by distributing th…
Exact Recovery of Chaotic Systems from Highly Corrupted Data
Giang Tran, Rachel Ward
Learning the governing equations in dynamical systems from time-varying measurements is of great interest across different scientific fields. This task becomes prohibitive when suc…
A near-stationary subspace for ridge approximation
Paul G. Constantine, Armin Eftekhari, Jeffrey Hokanson +1
Response surfaces are common surrogates for expensive computer simulations in engineering analysis. However, the cost of fitting an accurate response surface increases exponentiall…
Fast Cross-Polytope Locality-Sensitive Hashing
Christopher Kennedy, Rachel Ward
We provide a variant of cross-polytope locality sensitive hashing with respect to angular distance which is provably optimal in asymptotic sensitivity and enjoys $\mathcal{O}(d \ln…
Clustering subgaussian mixtures by semidefinite programming
Dustin G. Mixon, Soledad Villar, Rachel Ward
We introduce a model-free relax-and-round algorithm for k-means clustering based on a semidefinite relaxation due to Peng and Wei. The algorithm interprets the SDP output as a deno…