Optimal Algorithms for the Inhomogeneous Spiked Wigner Model
- URL: http://arxiv.org/abs/2302.06665v1
- Date: Mon, 13 Feb 2023 19:57:17 GMT
- Title: Optimal Algorithms for the Inhomogeneous Spiked Wigner Model
- Authors: Aleksandr Pak, Justin Ko, Florent Krzakala
- Abstract summary: We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem.
We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
- Score: 89.1371983413931
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study a spiked Wigner problem with an inhomogeneous noise
profile. Our aim in this problem is to recover the signal passed through an
inhomogeneous low-rank matrix channel. While the information-theoretic
performances are well-known, we focus on the algorithmic problem. We derive an
approximate message-passing algorithm (AMP) for the inhomogeneous problem and
show that its rigorous state evolution coincides with the information-theoretic
optimal Bayes fixed-point equations. We identify in particular the existence of
a statistical-to-computational gap where known algorithms require a
signal-to-noise ratio bigger than the information-theoretic threshold to
perform better than random. Finally, from the adapted AMP iteration we deduce a
simple and efficient spectral method that can be used to recover the transition
for matrices with general variance profiles. This spectral method matches the
conjectured optimal computational phase transition.
Related papers
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal.
Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
arXiv Detail & Related papers (2024-09-07T06:37:23Z) - Poisson-Gaussian Holographic Phase Retrieval with Score-based Image
Prior [19.231581775644617]
We propose a new algorithm called "AWFS" that uses the accelerated Wirtinger flow (AWF) with a score function as generative prior.
We calculate the gradient of the log-likelihood function for PR and determine the Lipschitz constant.
We provide theoretical analysis that establishes a critical-point convergence guarantee for the proposed algorithm.
arXiv Detail & Related papers (2023-05-12T18:08:47Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications.
This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
arXiv Detail & Related papers (2023-01-30T15:46:39Z) - Learning Sparse Graphs via Majorization-Minimization for Smooth Node
Signals [8.140698535149042]
We propose an algorithm for learning a sparse weighted graph by estimating its adjacency matrix.
We show that the proposed algorithm converges faster, in terms of the average number of iterations, than several existing methods in the literature.
arXiv Detail & Related papers (2022-02-06T17:06:13Z) - Fully Adaptive Bayesian Algorithm for Data Analysis, FABADA [0.0]
This paper describes a novel non-parametric noise reduction technique from the point of view of Bayesian inference.
It iteratively evaluates possible smoothed versions of the data, the smooth models, obtaining an estimation of the underlying signal.
Iterations stop based on the evidence and the $chi2$ statistic of the last smooth model, and we compute the expected value of the signal.
arXiv Detail & Related papers (2022-01-13T18:54:31Z) - Matrix completion based on Gaussian belief propagation [5.685589351789462]
We develop a message-passing algorithm for noisy matrix completion problems based on matrix factorization.
We derive a memory-friendly version of the proposed algorithm by applying a perturbation treatment commonly used in the literature of approximate message passing.
Experiments on synthetic datasets show that while the proposed algorithm quantitatively exhibits almost the same performance under settings where the earlier algorithm is optimal, it is advantageous when the observed datasets are corrupted by non-Gaussian noise.
arXiv Detail & Related papers (2021-05-01T12:16:49Z) - Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
We propose a plug-and-play compressed sensing (CS) recovery algorithm suitable for any i.i.d. source prior.
Our algorithm builds upon Borgerding's learned AMP (LAMP), yet significantly improves it by adopting a universal denoising function within the algorithm.
Numerical evaluation shows that the L-GM-AMP algorithm achieves state-of-the-art performance without any knowledge of the source prior.
arXiv Detail & Related papers (2020-11-18T16:40:45Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning.
Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms.
We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
arXiv Detail & Related papers (2020-07-01T18:43:32Z) - Sparse recovery by reduced variance stochastic approximation [5.672132510411465]
We discuss application of iterative quadratic optimization routines to the problem of sparse signal recovery from noisy observation.
We show how one can straightforwardly enhance reliability of the corresponding solution by using Median-of-Means like techniques.
arXiv Detail & Related papers (2020-06-11T12:31:20Z) - Active Model Estimation in Markov Decision Processes [108.46146218973189]
We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP)
We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
arXiv Detail & Related papers (2020-03-06T16:17:24Z)
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.