NuMax: A Convex Approach for Learning Near-Isometric Linear Embeddings

Chinmay Hegde, Aswin C. Sankaranarayanan, Wotao Yin, Richard G. Baraniuk

Research output: Contribution to journalArticle

37 Scopus citations

Abstract

We propose a novel framework for the deterministic construction of linear, near-isometric embeddings of a finite set of data points. Given a set of training points x C ℝn, we consider the secant set S(x)that consists of all pairwise difference vectors of , normalized to lie on the unit sphere. We formulate an affine 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 semidefinite 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 signal processing applications via a range of experiments on large-scale synthetic and real datasets.

Original languageEnglish (US)
Article number7145475
Pages (from-to)6109-6121
Number of pages13
JournalIEEE Transactions on Signal Processing
Volume63
Issue number22
DOIs
StatePublished - Nov 15 2015

Keywords

  • Approximate nearest neighbors
  • classification
  • compressive sensing
  • dimensionality reduction

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'NuMax: A Convex Approach for Learning Near-Isometric Linear Embeddings'. Together they form a unique fingerprint.

Cite this