Random Projections for Classification: A Recovery Approach

Lijun Zhang, Mehrdad Mahdavi, Rong Jin, Tianbao Yang, Shenghuo ZhuIEEE Trans. Information Theory 2014 · OpenReview

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...

Figure