We choose a family of matrices F : \\R^D \\to \\R^k and a metric \\rho on \\R^k such that with high
probability, \\rho(F (x), F (y)) is a strictly concave increasing function of ||x − y||_1 > 8 \\epsilon^2
for x, y \\in \\R^D , up to a multiplicative error of 1 ±\\epsilon. In particular, if X is a set of N
points in \\R^D , the target dimension k may be chosen as C ln^2 (N^{c+2})/(\\epsilon^2(1 −\\epsilon )^2), with
C a constant and \\epsilon > N^{−c} , to ensure all pairs of points of X of distance at least 8\\epsilon^2
are treated this way, with failure probability at most N^{-c} for c > 1. In some cases,
distances smaller than 8\\epsilon^2 can also be addressed. For distances larger than \\sqrt{1 +\\epsilon} ,
the target dimension can be reduced to C ln(N^{c+2})/(\\epsilon^2(1 −\\epsilon )^2).
","abstract_html":"<p>We choose a family of matrices F : \\R^D \\to \\R^k and a metric \\rho on \\R^k such that with high</p><p>probability, \\rho(F (x), F (y)) is a strictly concave increasing function of ||x − y||_1 > 8 \\epsilon^2</p><p>for x, y \\in \\R^D , up to a multiplicative error of 1 ±\\epsilon. In particular, if X is a set of N</p><p>points in \\R^D , the target dimension k may be chosen as C ln^2 (N^{c+2})/(\\epsilon^2(1 −\\epsilon )^2), with</p><p>C a constant and \\epsilon > N^{−c} , to ensure all pairs of points of X of distance at least 8\\epsilon^2</p><p>are treated this way, with failure probability at most N^{-c} for c > 1. In some cases,</p><p>distances smaller than 8\\epsilon^2 can also be addressed. For distances larger than \\sqrt{1 +\\epsilon} ,</p><p>the target dimension can be reduced to C ln(N^{c+2})/(\\epsilon^2(1 −\\epsilon )^2).</p>","abstract_has_math":false,"creators":["Casey, Michael P."],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Mukherjee, Sayan"],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019","date_published":"2019","updated_at":"2026-07-24T02:06:59Z","subjects":["Mathematics"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/10161/18836","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Mukherjee, Sayan"]},{"key":"dc:creator","label":"Author","values":["Casey, Michael P."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2019-06-07T19:49:46Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2019-06-07T19:49:46Z"]},{"key":"dc:date.issued","label":"Date","values":["2019"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10161/18836"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["We choose a family of matrices F : \\R^D \\to \\R^k and a metric \\rho on \\R^k such that with high
probability, \\rho(F (x), F (y)) is a strictly concave increasing function of ||x − y||_1 > 8 \\epsilon^2
for x, y \\in \\R^D , up to a multiplicative error of 1 ±\\epsilon. In particular, if X is a set of N
points in \\R^D , the target dimension k may be chosen as C ln^2 (N^{c+2})/(\\epsilon^2(1 −\\epsilon )^2), with
C a constant and \\epsilon > N^{−c} , to ensure all pairs of points of X of distance at least 8\\epsilon^2
are treated this way, with failure probability at most N^{-c} for c > 1. In some cases,
distances smaller than 8\\epsilon^2 can also be addressed. For distances larger than \\sqrt{1 +\\epsilon} ,
the target dimension can be reduced to C ln(N^{c+2})/(\\epsilon^2(1 −\\epsilon )^2).
"]},{"key":"dc:title","label":"Title","values":["Linear Dimension Reduction Approximately Preserving Level-Sets of the 1-Norm"]}]}],"canonical_facts":{"dc:contributor.advisor":["Mukherjee, Sayan"],"dc:creator":["Casey, Michael P."],"dc:date.accessioned":["2019-06-07T19:49:46Z"],"dc:date.available":["2019-06-07T19:49:46Z"],"dc:date.issued":["2019"],"dc:description.abstract":["We choose a family of matrices F : \\R^D \\to \\R^k and a metric \\rho on \\R^k such that with high
probability, \\rho(F (x), F (y)) is a strictly concave increasing function of ||x − y||_1 > 8 \\epsilon^2
for x, y \\in \\R^D , up to a multiplicative error of 1 ±\\epsilon. In particular, if X is a set of N
points in \\R^D , the target dimension k may be chosen as C ln^2 (N^{c+2})/(\\epsilon^2(1 −\\epsilon )^2), with
C a constant and \\epsilon > N^{−c} , to ensure all pairs of points of X of distance at least 8\\epsilon^2
are treated this way, with failure probability at most N^{-c} for c > 1. In some cases,
distances smaller than 8\\epsilon^2 can also be addressed. For distances larger than \\sqrt{1 +\\epsilon} ,
the target dimension can be reduced to C ln(N^{c+2})/(\\epsilon^2(1 −\\epsilon )^2).
"],"dc:identifier.uri":["https://hdl.handle.net/10161/18836"],"dc:subject":["Mathematics"],"dc:title":["Linear Dimension Reduction Approximately Preserving Level-Sets of the 1-Norm"],"dc:type":["Dissertation"]},"updated_at":"2026-07-24T02:06:59Z"}