Random Projections for Classification: A Recovery Approach
Lists
Only you see this
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.
BibTeX
@article{zhang2014random,
author = {Lijun Zhang and Mehrdad Mahdavi and Rong Jin and Tianbao Yang and Shenghuo Zhu},
title = {{Random Projections for Classification: A Recovery Approach}},
journal = {IEEE Trans. Information Theory},
year = {2014},
url = {https://openreview.net/forum?id=_AlBWBQ2X7d},
}Loading related content...