Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Recovering Optimal Solution by Dual Random Projection

Speaker  Rong Jin

Affiliation  Michigan State University

Host  Dengyong Zhou

Duration  01:16:54

Date recorded  5 August 2014

Random projection has been widely used in data classification. It maps high-dimensional data into a low dimensional space 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 solution to the optimization problem in the original 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 to the low-dimensional optimization problem to recover the solution to the original optimization problem. Our theoretical analysis shows that with a high probability, the proposed algorithm is able to accurately recover the optimal solution in the high dimensional space, provided that the data matrix is of low rank. We also examine the relationship between compressive sensing and the problem of recovering optimal solution using random projection.

©2014 Microsoft Corporation. All rights reserved.
> Recovering Optimal Solution by Dual Random Projection