Near-Optimal Bounds for Binary Embeddings of Arbitrary Sets

Samet Oymak, Ben Recht

Type: Preprint

Publication Date: 2015-01-01

Citations: 30

DOI: https://doi.org/10.48550/arxiv.1512.04433

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Binary Embedding: Fundamental Limits and Fast Algorithm	2015	Xinyang Yi Constantine Caramanis Eric Price
+	Binary Embedding: Fundamental Limits and Fast Algorithm	2015	Xinyang Yi Constantine Caramanis Eric Price
+ PDF Chat	Fast Metric Embedding into the Hamming Cube	2024	Sjoerd Dirksen Shahar Mendelson Alexander Stollenwerk
+	Binarized Johnson-Lindenstrauss embeddings	2020	Sjoerd Dirksen Alexander Stollenwerk
+	Binarized Johnson-Lindenstrauss embeddings.	2020	Sjoerd Dirksen Alexander Stollenwerk
+	Barriers for Faster Dimensionality Reduction	2022	Ora Nova Fandina Mikael Møller Høgsgaard Kasper Green Larsen
+	Near-Optimal Sample Complexity Bounds for Circulant Binary Embedding	2016	Samet Oymak
+	Near-Optimal Sample Complexity Bounds for Circulant Binary Embedding	2016	Samet Oymak
+ PDF Chat	Faster Binary Embeddings for Preserving Euclidean Distances	2020	Jinjie Zhang Rayan Saab
+	Faster Binary Embeddings for Preserving Euclidean Distances	2020	Jinjie Zhang Rayan Saab
+	Small Width, Low Distortions: Quantized Random Embeddings of Low-complexity Sets	2015	Laurent Jacques
+	Fast metric embedding into the Hamming cube	2022	Sjoerd Dirksen Shahar Mendelson Alexander Stollenwerk
+	Small Width, Low Distortions: Quantized Random Embeddings of Low-complexity Sets	2015	Laurent Jacques
+ PDF Chat	Near-optimal sample complexity bounds for circulant binary embedding	2017	Samet Oymak Christos Thrampoulidis Babak Hassibi
+	Optimal compression of approximate Euclidean distances	2016	Noga Alon Bo’az Klartag
+	Fast binary embeddings with Gaussian circulant matrices: improved bounds	2016	Sjoerd Dirksen Alexander Stollenwerk
+	Fast binary embeddings with Gaussian circulant matrices: improved bounds	2016	Sjoerd Dirksen Alexander Stollenwerk
+	Near-Optimal (Euclidean) Metric Compression	2016	Piotr Indyk Tal Wagner
+ PDF Chat	Average-Distortion Sketching	2024	Yuanyuan Bao Anubhav Baweja Nicolas Menand Erik Waingarten Nathan S. White Tian Zhang
+	Near-optimal (euclidean) metric compression	2017	Piotr Indyk Tal Wagner

Works That Cite This (25)

Action	Title	Year	Authors
+ PDF Chat	Representation and coding of signal geometry	2017	Petros T. Boufounos Shantanu Rane Hassan Mansour
+	Near-Optimal Sample Complexity Bounds for Circulant Binary Embedding	2016	Samet Oymak
+ PDF Chat	The rare eclipse problem on tiles: Quantised embeddings of disjoint convex sets	2017	Valerio Cambareri Chunlei Xu Laurent Jacques
+	The Generalized Lasso with Nonlinear Observations and Generative Priors	2020	Zhaoqiang Liu Jonathan Scarlett
+ PDF Chat	Uniform Exact Reconstruction of Sparse Signals and Low-Rank Matrices From Phase-Only Measurements	2023	Junren Chen Michael K. Ng
+ PDF Chat	A Unified Approach to Uniform Signal Recovery From Nonlinear Observations	2022	Martin Genzel Alexander Stollenwerk
+	Binarized Johnson-Lindenstrauss embeddings.	2020	Sjoerd Dirksen Alexander Stollenwerk
+	Non-Gaussian Hyperplane Tessellations and Robust One-Bit Compressed Sensing	2018	Sjoerd Dirksen Shahar Mendelson
+ PDF Chat	Near-optimal sample complexity bounds for circulant binary embedding	2017	Samet Oymak Christos Thrampoulidis Babak Hassibi
+ PDF Chat	Time for dithering: fast and quantized random embeddings via the restricted isometry property	2017	Laurent Jacques Valerio Cambareri

Works Cited by This (15)

Action	Title	Year	Authors
+	Small width, low distortions: quasi-isometric embeddings with quantized sub-Gaussian random projections.	2015	Laurent Jacques
+	Hashing for Similarity Search: A Survey	2014	Jingdong Wang Heng Tao Shen Jingkuan Song Jianqiu Ji
+	High-dimensional estimation with geometric constraints	2014	Yaniv Plan Roman Vershynin Elena Yudovina
+ PDF Chat	Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors	2013	Laurent Jacques Jason N. Laska Petros T. Boufounos Richard G. Baraniuk
+	Introduction to the non-asymptotic analysis of random matrices	2010	Roman Vershynin
+	Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing	2009	David L. Donoho Jared Tanner
+	Universality laws for randomized dimension reduction, with applications	2015	Samet Oymak Joel A. Tropp
+	Revisiting the Nystrom Method for Improved Large-Scale Machine Learning	2013	Alex Gittens Michael W. Mahoney
+	Dimensionality Reduction for k-Means Clustering and Low Rank Approximation	2014	Michael B. Cohen Sam Elder Cameron Musco Christopher Musco Madalina Persu
+	Circulant Binary Embedding	2014	Felix X. Yu Sanjiv Kumar Yunchao Gong Shih‐Fu Chang