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