Subspace embeddings for the L 1 -norm with applications

We show there is a distribution over linear mappings R:l 1 n -> l 1 O(d log d) , such that with arbitrarily large constant probability, for any fixed d-dimensional subspace L, for all x ∈ L we have |x| 1 ≤ |Rx| 1 = O(d log d)|x| 1 . This provides the first analogue of the ubiquitous subspace Johnson-Lindenstrauss embedding for the l 1 -norm. Importantly, the target dimension and distortion are independent of the ambient dimension n. We give several applications of this result. First, we give a faster algorithm for computing well-conditioned bases. Our algorithm is simple, avoiding the linear programming machinery required of previous algorithms. We also give faster algorithms for least absolute deviation regression and l 1 -norm best fit hyperplane problems, as well as the first single pass streaming algorithms with low space for these problems. These results are motivated by practical problems in image analysis, spam detection, and tatistics, where the l 1 -norm is used in studies where outliers may be safely and effectively ignored. This is because the l 1 -norm is more robust to outliers than the l 2 -norm.

Authors

• Christian Sohler
• David P. Woodruff

Keywords

• data stream algorithms
• hyperplane fitting
• regression
• well-conditioned basis