Linear Dimension Reduction Approximately Preserving Level-Sets of the 1-Norm
dc.contributor.advisor | Mukherjee, Sayan | |
dc.contributor.author | Casey, Michael P. | |
dc.date.accessioned | 2019-06-07T19:49:46Z | |
dc.date.available | 2019-06-07T19:49:46Z | |
dc.date.issued | 2019 | |
dc.department | Mathematics | |
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 | ||
dc.subject | Mathematics | |
dc.title | Linear Dimension Reduction Approximately Preserving Level-Sets of the 1-Norm | |
dc.type | Dissertation |
Files
Original bundle
- Name:
- Casey_duke_0066D_15247.pdf
- Size:
- 500.24 KB
- Format:
- Adobe Portable Document Format