Almost Euclidean subspaces of \ell_1^N via expander codes

Simple item page
dc.creatorGuruswami, Venkatesan
dc.creatorLee, James R.
dc.creatorRazborov, Alexander
dc.date2007-09-06
dc.date2009-03-26
dc.date.accessioned2026-07-07T12:56:12Z
dc.date.available2026-07-07T12:56:12Z
dc.descriptionWe give an explicit (in particular, deterministic polynomial time) construction of subspaces X of R^N of dimension (1-o(1))N such that for every element x in X, |x|_1 and N^{1/2} |x|_2 are equivalent up to a factor of (log N)^{log log log N}. If we are allowed to use N^{o(1)} random bits, this factor can be improved to poly(log N). Our construction makes use of unbalanced bipartite graphs to impose local linear constraints on vectors in the subspace, and our analysis relies on expansion properties of the graph. This is inspired by similar constructions of error-correcting codes.
dc.identifierhttps://arxiv.org/abs/0709.0887
dc.identifierhttp://arxiv.org/abs/0709.0887
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/224503
dc.subjectMetric Geometry
dc.subjectFunctional Analysis
dc.titleAlmost Euclidean subspaces of \ell_1^N via expander codes
dc.typetext

Files

Collections

arXiv