154 citations · 861 across the 94 of their papers we have counts for
5 papers · 1 filter
Near-Optimal Bounds for Binary Embeddings of Arbitrary Sets
Samet Oymak, Ben Recht
We study embedding a subset of the unit sphere to the Hamming cube . We characterize the tradeoff between distortion and sample complexity in terms of the Gaus…
Universality laws for randomized dimension reduction, with applications
Samet Oymak, Joel A. Tropp
Dimension reduction is the process of embedding high-dimensional data into a lower dimensional space to facilitate its analysis. In the Euclidean setting, one fundamental technique…
Parallel Correlation Clustering on Big Graphs
Xinghao Pan, Dimitris Papailiopoulos, Samet Oymak +3
Given a similarity graph between items, correlation clustering (CC) groups similar items together and dissimilar ones apart. One of the most popular CC algorithms is KwikCluster: a…
Sharp Time--Data Tradeoffs for Linear Inverse Problems
Samet Oymak, Benjamin Recht, Mahdi Soltanolkotabi
In this paper we characterize sharp time-data tradeoffs for optimization problems used for solving linear inverse problems. We focus on the minimization of a least-squares objectiv…
Isometric sketching of any set via the Restricted Isometry Property
Samet Oymak, Benjamin Recht, Mahdi Soltanolkotabi
In this paper we show that for the purposes of dimensionality reduction certain class of structured random matrices behave similarly to random Gaussian matrices. This class include…