C. Hegde, A. C. Sankaranarayanan, W. Yin, and R. G. Baraniuk, "A Convex Approach for Learning Near-Isometric Linear Embeddings," submitted to Journal of Machine Learning Research, 2012
Abstract: We propose a novel framework for the deterministic construction of linear, near-isometric embeddings of a nite set of data points. Given a set of training points X, we consider the secant set S(X) that consists of all pairwise di fference vectors of X, normalized to lie on the unit sphere. We formulate an ane rank minimization problem to construct a matrix that preserves the norms of all the vectors in S(X) up to a distortion parameter . While affine rank minimization is NP-hard, we show that this problem can be relaxed to a convex formulation that can be solved using a tractable semide nite program (SDP). In order to enable scalability of our 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) to solve the SDP. 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.
The above example illustrates the superior performance of NuMax on the MNIST dataset of handwritten digits (see (a)). We construct a training dataset S(X) comprising S = 3000 secant images and estimate the variation of the isometry constant that measures the distortion of the embedding as a function of the number of measurements M. The results of this experiment are plotted in (b) in comparison to principal components analysis (PCA) and random projections. For a distortion parameter =0.2, NuMax produces an embedding with 8x fewer measurements than PCA. In essence, NuMax provides the best
possible rate-distortion curve in terms of compressing the given image database.
A computationally efficient NuMax toolbox is available here.