### 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 language | English (US) |
---|---|

Article number | 7145475 |

Pages (from-to) | 6109-6121 |

Number of pages | 13 |

Journal | IEEE Transactions on Signal Processing |

Volume | 63 |

Issue number | 22 |

DOIs | |

State | Published - 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

*IEEE Transactions on Signal Processing*,

*63*(22), 6109-6121. [7145475]. https://doi.org/10.1109/TSP.2015.2452228