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

## Date

2019

## Authors

## Advisors

## Journal Title

## Journal ISSN

## Volume Title

## Repository Usage Stats

views

downloads

## 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).

## Type

## Department

## Description

## Provenance

## Subjects

## Citation

## Permalink

## Citation

Casey, Michael P. (2019). *Linear Dimension Reduction Approximately Preserving Level-Sets of the 1-Norm*. Dissertation, Duke University. Retrieved from https://hdl.handle.net/10161/18836.

## Collections

Except where otherwise noted, student scholarship that was shared on DukeSpace after 2009 is made available to the public under a Creative Commons Attribution / Non-commercial / No derivatives (CC-BY-NC-ND) license. All rights in student work shared on DukeSpace before 2009 remain with the author and/or their designee, whose permission may be required for reuse.