On the equivalence of sparse statistical problems
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
2017
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/107375 |
| _version_ | 1826193810733924352 |
|---|---|
| author | Park, Sung Min, S.M. Massachusetts Institute of Technology |
| author2 | Guy Bresler. |
| author_facet | Guy Bresler. Park, Sung Min, S.M. Massachusetts Institute of Technology |
| author_sort | Park, Sung Min, S.M. Massachusetts Institute of Technology |
| collection | MIT |
| description | Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016. |
| first_indexed | 2024-09-23T09:45:46Z |
| format | Thesis |
| id | mit-1721.1/107375 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:45:46Z |
| publishDate | 2017 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1073752022-01-13T07:54:01Z On the equivalence of sparse statistical problems Park, Sung Min, S.M. Massachusetts Institute of Technology Guy Bresler. 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. Cataloged from PDF version of thesis. Includes bibliographical references (pages 43-47). Sparsity is a widely used and theoretically well understood notion that has allowed inference to be statistically and computationally possible in the high-dimensional setting. Sparse Principal Component Analysis (SPCA) and Sparse Linear Regression (SLR) are two problems that have a wide range of applications and have attracted a tremendous amount of attention in the last two decades as canonical examples of statistical problems in high dimension. A variety of algorithms have been proposed for both SPCA and SLR, but their literature has been disjoint for the most part. We have a fairly good understanding of conditions and regimes under which these algorithms succeed. But is there be a deeper connection between computational structure of SPCA and SLR? In this paper we show how to efficiently transform a blackbox solver for SLR into an algorithm for SPCA. Assuming the SLR solver satisfies prediction error guarantees achieved by existing efficient algorithms such as those based on the Lasso, we show that the SPCA algorithm derived from it achieves state of the art performance, matching guarantees for testing and for support recovery under the single spiked covariance model as obtained by the current best polynomial-time algorithms. Our reduction not only highlights the inherent similarity between the two problems, but also, from a practical standpoint, it allows one to obtain a collection of algorithms for SPCA directly from known algorithms for SLR. Experiments on simulated data show that these algorithms perform well. by Sung Min Park. S.M. 2017-03-10T15:07:43Z 2017-03-10T15:07:43Z 2016 2016 Thesis http://hdl.handle.net/1721.1/107375 973720220 eng MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission. http://dspace.mit.edu/handle/1721.1/7582 52 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Park, Sung Min, S.M. Massachusetts Institute of Technology On the equivalence of sparse statistical problems |
| title | On the equivalence of sparse statistical problems |
| title_full | On the equivalence of sparse statistical problems |
| title_fullStr | On the equivalence of sparse statistical problems |
| title_full_unstemmed | On the equivalence of sparse statistical problems |
| title_short | On the equivalence of sparse statistical problems |
| title_sort | on the equivalence of sparse statistical problems |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/107375 |
| work_keys_str_mv | AT parksungminsmmassachusettsinstituteoftechnology ontheequivalenceofsparsestatisticalproblems |