On the equivalence of sparse statistical problems

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.

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

• Park, Sung Min (Data scientist) Massachusetts Institute of Technology

Advisor dc:contributor.advisor

• Guy Bresler.

• Electrical Engineering and Computer Science.

Statement dc:rights

• 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.

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/107375

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/107375