  We propose a dimensionality reducing matrix design based on training data
with constraints on its Frobenius norm and number of rows. Our design criteria
is aimed at preserving the distances between the data points in the
dimensionality reduced space as much as possible relative to their distances in
original data space. This approach can be considered as a deterministic
Bi-Lipschitz embedding of the data points. We introduce a scalable learning
algorithm, dubbed AMUSE, and provide a rigorous estimation guarantee by
leveraging game theoretic tools. We also provide a generalization
characterization of our matrix based on our sample data. We use compressive
sensing problems as an example application of our problem, where the Frobenius
norm design constraint translates into the sensing energy.
