The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing

DOI10.1109/TIT.2010.2094817zbMath1366.94079arXiv1001.3448OpenAlexW3098848552MaRDI QIDQ5281076

Mohsen Bayati, Andrea Montanari

Publication date: 27 July 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Applications of graph theory (05C90) Random matrices (probabilistic aspects) (60B20) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Related Items

Fundamental barriers to high-dimensional regression with convex penalties, Approximate message passing algorithms for rotationally invariant matrices, Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information, Approximate message passing with spectral initialization for generalized linear models*, Disordered systems insights on computational hardness, Analysis of Bayesian inference algorithms by the dynamical functional approach, On the universality of noiseless linear estimation with respect to the measurement matrix, Computational barriers to estimation from low-degree polynomials, Recovering Structured Signals in Noise: Least-Squares Meets Compressed Sensing, Sharp MSE bounds for proximal denoising, High dimensional robust M-estimation: asymptotic variance via approximate message passing, Estimation of low-rank matrices via approximate message passing, Statistical limits of spiked tensor models, Bayesian Imaging Using Plug & Play Priors: When Langevin Meets Tweedie, An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model, Fast and Reliable Parameter Estimation from Nonlinear Observations, Algorithmic pure states for the negative spherical perceptron, Analysis of random sequential message passing algorithms for approximate inference, Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising, Characterizing the SLOPE trade-off: a variational perspective and the Donoho-Tanner limit, Automatic bias correction for testing in high‐dimensional linear models, Fundamental limits of weak recovery with applications to phase retrieval, Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree, Detangling robustness in high dimensions: composite versus model-averaged estimation, Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time, Approximate message passing for sparse matrices with application to the equilibria of large ecological Lotka-Volterra systems, Optimization algorithms for multi-species spherical spin glasses, Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022, A power analysis for Model-X knockoffs with \(\ell_p\)-regularized statistics, Algorithmic obstructions in the random number partitioning problem, Universality of approximate message passing with semirandom matrices, A Message-Passing Approach to Phase Retrieval of Sparse Signals, Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization, Noisy linear inverse problems under convex constraints: exact risk asymptotics in high dimensions, Learning low-dimensional nonlinear structures from high-dimensional noisy data: an integral operator approach, Universality of regularized regression estimators in high dimensions, Optimizing mean field spin glasses with external field, A tradeoff between false discovery and true positive proportions for sparse high-dimensional logistic regression, On the TAP equations via the cavity approach in the generic mixed \(p\)-spin models, Asymptotic mutual information for the balanced binary stochastic block model, Data assimilation -- mathematical foundation and applications. Abstracts from the workshop held February 20--26, 2022, The existence of maximum likelihood estimate in high-dimensional binary response generalized linear models, Unnamed Item, Which bridge estimator is the best for variable selection?, Asymptotic risk and phase transition of \(l_1\)-penalized robust estimator, Notes on computational-to-statistical gaps: predictions using statistical physics, TAP free energy, spin glasses and variational inference, The overlap gap property and approximate message passing algorithms for \(p\)-spin models, Compressive Computed Tomography Reconstruction through Denoising Approximate Message Passing, Statistical mechanics approach to 1-bit compressed sensing, Blind sensor calibration using approximate message passing, Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes, Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications, Optimization of the Sherrington--Kirkpatrick Hamiltonian, Perfect reconstruction of sparse signals with piecewise continuous nonconvex penalties and nonconvexity control, Phase transition in random tensors with multiple independent spikes, Unnamed Item, Debiasing the Lasso: optimal sample size for Gaussian designs, Overcoming the limitations of phase transition by higher order analysis of regularization techniques, Robust subspace clustering, Submatrix localization via message passing, Community Detection and Stochastic Block Models, Consistent parameter estimation for Lasso and approximate message passing, The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising, Unnamed Item, The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square, Optimality and sub-optimality of PCA. I: Spiked random matrix models, Universality of approximate message passing algorithms, Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis, The distribution of the Lasso: uniform control over sparse balls and adaptive parameter tuning, Unnamed Item, Critical behavior and universality classes for an algorithmic phase transition in sparse reconstruction, Optimization of mean-field spin glasses, Phase transition in the spiked random tensor with Rademacher prior, Optimal combination of linear and spectral estimators for generalized linear models, The scaling limit of high-dimensional online independent component analysis, Statistical mechanics of low-rank tensor decomposition, Plug in estimation in high dimensional linear inverse problems a rigorous analysis, The committee machine: computational to statistical gaps in learning a two-layers neural network, Approximate survey propagation for statistical inference, Semi-analytic approximate stability selection for correlated data in generalized linear models, A dynamical mean-field theory for learning in restricted Boltzmann machines, Generalized approximate survey propagation for high-dimensional estimation ^*, Regularization by Denoising via Fixed-Point Projection (RED-PRO), A Unifying Tutorial on Approximate Message Passing, Unbiasing in iterative reconstruction algorithms for discrete compressed sensing, LASSO risk and phase transition under dependence, Matrix inference and estimation in multi-layer models*, Statistical mechanics analysis of generalized multi-dimensional knapsack problems, Replica analysis of overfitting in generalized linear regression models, Optimal low-degree hardness of maximum independent set