Recovering the Optimal Solution by Dual Random Projection
Preprint
Abstract
Random projection has been widely used in data classification. It maps high-dimensional data into a low-dimensional subspace in order to reduce the computational cost in solving the related optimization problem. While previous studies are focused on analyzing the classification performance of using random projection, in this work, we consider the recovery problem, i.e., how to accurately recover the optimal solution to the original optimization problem in the high-dimensional space based on the solution learned from the subspace spanned by random projections. We present a simple algorithm, termed Dual Random Projection, that uses the dual solution of the low-dimensional optimization problem to recover the optimal solution to the original problem. Our theoretical analysis shows that with a high probability, the proposed algorithm is able to accurately recover the optimal solution to the original problem, provided that the data matrix is of low rank or can be well approximated by a low rank matrix.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Random Projections for Linear Support Vector MachinesACM Transactions on Knowledge Discovery From Data, 2014
- An empirical feature-based learning algorithm producing sparse approximationsApplied and Computational Harmonic Analysis, 2012
- Tail Bounds for All Eigenvalues of a Sum of Random Matrices2011
- Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix DecompositionsSIAM Review, 2011
- Kernels as features: On kernels, margins, and low-dimensional mappingsMachine Learning, 2006
- Database-friendly random projections: Johnson-Lindenstrauss with binary coinsJournal of Computer and System Sciences, 2003