{"data":{"id":"10.48550/arxiv.1005.1440","type":"dois","attributes":{"doi":"10.48550/arxiv.1005.1440","prefix":"10.48550","suffix":"arxiv.1005.1440","identifiers":[{"identifier":"1005.1440","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"1005.1440"}],"creators":[{"name":"Rojo, Javier","nameType":"Personal","givenName":"Javier","familyName":"Rojo","affiliation":[],"nameIdentifiers":[]},{"name":"Nguyen, Tuan","nameType":"Personal","givenName":"Tuan","familyName":"Nguyen","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Improving the Johnson-Lindenstrauss Lemma"}],"publisher":"arXiv","container":{},"publicationYear":2010,"subjects":[{"lang":"en","subject":"Machine Learning (stat.ML)","subjectScheme":"arXiv"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2010-05-10T03:05:23Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2010-05-11T00:01:24Z","dateType":"Updated","dateInformation":"v1"},{"date":"2010-05","dateType":"Available","dateInformation":"v1"},{"date":"2010","dateType":"Issued"}],"language":null,"types":{"ris":"GEN","bibtex":"misc","citeproc":"article","schemaOrg":"CreativeWork","resourceType":"Article","resourceTypeGeneral":"Preprint"},"relatedIdentifiers":[],"relatedItems":[],"sizes":[],"formats":[],"version":"1","rightsList":[{"rights":"arXiv.org perpetual, non-exclusive license","rightsUri":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/"}],"descriptions":[{"description":"The Johnson-Lindenstrauss Lemma allows for the projection of $n$ points in $p-$dimensional Euclidean space onto a $k-$dimensional Euclidean space, with $k \\ge \\frac{24\\ln \\emph{n}}{3ε^2-2ε^3}$, so that the pairwise distances are preserved within a factor of $1\\pmε$. Here, working directly with the distributions of the random distances rather than resorting to the moment generating function technique, an improvement on the lower bound for $k$ is obtained. The additional reduction in dimension when compared to bounds found in the literature, is at least $13\\%$, and, in some cases, up to $30\\%$ additional reduction is achieved. Using the moment generating function technique, we further provide a lower bound for $k$ using pairwise $L_2$ distances in the space of points to be projected and pairwise $L_1$ distances in the space of the projected points. Comparison with the results obtained in the literature shows that the bound presented here provides an additional $36-40\\%$ reduction.","descriptionType":"Abstract"},{"description":"24 pages, 2 tables","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4xMDA1LjE0NDA8L2lkZW50aWZpZXI+CiAgPGFsdGVybmF0ZUlkZW50aWZpZXJzPgogICAgPGFsdGVybmF0ZUlkZW50aWZpZXIgYWx0ZXJuYXRlSWRlbnRpZmllclR5cGU9ImFyWGl2Ij4xMDA1LjE0NDA8L2FsdGVybmF0ZUlkZW50aWZpZXI+CiAgPC9hbHRlcm5hdGVJZGVudGlmaWVycz4KICA8Y3JlYXRvcnM+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+Um9qbywgSmF2aWVyPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5KYXZpZXI8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+Um9qbzwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5OZ3V5ZW4sIFR1YW48L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPlR1YW48L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+Tmd1eWVuPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogIDwvY3JlYXRvcnM+CiAgPHRpdGxlcz4KICAgIDx0aXRsZT5JbXByb3ZpbmcgdGhlIEpvaG5zb24tTGluZGVuc3RyYXVzcyBMZW1tYTwvdGl0bGU+CiAgPC90aXRsZXM+CiAgPHB1Ymxpc2hlcj5hclhpdjwvcHVibGlzaGVyPgogIDxwdWJsaWNhdGlvblllYXI+MjAxMDwvcHVibGljYXRpb25ZZWFyPgogIDxzdWJqZWN0cz4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPk1hY2hpbmUgTGVhcm5pbmcgKHN0YXQuTUwpPC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc3ViamVjdFNjaGVtZT0iRmllbGRzIG9mIFNjaWVuY2UgYW5kIFRlY2hub2xvZ3kgKEZPUykiPkZPUzogQ29tcHV0ZXIgYW5kIGluZm9ybWF0aW9uIHNjaWVuY2VzPC9zdWJqZWN0PgogIDwvc3ViamVjdHM+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxMC0wNS0xMFQwMzowNToyM1o8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxMC0wNS0xMVQwMDowMToyNFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iQXZhaWxhYmxlIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDEwLTA1PC9kYXRlPgogIDwvZGF0ZXM+CiAgPHJlc291cmNlVHlwZSByZXNvdXJjZVR5cGVHZW5lcmFsPSJQcmVwcmludCI+QXJ0aWNsZTwvcmVzb3VyY2VUeXBlPgogIDx2ZXJzaW9uPjE8L3ZlcnNpb24+CiAgPHJpZ2h0c0xpc3Q+CiAgICA8cmlnaHRzIHJpZ2h0c1VSST0iaHR0cDovL2FyeGl2Lm9yZy9saWNlbnNlcy9ub25leGNsdXNpdmUtZGlzdHJpYi8xLjAvIj5hclhpdi5vcmcgcGVycGV0dWFsLCBub24tZXhjbHVzaXZlIGxpY2Vuc2U8L3JpZ2h0cz4KICA8L3JpZ2h0c0xpc3Q+CiAgPGRlc2NyaXB0aW9ucz4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9IkFic3RyYWN0Ij5UaGUgSm9obnNvbi1MaW5kZW5zdHJhdXNzIExlbW1hIGFsbG93cyBmb3IgdGhlIHByb2plY3Rpb24gb2YgJG4kIHBvaW50cyBpbiAgJHAtJGRpbWVuc2lvbmFsIEV1Y2xpZGVhbiBzcGFjZSBvbnRvIGEgJGstJGRpbWVuc2lvbmFsIEV1Y2xpZGVhbiBzcGFjZSwgd2l0aCAkayBcZ2UgXGZyYWN7MjRcbG4gXGVtcGh7bn19ezPOtV4yLTLOtV4zfSQsIHNvIHRoYXQgdGhlIHBhaXJ3aXNlIGRpc3RhbmNlcyBhcmUgcHJlc2VydmVkIHdpdGhpbiBhIGZhY3RvciBvZiAkMVxwbc61JC4gSGVyZSwgd29ya2luZyBkaXJlY3RseSB3aXRoIHRoZSBkaXN0cmlidXRpb25zIG9mIHRoZSByYW5kb20gZGlzdGFuY2VzIHJhdGhlciB0aGFuIHJlc29ydGluZyB0byB0aGUgbW9tZW50IGdlbmVyYXRpbmcgZnVuY3Rpb24gdGVjaG5pcXVlLCBhbiBpbXByb3ZlbWVudCBvbiB0aGUgbG93ZXIgYm91bmQgZm9yICRrJCBpcyBvYnRhaW5lZC4gVGhlIGFkZGl0aW9uYWwgcmVkdWN0aW9uIGluIGRpbWVuc2lvbiB3aGVuIGNvbXBhcmVkIHRvIGJvdW5kcyBmb3VuZCBpbiB0aGUgbGl0ZXJhdHVyZSwgaXMgYXQgbGVhc3QgJDEzXCUkLCBhbmQsIGluIHNvbWUgY2FzZXMsIHVwIHRvICQzMFwlJCBhZGRpdGlvbmFsIHJlZHVjdGlvbiBpcyBhY2hpZXZlZC4gVXNpbmcgdGhlIG1vbWVudCBnZW5lcmF0aW5nIGZ1bmN0aW9uIHRlY2huaXF1ZSwgd2UgZnVydGhlciBwcm92aWRlIGEgbG93ZXIgYm91bmQgZm9yICRrJCB1c2luZyBwYWlyd2lzZSAkTF8yJCBkaXN0YW5jZXMgaW4gdGhlIHNwYWNlIG9mIHBvaW50cyB0byBiZSBwcm9qZWN0ZWQgYW5kIHBhaXJ3aXNlICRMXzEkIGRpc3RhbmNlcyBpbiB0aGUgc3BhY2Ugb2YgdGhlIHByb2plY3RlZCBwb2ludHMuIENvbXBhcmlzb24gd2l0aCB0aGUgcmVzdWx0cyBvYnRhaW5lZCBpbiB0aGUgbGl0ZXJhdHVyZSAgc2hvd3MgdGhhdCB0aGUgYm91bmQgcHJlc2VudGVkIGhlcmUgcHJvdmlkZXMgYW4gYWRkaXRpb25hbCAkMzYtNDBcJSQgIHJlZHVjdGlvbi48L2Rlc2NyaXB0aW9uPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iT3RoZXIiPjI0IHBhZ2VzLCAyIHRhYmxlczwvZGVzY3JpcHRpb24+CiAgPC9kZXNjcmlwdGlvbnM+CjwvcmVzb3VyY2U+","url":"https://arxiv.org/abs/1005.1440","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-13T23:40:09.000Z","registered":"2022-03-13T23:40:09.000Z","published":"2010","updated":"2022-03-13T23:40:09.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.1005.1440","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}