A unified framework for linear dimensionality reduction in L1

Publication date 8 September 2016

Abstract: For a family of interpolation norms

| c d o t |_{1, 2, s}

on

m a t h b b R^{n}

, we provide a distribution over random matrices

P h i_{s} i n m a t h b b R^{m i m e s n}

parametrized by sparsity level

s

such that for a fixed set

X

of

K

points in

m a t h b b R^{n}

, if

m g e q C s l o g (K)

then with high probability,

f r a c 12 | x |_{1, 2, s} l e q | P h i_{s} (x) |_{1} l e q 2 | x |_{1, 2, s}

for all

x i n X

. Several existing results in the literature reduce to special cases of this result at different values of

s

: for

s = n

,

| x |_{1, 2, n} e q u i v | x |_{1}

and we recover that dimension reducing linear maps can preserve the

e l l_{1}

-norm up to a distortion proportional to the dimension reduction factor, which is known to be the best possible such result. For

s = 1

,

| x |_{1, 2, 1} e q u i v | x |_{2}

, and we recover an

e l l_{2} / e l l_{1}

variant of the Johnson-Lindenstrauss Lemma for Gaussian random matrices. Finally, if

x

is

s

-sparse, then

| x |_{1, 2, s} = | x |_{1}

and we recover that

s

-sparse vectors in

e l l_{1}^{n}

embed into

e l l_{1}^{m a t h c a l O (s l o g (n))}

via sparse random matrix constructions.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: A unified framework for linear dimensionality reduction in L1