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

This paper investigates the fundamental limits for detecting ahigh-dimensional sparse matrix contaminated by white Gaussian noise from boththe statistical and computational perspectives. We consider $p\times p$matrices whose rows and columns are individually $k$-sparse. We provide a tightcharacterization of the statistical and computational limits for sparse matrixdetection, which precisely describe when achieving optimal detection is easy,hard, or impossible, respectively. Although the sparse matrices considered inthis paper have no apparent submatrix structure and the correspondingestimation problem has no computational issue at all, the detection problem hasa surprising computational barrier when the sparsity level $k$ exceeds thecubic root of the matrix size $p$: attaining the optimal detection boundary iscomputationally at least as hard as solving the planted clique problem.  The same statistical and computational limits also hold in the sparsecovariance matrix model, where each variable is correlated with at most $k$others. A key step in the construction of the statistically optimal test is astructural property for sparse matrices, which can be of independent interest.

Statistical and Computational Limits for Sparse Matrix Detection