NuMax: a convex approach for learning near-isometric linear embeddings

Published in IEEE Transactions on Signal Processing

Overview

We propose a novel framework for the deterministic construction of linear, near-isometric embeddings of finite 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 semidefinite 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.

To embed the digit 5, NuMax needs fewer measurements to reach the same level of isometry 
To embed the digit 5, NuMax needs fewer measurements to reach the same level of isometry

Citation

C. Hegde, A.C. Sankaranarayanan, W. Yin, and R.G. Baraniuk, NuMax: a convex approach for learning near-isometric linear embeddings, IEEE Transactions on Signal Processing 63(22), 6109-6121, 2015. DOI: 10.1109/TSP.2015.2452228


« Back