We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Random Projection and Recovery for High Dimensional Optimization with Arbitrary Outliers.
- Authors
Huang, Jiawei; Qin, Ruizhe; Yang, Fan; Ding, Hu
- Abstract
Robust optimization problems have attracted considerable attention in recent years. In this paper, we focus on two fundamental robust optimization problems: SVM with outliers and k -center clustering with outliers. The key obstacle is that the outliers can be located arbitrarily in the space (e.g., by an attacker), and thus they are actually quite challenging combinatorial optimization problems. Their computational complexities can be very high especially in high dimensional spaces. The Johnson–Lindenstrauss (JL ) Transform is a popular random projection method for dimension reduction. Though the JL transform has been widely studied in the past decades, its effectiveness for dealing with high-dimensional optimizations with outliers has never been investigated before (to the best of our knowledge). Based on some novel insights from the geometry, we prove that the complexities of these two problems can be significantly reduced through the JL transform. Moreover, we prove that the solution in the dimensionality-reduced space can be efficiently recovered in the original ℝ d space while the quality is still preserved. To study its performance in practice, we compare different JL transform methods with several other well known dimension reduction methods in our experiments.
- Subjects
RANDOM projection method; ROBUST optimization; COMBINATORIAL optimization; COMPUTATIONAL complexity
- Publication
International Journal of Computational Geometry & Applications, 2022, Vol 32, Issue 3/4, p201
- ISSN
0218-1959
- Publication type
Article
- DOI
10.1142/S0218195922500078