Learning Near-Isometric Linear Embeddings

30 Oct
Computer Science Colloquium Series
Richard Baraniuk, Rice University
Thursday, October 30, 2014 -
4:00pm to 5:15pm
Maxwell Dworkin G115

In many machine learning and signal processing applications, we seek a low-dimensional representation (or embedding) of data that live in a high-dimensional ambient space.  The classical principal components analysis (PCA) approach linearly maps the data into the lower-dimensional subspace spanned by the dominant eigenvectors of the data covariance matrix.  While simple and computationally efficient, PCA suffers from an important drawback: the resulting embedding can arbitrarily distort pairwise distances between sample data points.  The neoclassical random projections approach maps the data into a random lower-dimensional subspace.  While also simple, random projections offer only probabilistic and asymptotic performance guarantees and, moreover, cannot leverage any special geometric structure of the data that might be present.  In this talk, we introduce a new framework for the deterministic construction of linear, near-isometric embeddings of a finite set of data points.  Our formulation is based on an affine rank minimization problem that we relax into a tractable semidefinite program (SDP).  The resulting Nuclear norm minimization with Max-norm constraints (NuMax) framework has a number of applications in machine learning and signal processing, which we demonstrate via a range of experiments on large-scale datasets.

Speaker Bio: 

Richard G. Baraniuk is the Victor E. Cameron Professor of Electrical and Computer Engineering at Rice University.  His research interests lie in new theory, algorithms, and hardware for sensing, signal processing, and machine learning.  He is a Fellow of the IEEE and AAAS, a Thomson Reuters’ Highly Cited Researcher, and has received national young investigator awards from the US NSF and ONR, the Rosenbaum Fellowship from the Isaac Newton Institute of Cambridge University, the ECE Young Alumni Achievement Award from the University of Illinois, and the Wavelet Pioneer and Compressive Sampling Pioneer Awards from SPIE.  His work on the Rice single-pixel compressive camera has been widely reported in the popular press and was selected by MIT Technology Review as a TR10 Top 10 Emerging Technology for 2007.  For his teaching and education projects, including Connexions (cnx.org) and OpenStax College (openstaxcollege.org), he has received the C. Holmes MacDonald National Outstanding Teaching Award from Eta Kappa Nu, Tech Museum of Innovation Laureate Award, the Internet Pioneer Award from the Berkman Center for Internet and Society at Harvard Law School, the World Technology Award for Education, the IEEE-SPS Education Award, and the WISE Education Award.

Jelani Nelson
Gioia Sweetland