Nearly tight oblivious subspace embeddings by trace inequalities

We present a new analysis of sparse oblivious subspace embeddings, based on the "matrix Chernoff" technique. These are probability distributions over (relatively) sparse matrices such that for any d-dimensional subspace of Rn, the norms of all vectors in the subspace are simultaneously approximately preserved by the embedding with high probability-typically with parameters depending on d but not on n. The families of embedding matrices considered here are essentially the same as those in [NN13], but with better parameters (sparsity and embedding dimension). Because of this, this analysis essentially serves as a "drop-in replacement" for Nelson-Nguyen's, improving bounds on its many applications to problems such as as least squares regression and low-rank approximation. This new method is based on elementary tail bounds combined with matrix trace inequalities (Golden-Thompson or Lieb's theorem), and does not require combinatorics, unlike the Nelson-Nguyen approach. There are also variants of this method that are even simpler, at the cost of worse parameters. Furthermore, the bounds obtained are much tighter than previous ones, matching known lower bounds up to a single log(d) factor in embedding dimension (previous results had more log factors and also had suboptimal tradeoffs with sparsity).

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2016

Author dc:creator

• Cohen, Michael Benjamin.

Advisor dc:contributor.advisor

• Jonathan Kelner.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/105577

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/105577