Nearly tight oblivious subspace embeddings by trace inequalities
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2016
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/105577 |
| _version_ | 1811080424423686144 |
|---|---|
| author | Cohen, Michael Benjamin. |
| author2 | Jonathan Kelner. |
| author_facet | Jonathan Kelner. Cohen, Michael Benjamin. |
| author_sort | Cohen, Michael Benjamin. |
| collection | MIT |
| description | Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016. |
| first_indexed | 2024-09-23T11:31:27Z |
| format | Thesis |
| id | mit-1721.1/105577 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:31:27Z |
| publishDate | 2016 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1055772019-04-12T17:32:40Z Nearly tight oblivious subspace embeddings by trace inequalities Cohen, Michael Benjamin. Jonathan Kelner. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 17-18). 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). by Michael B. Cohen. S.M. 2016-12-05T19:11:19Z 2016-12-05T19:11:19Z 2016 2016 Thesis http://hdl.handle.net/1721.1/105577 964450957 eng 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. http://dspace.mit.edu/handle/1721.1/7582 24 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Cohen, Michael Benjamin. Nearly tight oblivious subspace embeddings by trace inequalities |
| title | Nearly tight oblivious subspace embeddings by trace inequalities |
| title_full | Nearly tight oblivious subspace embeddings by trace inequalities |
| title_fullStr | Nearly tight oblivious subspace embeddings by trace inequalities |
| title_full_unstemmed | Nearly tight oblivious subspace embeddings by trace inequalities |
| title_short | Nearly tight oblivious subspace embeddings by trace inequalities |
| title_sort | nearly tight oblivious subspace embeddings by trace inequalities |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/105577 |
| work_keys_str_mv | AT cohenmichaelbenjamin nearlytightoblivioussubspaceembeddingsbytraceinequalities |