A Subspace Embedding Method in L2 Norm via Fast Cauchy Transform

Abstract EN

We propose a subspace embedding method via Fast Cauchy Transform (FCT) in L2 norm.

It is motivated by and complements the work of the subspace embedding method in Lp norm, for all p∈[1,∞] except p = 2, by K.

L.

Clarkson (ACM-SIAM, 2013).

Unlike the traditionally used orthogonal basis in Johnson-Lindenstrauss (JL) embedding, we employ the well-conditioned basis in L2 norm to obtain concentration property of FCT in L2 norm.