English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In recent years, sparse principal component analysis has emerged as anextremely popular dimension reduction technique for high-dimensional data. Thetheoretical challenge, in the simplest case, is to estimate the leadingeigenvector of a population covariance matrix under the assumption that thiseigenvector is sparse. An impressive range of estimators have been proposed;some of these are fast to compute, while others are known to achieve theminimax optimal rate over certain Gaussian or sub-Gaussian classes. In thispaper, we show that, under a widely-believed assumption from computationalcomplexity theory, there is a fundamental trade-off between statistical andcomputational performance in this problem. More precisely, working with new,larger classes satisfying a restricted covariance concentration condition, weshow that there is an effective sample size regime in which no randomisedpolynomial time algorithm can achieve the minimax optimal rate. We also studythe theoretical performance of a (polynomial time) variant of the well-knownsemidefinite relaxation estimator, revealing a subtle interplay betweenstatistical and computational efficiency.

Statistical and computational trade-offs in estimation of sparse principal components