Free Energy Wells and Overlap Gap Property in Sparse PCA

DOI10.1002/cpa.22083arXiv2006.10689OpenAlexW3036604581MaRDI QIDQ6074556

Ilias Zadik, Alexander S. Wein, Gérard Ben Arous

Publication date: 12 October 2023

Published in: Communications on Pure and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.10689

Mathematics Subject Classification ID

Computer science (68-XX) Statistical mechanics, structure of matter (82-XX)

Cites Work

• Unnamed Item
• Statistical and computational trade-offs in estimation of sparse principal components
• Optimal detection of sparse principal components in high dimension
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• Algorithmic thresholds for tensor PCA
• On the distribution of the largest eigenvalue in principal components analysis
• Local algorithms for independent sets are half-optimal
• The overlap gap property in principal submatrix recovery
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• Bounding flows for spherical spin glass dynamics
• Suboptimality of local algorithms for a class of max-cut problems
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Sparse PCA: optimal rates and adaptive estimation
• The largest eigenvalue of rank one deformation of large Wigner matrices
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Sparse PCA via Covariance Thresholding
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• Large Cliques Elude the Metropolis Process
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
• On Consistency and Sparsity for Principal Components Analysis in High Dimensions
• Walksat Stalls Well Below Satisfiability
• Limits of local algorithms over sparse random graphs
• On the solution‐space geometry of random constraint satisfaction problems
• The planted matching problem: sharp threshold and infinite-order phase transition

This page was built for publication: Free Energy Wells and Overlap Gap Property in Sparse PCA