《DRAFT On the Impossibility of Dimension Reduction in # 1 #》由会员分享，可在线阅读，更多相关《DRAFT On the Impossibility of Dimension Reduction in # 1 #（21页珍藏版）》请在金锄头文库上搜索。
1、DRAFTOn the Impossibility of Dimension Reduction in 1Bo BrinkmanPrinceton University Moses Charikar Princeton UniversityAbstractThe Johnson-Lindenstrauss Lemma shows that any n points in Euclidean space (with distances mea-sured by the 2 norm) may be mapped down to O(logn)/2) dimensions such that no
2、 pairwise distanceis distorted by more than a (1 + ) factor. Determining whether such dimension reduction is possiblein 1 has been an intriguing open question. Charikar and Sahai 7 recently showed lower bounds fordimension reduction in 1 that can be achieved by linear projections, and positive resul
3、ts for shortestpath metrics of restricted graph families. However the question of general dimension reduction in 1 wasstill open. For example, it was not known whether it is possible to reduce the number of dimensions toO(logn) with 1 + distortion.We show strong lower bounds for general dimension re
4、duction in 1. We give an explicit familyof n points in 1 such that any embedding with distortion requires n(1/2) dimensions. This provesthat there is no analog of the Johnson-Lindenstrauss Lemma for 1; in fact embedding with any constantdistortion requires n(1) dimensions. Further, embedding the poi
5、nts into 1 with 1+ distortion requiresn12O(log(1) dimensions. Our proof establishes this lower bound for shortest path metrics of series-parallel graphs. We make extensive use of linear programming and duality in devising our bounds. Weexpect that the tools and techniques we develop will be useful f
6、or future investigations of embeddingsinto 1.The full version of this paper may be found on Moses Charikars home page, http:/www.cs.princeton.edu/moses/papers/l1impossibility.ps.Email: brinkmancs.princeton.edu. Supported by a Frances Upton Fellowship and DOE grant DE-FG02-02ER25540.Email: mosescs.pr
7、inceton.edu. Research supported by NSF ITR grant CCR-0205594 and DOE Early Career Princi-pal Investigator award DE-FG02-02ER25540.DRAFT1 IntroductionDimension reduction refers to mapping points in a high dimensional space to a space with low dimensionswhile approximately preserving some property of
8、the original points. We will be interested in dimensionreduction techniques that map dp to dp and approximately preserve pairwise distances of points. Givenmetric spaces (M1,d1) and (M2,d2), an embedding : M1 M2 is said to be an embedding of M1 intoM2 with distortion if,1 u,v M1, d1(u,v) d2(u),(v) d
9、1(u,v).The fundamental result in this area is the Johnson-Lindenstrauss lemma 17 which shows that any setof n points in Euclidean space can be mapped down to O(logn)/2) dimensions such that all distances aredistorted by at most 1 + . Moreover, such a mapping can be computed with high probability by
10、simplyprojecting the set of points on randomly chosen unit vectors. 2Metric embeddings have traditionally been studied by functional analysts, and have recently attracteda lot of attention in the theoretical computer science community due to connections to approximation al-gorithms and the design of
11、 efficient algorithms. Dimensionality reduction techniques using the Johnson-Lindenstrauss lemma and closely related methods have recently found numerous algorithmic applications:e.g. approximate searching for nearest neighbors 16, 18, 13, clustering of high dimensional point sets8, 23, streaming co
12、mputation 3, 14 and so on. (See the recent survey by Indyk 15.)The Johnson-Lindenstrauss lemma has proved to be a particularly useful tool since the 2 norm is acommonly used norm in various settings. A natural question to ask is whether there exists an analogue ofthe Johnson-Lindenstrauss lemma for
13、other p norms. Surprisingly little is known about this question. Inparticular, the dimension reduction question for the 1 norm stands out and has attracted attention in severalrecent surveys on the subject of metric embeddings. This question is interesting both because of its inherenttheoretical app
14、eal as well as its potential algorithmic applications. Indyk 15, in his tutorial on algorithmicapplications of embeddings in FOCS 01, asks: “Is there an analog of JL lemma for other norms, especially1? This would give a powerful technique for designing approximation algorithms for 1 norms . . . ”. L
15、inial19, in his article on finite metric spaces at the International Congress of Mathematicians in 2002, says thefollowing about the “mysterious 1”: “We know much less about metric embeddings into 1, and the attemptsto understand them give rise to many intriguing open problems . . . What is the smal
16、lest k = k(n,) so thatevery n-point metric in 1 can be embedded into k1 with distortion 0. The lower bound is trivial and the upperbound is from 25, 26.”Known results on dimension reduction: Ball 5 studied upper and lower bounds on the minimum di-mension required for isometric embeddings in p, proving linear lower bounds and quadratic upper bounds.The book by Deza and Laurent 10 gives a very good o
