Journal article
Random Projections for Classification: A Recovery Approach
IEEE transactions on information theory, Vol.60(11), pp.7300-7316
11/2014
DOI: 10.1109/TIT.2014.2359204
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 in the low-dimensional space, in this paper, we consider the recovery problem, i.e., how to accurately recover the optimal solution to the original high-dimensional optimization problem based on the solution learned after random projection. We present a simple algorithm, termed dual random projection, which 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 (approximately) low-rank and/or optimal solution is (approximately) sparse. We further show that the proposed algorithm can be applied iteratively to reducing the recovery error exponentially.
Details
- Title: Subtitle
- Random Projections for Classification: A Recovery Approach
- Creators
- Lijun Zhang - Nanjing UniversityMehrdad Mahdavi - Toyota Technological Institute at ChicagoRong Jin - Michigan State UniversityTianbao Yang - University of IowaShenghuo Zhu - Alibaba Group
- Resource Type
- Journal article
- Publication Details
- IEEE transactions on information theory, Vol.60(11), pp.7300-7316
- Publisher
- IEEE
- DOI
- 10.1109/TIT.2014.2359204
- ISSN
- 0018-9448
- eISSN
- 1557-9654
- Grant note
- N000141210431; N000141410631 / Office of Naval Research (10.13039/100000006) 61321491 / National Natural Science Foundation of China; National Science Foundation of China (10.13039/501100001809) IIS-1251031 / National Science Foundation (10.13039/100000001)
- Language
- English
- Date published
- 11/2014
- Academic Unit
- Computer Science
- Record Identifier
- 9984259500402771
Metrics
4 Record Views