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

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

    Research output: Contribution to journalArticlepeer-review


    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
    Issue number22
    StatePublished - Nov 15 2015


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

    ASJC Scopus subject areas

    • Signal Processing
    • Electrical and Electronic Engineering


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

    Cite this