  Random projections have been applied in many machine learning algorithms.
However, whether margin is preserved after random projection is non-trivial and
not well studied. In this paper we analyse margin distortion after random
projection, and give the conditions of margin preservation for binary
classification problems. We also extend our analysis to margin for multiclass
problems, and provide theoretical bounds on multiclass margin on the projected
data.
