Spectral Phase Transition and Optimal PCA in Block-Structured Spiked models

• URL: http://arxiv.org/abs/2403.03695v1
• Date: Wed, 6 Mar 2024 13:23:55 GMT
• Title: Spectral Phase Transition and Optimal PCA in Block-Structured Spiked models
• Authors: Pierre Mergny, Justin Ko, Florent Krzakala
• Abstract summary: We discuss the inhomogeneous spiked Wigner model, a theoretical framework recently introduced to study structured noise in various learning scenarios. Our primary objective is to find an optimal spectral method and to extend the celebrated citeBBP (BBP) phase transition criterion to our inhomogeneous, block-structured, Wigner model.
• Score: 20.742571160909456
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We discuss the inhomogeneous spiked Wigner model, a theoretical framework recently introduced to study structured noise in various learning scenarios, through the prism of random matrix theory, with a specific focus on its spectral properties. Our primary objective is to find an optimal spectral method and to extend the celebrated \cite{BBP} (BBP) phase transition criterion -- well-known in the homogeneous case -- to our inhomogeneous, block-structured, Wigner model. We provide a thorough rigorous analysis of a transformed matrix and show that the transition for the appearance of 1) an outlier outside the bulk of the limiting spectral distribution and 2) a positive overlap between the associated eigenvector and the signal, occurs precisely at the optimal threshold, making the proposed spectral method optimal within the class of iterative methods for the inhomogeneous Wigner problem.

Related papers

• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  We present a unified approach for the theoretical analysis of first-order variation methods. Our approach covers both non-linear gradient and strongly Monte Carlo problems. We provide bounds that match the oracle strongly in the case of convex method optimization problems.
  arXiv  Detail & Related papers  (2023-05-25T11:11:31Z)
• Precise Asymptotics for Spectral Methods in Mixed Generalized Linear Models [31.58736590532443]
  We consider the problem of estimating two statistically independent signals in a mixed generalized linear model. Our characterization exploits a mix of tools from random matrices, free probability and the theory of approximate message passing algorithms.
  arXiv  Detail & Related papers  (2022-11-21T11:35:25Z)
• Spectral Decomposition Representation for Reinforcement Learning [100.0424588013549]
  We propose an alternative spectral method, Spectral Decomposition Representation (SPEDER), that extracts a state-action abstraction from the dynamics without inducing spurious dependence on the data collection policy. A theoretical analysis establishes the sample efficiency of the proposed algorithm in both the online and offline settings. An experimental investigation demonstrates superior performance over current state-of-the-art algorithms across several benchmarks.
  arXiv  Detail & Related papers  (2022-08-19T19:01:30Z)
• Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering [7.342677574855651]
  The singular subspaces perturbation theory is of fundamental importance in probability and statistics. We consider two arbitrary matrices where one is a leave-one-column-out submatrix of the other one. It is well-suited for mixture models and results in a sharper and finer statistical analysis than classical perturbation bounds such as Wedin's Theorem.
  arXiv  Detail & Related papers  (2022-05-30T05:07:09Z)
• Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
  We propose a spectral algorithm that achieves perfect clustering with high probability on a class of large, sparse networks. Our method is the first to offer a guarantee of consistent latent structure recovery using spectral clustering.
  arXiv  Detail & Related papers  (2022-05-17T01:41:06Z)
• Robust, Nonparametric, Efficient Decomposition of Spectral Peaks under Distortion and Interference [0.0]
  We propose a decomposition method for the spectral peaks in an observed frequency spectrum, which is efficiently acquired by utilizing the Fast Fourier Transform. We model the peaks in spectrum as pseudo-symmetric functions, where the only constraint is a nonincreasing behavior around a central frequency when the distance increases. Our approach is more robust against arbitrary distortion, interference and noise on the spectrum that may be caused by an observation system.
  arXiv  Detail & Related papers  (2022-04-18T17:08:37Z)
• Spectral learning of multivariate extremes [0.0]
  We propose a spectral clustering algorithm for analyzing the dependence structure of multivariate extremes. Our work studies the theoretical performance of spectral clustering based on a random $k-nearest neighbor graph constructed from an extremal sample. We propose a simple consistent estimation strategy for learning the angular measure.
  arXiv  Detail & Related papers  (2021-11-15T14:33:06Z)
• Simulation of absorption spectra of molecular aggregates: a Hierarchy of Stochastic Pure States approach [68.8204255655161]
  hierarchy of pure states (HOPS) provides a formally exact solution based on local, trajectories. Exploiting the localization of HOPS for the simulation of absorption spectra in large aggregares requires a formulation in terms of normalized trajectories.
  arXiv  Detail & Related papers  (2021-11-01T16:59:54Z)
• One-dimensional Active Contour Models for Raman Spectrum Baseline Correction [0.0]
  Raman spectroscopy is a powerful and non-invasive method for analysis of chemicals and detection of unknown substances. Background noise can distort the actual Raman signal. A modified version of active contour models in one-dimensional space has been proposed for the baseline correction of Raman spectra.
  arXiv  Detail & Related papers  (2021-04-26T19:30:34Z)
• Multi-View Spectral Clustering Tailored Tensor Low-Rank Representation [105.33409035876691]
  This paper explores the problem of multi-view spectral clustering (MVSC) based on tensor low-rank modeling. We design a novel structured tensor low-rank norm tailored to MVSC. We show that the proposed method outperforms state-of-the-art methods to a significant extent.
  arXiv  Detail & Related papers  (2020-04-30T11:52:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.