Author name cluster

Jean Bourgain

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

STOC Conference 2015 Conference Paper

Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space

Jean Bourgain
Sjoerd Dirksen
Jelani Nelson

Let Φ∈R m x n be a sparse Johnson-Lindenstrauss transform [52] with column sparsity s. For a subset T of the unit sphere and ε∈(0,1/2), we study settings for m,s to ensure E Φ sup x∈ T |Φ x| 2 2 - 1| < ε, i.e. so that Φ preserves the norm of every x ∈ T simultaneously and multiplicatively up to 1+ε. We introduce a new complexity parameter, which depends on the geometry of T, and show that it suffices to choose s and m such that this parameter is small. Our result is a sparse analog of Gordon's theorem, which was concerned with a dense Φ having i.i.d. Gaussian entries. We qualitatively unify several results related to the Johnson-Lindenstrauss lemma, subspace embeddings, and Fourier-based restricted isometries. Our work also implies new results in using the sparse Johnson-Lindenstrauss transform in randomized linear algebra, compressed sensing, manifold learning, and constrained least squares problems such as the Lasso.

Details

STOC Conference 2012 Conference Paper

Monotone expansion

Jean Bourgain
Amir Yehudayoff

This work presents an explicit construction of a family of monotone expanders, which are bi-partite expander graphs whose edge-set is defined by (partial) monotone functions. The family is essentially defined by the Mobius action of SL 2 (R), the group of 2 x 2 matrices with determinant one, on the interval [0,1]. No other proof-of-existence for monotone expanders is known, not even using the probabilistic method. The proof extends recent results on finite/compact groups to the non-compact scenario. Specifically, we show a product-growth theorem for SL 2 (R); roughly, that for every A ⊂ SL 2 (R) with certain properties, the size of AAA is much larger than that of A. We mention two applications of this construction: Dvir and Shpilka showed that it yields a construction of explicit dimension expanders, which are a generalization of standard expander graphs. Dvir and Wigderson proved that it yields the existence of explicit pushdown expanders, which are graphs that arise in Turing machine simulations.

Details

STOC Conference 2011 Conference Paper

Breaking the k 2 barrier for explicit RIP matrices

Jean Bourgain
Stephen J. Dilworth
Kevin Ford
Sergei Konyagin
Denka Kutzarova

We give a new explicit construction of n x N matrices satisfying the Restricted Isometry Property (RIP). Namely, for some ε>0, large k and k 2-ε ≤ N ≤ k 2+ε , we construct RIP matrices of order k with n=O(k 2-ε ). This overcomes the natural barrier n >> k 2 for proofs based on small coherence, which are used in all previous explicit constructions of RIP matrices. Key ingredients in our proof are new estimates for sumsets in product sets and for exponential sums with the products of sets possessing special additive structure.

Details