Linear Dimension Reduction Approximately Preserving Level-Sets of the 1-Norm

<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>

Author dc:creator

• Casey, Michael P.

Advisor dc:contributor.advisor

• Mukherjee, Sayan

• Mathematics

Handle dc:identifier.uri

https://hdl.handle.net/10161/18836

OAI identifier oai:identifier

oai:dukespace.lib.duke.edu:10161/18836