Skip navigation
Please use this identifier to cite or link to this item:
Title: Statistical and Computational Tradeoffs in High-dimensional Problems
Authors: Berthet, Quentin
Advisors: Rigollet, Philippe
Contributors: Operations Research and Financial Engineering Department
Keywords: Computational efficiency
Planted Clique
Sparse PCA
Subjects: Statistics
Computer science
Issue Date: 2014
Publisher: Princeton, NJ : Princeton University
Abstract: With the recent data revolution, statisticians are considering larger datasets, more sophisticated models, more complex problems. As a consequence, the algorithmic aspect of statistical methods can no longer be neglected in a world where computational power is the bottleneck, not the lack of observations. In this context, we present in this thesis results that establish fundamental limits in the statistical performance of computationally efficient procedures, for the problem of sparse principal component analysis. We will show how it is achieved through average-case reduction to the planted clique problem. We will also introduce further areas of research in this promising eld, related to the detection of planted satisability in boolean formulas.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Operations Research and Financial Engineering

Files in This Item:
File Description SizeFormat 
Berthet_princeton_0181D_10972.pdf1.11 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.