Bilinear Generalized Approximate Message Passing

Abstract

We extend the generalized approximate message passing (G-AMP) approach, originally proposed for high-dimensional generalized-linear regression in the context of compressive sensing, to the generalized-bilinear case, which enables its application to matrix completion, robust PCA, dictionary learning, and related matrix-factorization problems. In the first part of the paper, we derive our Bilinear G-AMP (BiG-AMP) algorithm as an approximation of the sum-product belief propagation algorithm in the high-dimensional limit, where central-limit theorem arguments and Taylor-series approximations apply, and under the assumption of statistically independent matrix entries with known priors. In addition, we propose an adaptive damping mechanism that aids convergence under finite problem sizes, an expectation-maximization (EM)-based method to automatically tune the parameters of the assumed priors, and two rank-selection strategies. In the second part of the paper, we discuss the specializations of EM-BiG-AMP to the problems of matrix completion, robust PCA, and dictionary learning, and present the results of an extensive empirical study comparing EM-BiG-AMP to state-of-the-art algorithms on each problem. Our numerical results, using both synthetic and real-world datasets, demonstrate that EM-BiG-AMP yields excellent reconstruction accuracy (often best in class) while maintaining competitive runtimes and avoiding the need to tune algorithmic parameters.

References in corpus (10)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Message Passing Algorithms for Compressed Sensing
• The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Expectation-Maximization Gaussian-Mixture Approximate Message Passing
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Exact Recovery of Sparsely-Used Dictionaries
• Online Robust Subspace Tracking from Partial Information
• Phase Diagram and Approximate Message Passing for Blind Calibration and Dictionary Learning
• IMP: A Message-Passing Algorithmfor Matrix Completion

Cited by in corpus (70)

• Statistical physics of inference: Thresholds and algorithms
• Bayes-Optimal Joint Channel-and-Data Estimation for Massive MIMO with Low-Precision ADCs
• Matrix-Calibration-Based Cascaded Channel Estimation for Reconfigurable Intelligent Surface Assisted Multiuser MIMO
• A Survey of Intelligent Reflecting Surfaces (IRSs): Towards 6G Wireless Communication Networks
• Sparsity Learning Based Multiuser Detection in Grant-Free Massive-Device Multiple Access
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• Blind Estimation of Sparse Broadband Massive MIMO Channels with Ideal and One-bit ADCs
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Sparse Bayesian learning with uncertainty models and multiple dictionaries
• Bayesian User Localization and Tracking for Reconfigurable Intelligent Surface Aided MIMO Systems
• Hybrid Approximate Message Passing
• Fast Low-Rank Bayesian Matrix Completion with Hierarchical Gaussian Prior Models
• Parametric Bilinear Generalized Approximate Message Passing
• Joint Channel, Data, and Radar Parameter Estimation for AFDM Systems in Doubly-Dispersive Channels
• Finite Sample Analysis of Approximate Message Passing Algorithms
• A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality
• Environment Sensing Considering the Occlusion Effect: A Multi-View Approach
• Recovery of Low-Rank Matrices under Affine Constraints via a Smoothed Rank Function
• An Empirical-Bayes Approach to Recovering Linearly Constrained Non-Negative Sparse Signals
• Super-Resolution Blind Channel-and-Signal Estimation for Massive MIMO with One-Dimensional Antenna Array
• Cascaded Channel Estimation for Large Intelligent Metasurface Assisted Massive MIMO
• Bilinear Recovery using Adaptive Vector-AMP
• Multi-Layer Bilinear Generalized Approximate Message Passing
• Statistical limits of dictionary learning: random matrix theory and the spectral replica method
• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• Revisiting XL-MIMO Channel Estimation: When Dual-Wideband Effects Meet Near Field
• Joint Device Activity Detection, Channel Estimation and Signal Detection for Massive Grant-free Access via BiGAMP
• Channel Estimation in Broadband Millimeter Wave MIMO Systems with Few-Bit ADCs
• Interference-Cancellation-Based Channel Knowledge Map Construction and Its Applications to Channel Estimation
• Deep learning via message passing algorithms based on belief propagation
• Denoising-based Turbo Message Passing for Compressed Video Background Subtraction
• Passive Beamforming and Information Transfer via Large Intelligent Surface
• Near-optimal matrix recovery from random linear measurements
• Non-negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
• Phase diagram of matrix compressed sensing
• Semi-Blind Cascaded Channel Estimation for Reconfigurable Intelligent Surface Aided Massive MIMO
• Fixed Points of Generalized Approximate Message Passing with Arbitrary Matrices
• Multi-Processor Approximate Message Passing Using Lossy Compression
• On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel
• Simultaneous Active and Passive Information Transfer for RIS-Aided MIMO Systems: Iterative Decoding and Evolution Analysis
• Inference for Generalized Linear Models via Alternating Directions and Bethe Free Energy Minimization
• Bilinear Generalized Vector Approximate Message Passing
• Reconfigurable Intelligent Surface for Massive Connectivity
• Bayesian inference of infected patients in group testing with prevalence estimation
• Joint User Identification, Channel Estimation, and Signal Detection for Grant-Free NOMA
• Boolean Matrix Factorization and Noisy Completion via Message Passing
• Joint Channel-and-Data Estimation for Large-MIMO Systems with Low-Precision ADCs
• Joint Channel Estimation and Signal Recovery in RIS-Assisted Multi-User MISO Communications
• An Overview of Multi-Processor Approximate Message Passing
• Estimation for High-Dimensional Multi-Layer Generalized Linear Model -- Part I: The Exact MMSE Estimator
• Joint Activity Detection and Data Decoding in Massive Random Access via a Turbo Receiver
• Approximate matrix completion based on cavity method
• Blind Signal Detection in Massive MIMO: Exploiting the Channel Sparsity
• Grant-Free Access via Bilinear Inference for Cell-Free MIMO with Low-Coherent Pilots
• Message-Passing Receiver for Joint Channel Estimation and Decoding in 3D Massive MIMO-OFDM Systems
• Semi-Blind Channel-and-Signal Estimation for Uplink Massive MIMO With Channel Sparsity
• Optimizing Binary Symptom Checkers via Approximate Message Passing
• Pseudo-Bayesian Robust PCA: Algorithms and Analyses
• Covariance-domain Dictionary Learning for Overcomplete EEG Source Identification
• Double-Sparsity Learning Based Channel-and-Signal Estimation in Massive MIMO with Generalized Spatial Modulation
• A Bayesian Tensor Approach to Enable RIS for 6G Massive Unsourced Random Access
• Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolation
• Statistical mechanics of extensive-width Bayesian neural networks near interpolation
• Online Variational Bayesian Subspace Filtering with Applications
• Universality of Approximate Message Passing Algorithms
• Symbol Detection for Massive MIMO AF Relays Using Approximate Bayesian Inference
• An approximate message passing approach for compressive hyperspectral imaging using a simultaneous low-rank and joint-sparsity prior
• Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation
• Joint Transceiver Design Based on Dictionary Learning Algorithm for SCMA
• Sparse Kronecker-Product Coding for Unsourced Multiple Access