## NuMax: a convex approach for learning near-isometric linear embeddingsC. Hegde, A. C. Sankaranarayanan, W. Yin, and R. G. Baraniuk Published in IEEE Transactions on Signal Processing ## OverviewWe propose a novel framework for the deterministic construction of linear, near-isometric embeddings of ﬁnite sets of data points. Given a set of training points X in R^n, we consider the secant set S(X) that consists of all pairwise difference vectors of X, normalized to lie on the unit sphere. We formulate an affine rank minimization problem to construct a matrix Psi that preserves the norms of all the vectors in S(X) up to a distortion parameter delta. While affine rank minimization is NP-hard, we show that this problem can be relaxed to a convex program that can be solved using a tractable semideﬁnite program (SDP). To enable scalability of the proposed SDP to very large-scale problems, we adopt a two-stage approach. First, in order to reduce compute time, we develop a novel algorithm based on the Alternating Direction Method of Multipliers (ADMM) that we call nuclear norm minimization with Max-norm constraints (NuMax). Second, we develop a greedy, approximate version of NuMax based on the column generation method commonly used to solve large-scale linear programs. We demonstrate that our framework is useful for a number of applications in machine learning and signal processing via a range of experiments on large-scale synthetic and real datasets.
## Citation
« Back |