2008/06/27 by Ping Li, Li, Ping
Computer Science · Mathematics · #Algorithm #Artificial intelligence #Combinatorics #Computer science #Data Management and Algorithms #FOS: Computer and information sciences #Face and Expression Recognition #Gaussian #Machine Learning (cs.LG) #Mathematics #Matrix (chemical analysis) #Multivariate random variable #Pairwise comparison #Pairwise independence #Projection (relational algebra) #Random Matrices and Applications #Random variable #Simple (philosophy) #Statistics #cs.LG
paper · pdf · open access · doi:10.48550/arxiv.0806.4423
published in arXiv (Cornell University) (Cornell University)
arxiv created 2008/06/27 · openalex publication_date 2008/06/27 · arxiv updated 2009/12/01 · openalex created_date 2024/04/10 · openalex updated_date 2026/07/28
Applications in machine learning and data mining require computing pairwise Lp distances in a data matrix A. For massive high-dimensional data, computing all pairwise distances of A can be infeasible. In fact, even storing A or all pairwise distances of A in the memory may be also infeasible. This paper proposes a simple method for p = 2, 4, 6, ... We first decompose the lp (where p is even) distances into a sum of 2 marginal norms and p-1 ``inner products'' at different orders. Then we apply normal or sub-Gaussian random projections to approximate the resultant ``inner products,'' assuming that the marginal norms can be computed exactly by a linear scan. We propose two strategies for applying random projections. The basic projection strategy requires only one projection matrix but it is more difficult to analyze, while the alternative projection strategy requires p-1 projection matrices but its theoretical analysis is much easier. In terms of the accuracy, at least for p=4, the basic strategy is always more accurate than the alternative strategy if the data are non-negative, which is common in reality.