80 problems

Bayes-GVAMP's polynomial-time optimality conjecture
arXiv@arxiv
Consider a generic orthogonally invariant generalized linear model and the spectrally initialized Bayes-GVAMP estimator. Bayes-GVAMP optimality conjecture. Bayes-GVAMP is optimal a…
Conjectureopenapproximate-message-passing computational-statistics generalized-linear-models
1
Lipschitz-continuity conjecture for FEC-code denoisers in MAMP
arXiv@arxiv
In a memory approximate message passing (MAMP) receiver, let $\hat{\phi}_t(\cdot)$ denote the code constraint associated with the forward-error-correction (FEC) decoder at iteratio…
Conjectureopenapproximate-message-passing coding-theory state-evolution
0
State-evolution prediction for AMP with Toeplitz matrices
arXiv@arxiv
Consider the given BDD signal model and compare AMP and AMP-SI using Toeplitz sensing matrices with the corresponding state-evolution prediction, as well as using independent and i…
Conjectureopenapproximate-message-passing state-evolution structured-matrices
0
Hard-phase conjecture for generalized linear models
arXiv@arxiv
Hard-phase conjecture. There is no efficient algorithm that achieves better performance than GAMP in the hard phase.
Conjectureopenapproximate-message-passing computational-complexity generalized-linear-models
0
AMP optimality conjecture for average-case sparse optimization
arXiv@arxiv
AMP optimality conjecture. AMP algorithms are optimal for average-case sparse optimization problems.
Conjectureopenapproximate-message-passing quantum-algorithms sparse-optimization
0
MF-AOA asymptotic performance conjecture for the binary paint shop problem
arXiv@arxiv
MF-AOA asymptotic performance conjecture. In the limit $n\rightarrow\infty$ , AMP algorithms such as the MF-AOA achieve a performance of approximately
Conjectureopenapproximate-message-passing combinatorial-optimization quantum-algorithms
0
The general AMP equilibrium empirical-measure conjecture for non-structured interaction matrices
arXiv@arxiv
General AMP equilibrium conjecture. The empirical distribution of the equilibrium $u^\star$ converges to $\mu_n$ in Wasserstein distance:
Conjectureopenapproximate-message-passing ecological-systems random-matrices
1
Maillard et al.'s replica prediction for Bayes risk
arXiv@arxiv
Consider the generalized linear model with orthogonally invariant design, and let $\widehat{\beta}_{\mathrm{B}}=\mathbb{E}[\beta_*\mid X,y]$ be the posterior mean estimator. Let…
Conjectureopenapproximate-message-passing generalized-linear-models replica-methods
0
Optimality conjecture for orthogonal approximate message passing
arXiv@arxiv
Consider rectangular spiked matrix models with general rotationally invariant noise, and let the optimal orthogonal approximate message passing (OAMP) algorithm be the variant that…
Conjectureopenapproximate-message-passing random-matrix-theory statistical-inference
0
Universality-class extension conjecture for OAMP/VAMP
arXiv@arxiv
Let $\mathscr{U}$ be the universality class used in the paper, let $\mathscr{Q}$ be a matrix class, let OAMP/VAMP denote the stated algorithms, and let SE denote their state evolut…
Conjectureopenapproximate-message-passing random-matrices universality
0
Replica MMSE conjecture for right unitarily invariant matrices
arXiv@arxiv
Let $\bm{A}$ be a right unitarily-invariant matrix, and suppose that the fixed point $v^*$ of the replica MMSE equation is unique. Let the replica MMSE be the MMSE predicted by the…
Conjectureopenapproximate-message-passing information-theory random-matrices
0
Statistical optimality of optimal OAMP for rectangular spiked matrix models
arXiv@arxiv
OAMP optimality conjecture. The predicted performance of the proposed optimal OAMP algorithm agrees with the replica-symmetric predictions for the associated Bayes-optimal estimato…
Conjectureopenapproximate-message-passing random-matrix-theory spiked-matrix-models
0
Near-linear-time weak recovery by Glauber dynamics
arXiv@arxiv
In the spiked Wigner inference problem, let annealed Glauber dynamics refer to the Markov chain studied in the paper, and let weak recovery mean achieving nonzero correlation with…
Conjectureopenapproximate-message-passing markov-chains spiked-wigner-model
1
AMP fidelity-bias conjecture for Hadamard and GHZ states
arXiv@arxiv
Consider AMP reconstruction applied to quantum state tomography experiments for Hadamard and GHZ states, with state preparation fidelity denoted by…
Conjectureopenapproximate-message-passing quantum-noise quantum-state-tomography
1
AMP optimality conjecture for quantum state tomography
arXiv@arxiv
Let $d=2^n$ be the Hilbert-space dimension for an $n$ -qubit system, and consider quantum state tomography in the high-dimensional regime where the ratio of the number of measuremen…
Conjectureopenapproximate-message-passing computational-statistics quantum-state-tomography
1
The computational hardness conjecture for inhomogeneous low-rank estimation below the AMP threshold
arXiv@arxiv
In the block-structured spiked model, let $\beta_*$ denote the threshold governing the performance of spectral and approximate message passing algorithms, and let $\beta$ be the si…
Conjectureopenapproximate-message-passing computational-complexity low-rank-estimation
0
Asymptotic equivalence of TAP and true free energies
arXiv@arxiv
Assume a uniform prior on $S_{p-1}(\sqrt{p})$ and define the TAP function for $a$ with $\|a\|^2=pq$ by … Let $F_{TAP}=\sup_{\|a\|^2\leq p}f_{\mathrm{TAP}}(a)$ , and let the true fre…
Conjectureopenapproximate-message-passing bayesian-linear-regression tap-free-energy
1
AMP optimality conjecture for high-dimensional estimation
arXiv@arxiv
AMP optimality conjecture. For a wide class of estimation problems, AMP is conjectured to be optimal among all polynomial-time algorithms.
Conjectureopenapproximate-message-passing computational-statistics high-dimensional-statistics
0
Hou et al.'s capacity-achieving conjecture for VAMP decoding of sparse superposition codes
arXiv@arxiv
Let SS denote sparse superposition coding with right orthogonally invariant design matrices, and suppose that the design matrices satisfy the spectra criterion. Hou et al.'s conjec…
Conjectureopenapproximate-message-passing information-theory sparse-superposition-codes
1
Replica-symmetric prediction for the regressor MMSE in high-dimensional time series
arXiv@arxiv
Let $\boldsymbol{\beta}$ be the regressor, let $\mathbf{Y}_N$ and $\boldsymbol{\Phi}_N$ denote the observations and design matrix, and suppose the discrete eigenvalues profile has…
Conjectureopenapproximate-message-passing high-dimensional-statistics information-theory
0
Universality conjecture for randomly signed Fourier dictionaries
arXiv@arxiv
Universality conjecture for randomly signed Fourier dictionaries. The theoretical results developed for the dictionary model in the paper continue to hold, perhaps under a weaker h…
Conjectureopenapproximate-message-passing random-matrices universality
0
The efficient-sampling threshold as the AMP estimation-failure variance
arXiv@arxiv
Consider a Bayesian inference problem with a noise variance parameter, and let AMP be used for estimation. Define the asymptotically Bayes-optimal estimation regime as the set of v…
Conjectureopenapproximate-message-passing posterior-sampling statistical-physics
0
The AMP characterization of the algorithmic hard phase
arXiv@arxiv
Consider a high-dimensional Bayesian inference problem for which approximate message passing (AMP) has a state evolution and a Bayes-optimal solution given by the posterior mean es…
Conjectureopenapproximate-message-passing bayesian-inference
0
Montanari's sampling-hardness threshold conjecture for the spiked model
arXiv@arxiv
Let $\boldsymbol{X}=n^{-1}\beta\boldsymbol{\theta}\boldsymbol{\theta}^\top+\boldsymbol{W}$ be a spiked model, where $\beta$ is the signal strength and $\boldsymbol{\theta}$ is the…
Conjectureopenapproximate-message-passing posterior-sampling spiked-models
0
The AMP algorithmic threshold conjecture for weak signal recovery
arXiv@arxiv
AMP algorithmic threshold conjecture. Approximate Message Passing algorithms of the form developed in PWBM2018 are expected to achieve weak signal recovery from a random initializa…
Conjectureopenapproximate-message-passing computational-statistics group-synchronization
0