PaperlayerView exact revision on arXiv

Source-linked AI summary

Bilinear Generalized Approximate Message Passing

Jason T. Parker, Philip Schniter, Volkan Cevher

arXiv:1310.2632v3cs.IT

TL;DR

The paper addresses generalized bilinear inference, estimating latent matrices whose product generates observations, for problems including matrix completion, robust PCA, and dictionary learning. It derives BiG-AMP as an approximate belief-propagation algorithm and adds damping, EM tuning, and rank selection. Across synthetic and realistic datasets, the method reports excellent reconstruction accuracy, often best in class, with competitive runtimes and reduced parameter tuning.

  • Problem

    The paper studies how to extend AMP from generalized linear regression to generalized bilinear inference for matrix-factorization problems.

  • Method

    BiG-AMP approximates sum-product belief propagation with central-limit-theorem and Taylor-series arguments, augmented by adaptive damping, EM parameter tuning, and rank-selection strategies.

  • Results

    Across matrix completion, robust PCA, and dictionary learning experiments, BiG-AMP achieved excellent reconstruction accuracy, often best in class, with competitive runtimes.

  • Takeaways & Limitations

    EM and rank-selection strategies can avoid tuning algorithmic parameters while preserving the method's reported reconstruction and runtime performance.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper formulates generalized bilinear inference for estimating two latent matrices from observations coupled to their product, extending AMP beyond generalized linear regression. It develops BiG-AMP through approximate belief propagation and introduces adaptations for practical applications and unknown model parameters.

  • The generalized bilinear problem estimates A and X from observations Y statistically coupled to Z = AX, assuming separable matrix priors and likelihoods.
  • Matrix completion, robust PCA, and dictionary learning are presented as important special cases of generalized bilinear inference.
  • AMP's large-system state evolution and low per-iteration complexity motivate testing whether AMP can extend successfully to generalized bilinear inference.
  • The framework adds adaptive damping, EM-based parameter tuning, and rank-selection methods, including Gaussian-mixture modeling when priors or likelihoods are unknown.
  • The paper compares application-specific BiG-AMP methods with state-of-the-art solvers on synthetic and real-world datasets, reporting excellent reconstruction and competitive runtimes.
  • The approach remains restricted to separable known probability models, although hidden coupling variables can relax separability and are not discussed because of space limitations.
  • BiG-AMP approximates sum-product belief propagation using central-limit-theorem and Taylor-series arguments for high-dimensional inference.

D. Approximated Factor-to-Variable Messages

Factor-to-variable messages are approximated by treating bilinear products as conditionally Gaussian, then simplifying their dependence through large-system scalings and Taylor expansions. The resulting approximation reduces message computation while retaining posterior information about Z.

  • CLT arguments treat each z_ml conditioned on x_nl as approximately Gaussian, characterized by a conditional mean and variance.This approximation applies in the large-system limit, with M, L, and N tending to infinity at fixed ratios.
  • The approximated factor-to-variable message requires a single integration rather than the original sum-product message's full integration structure.The simplification follows after replacing the conditional distribution with the Gaussian approximation.
  • Taylor-series expansions and scaling arguments discard terms that vanish relative to dominant terms as N grows.Terms of order O(1/N^3/2) and related higher-order contributions are neglected in the large-system limit.
  • The resulting posterior approximation for z_ml is interpreted as the iteration-t marginal posterior used by BiG-AMP.It can also be viewed as an exact posterior under an implicitly assumed Gaussian prior for z_ml.

E. Approximated Variable-to-Factor Messages

Variable-to-factor messages are simplified by Taylor expansions and established large-system scalings, producing destination-independent approximations for messages associated with X and A.

  • Variable-to-factor messages are approximated by inserting the Gaussian factor-message approximation and expanding around current estimates.The derivation repeats the same CLT and Taylor-series strategy for both matrix factors.
  • Differences between destination-specific and invariant messages are treated as small perturbations under the assumed O(1/N) scalings.These scalings justify replacing destination-dependent quantities with common approximations.
  • The resulting approximations support updates for the posterior means and variances of x_nl and a_mn.Analogous derivations are used for the two classes of unknown matrix entries.

F. Closing the Loop

The derivation closes the loop by replacing destination-specific estimates with invariant quantities and retaining only terms that remain significant in the large-system limit.

  • Substituting the invariant approximations into earlier expressions removes destination dependence from the remaining message updates.The substitutions use approximations for both X- and A-related quantities.
  • Terms of order O(1/N) and O(1/N^3/2) are neglected when they vanish relative to O(1) contributions.The stated approximation errors determine which terms are retained in the closed-loop updates.
  • The resulting expressions complete the approximation of the remaining sum-product updates needed for BiG-AMP.These substitutions precede the separate posterior-log-pdf approximation.

G. Approximated Posteriors

BiG-AMP approximates the posterior distributions of X and A using Gaussian effective observations, while the summarized implementation supports damping, stopping criteria, and lower-complexity variants.

  • G. Approximated Posteriors: The final derivation approximates the marginal posteriors p_xnl|Y and p_amn|Y through iteration-dependent posterior densities.The associated means and variances are obtained from these approximated posterior pdfs.
  • G. Approximated Posteriors: BiG-AMP interprets the updates for x_nl and a_mn as Bayesian posterior calculations from effective observations and assumed likelihoods.The same interpretation is given for both unknown matrix factors.
  • G. Approximated Posteriors: Table III summarizes the algorithm with a maximum iteration count and a residual-change stopping condition.The table also permits complex-valued quantities, including the corresponding complex conjugates and circular complex Gaussian noise model.
  • G. Approximated Posteriors: BiG-AMP avoids SVD and QR decompositions, but its baseline complexity is dominated by ten matrix multiplications per iteration.Each multiplication requires MNL multiplications, while scalar-variance simplifications can reduce the total to three matrix multiplications per iteration.

B. Possibly Incomplete AWGN Observations

The PIAWGN model handles noisy observations on a subset of entries and missingness elsewhere, enabling simplified BiG-AMP computations that exploit incomplete data.

  • PIAWGN applies AWGN corruption at observed indices and treats unobserved entries as missing, with the standard AWGN model as the fully observed special case.
  • At missing entries, the observation is non-informative, so the corresponding posterior update contributes zero residual information.
  • Under scalar-variance approximations, the PIAWGN specialization reduces each of three partial matrix multiplies to N|Ω| scalar multiplies.
  • The projection operator PΩ restricts residual processing to observed entries, avoiding storage of residual matrices at missing locations.
  • BiG-AMP-Lite therefore costs (3N + 5)|Ω| + 3(MN + NL) + 29 multiplies per iteration.

IV. ADAPTIVE DAMPING

Adaptive damping addresses divergence risks caused by finite dimensions by slowing selected BiG-AMP variables and adapting updates according to an approximate cost criterion.

  • Large-system approximations may fail at finite dimensions, where BiG-AMP can diverge; damping is introduced to improve practical convergence.
  • The damping factor β(t) slows selected variables, with β(t)=1 leaving updates unchanged and β(t)=0 freezing them.
  • Adaptive damping reduces β(t) when a monitored cost criterion fails to decrease over a recent step window.
  • The cost is approximated by replacing AX with an independent Gaussian matrix whose component means and variances match those of AX.
  • The approximate cost penalizes deviations from the priors on X and A while rewarding estimates Z that are likely under the observation model.

V. PARAMETER TUNING AND RANK SELECTION

The paper extends BiG-AMP with EM-based parameter learning and two data-driven rank-selection procedures, while identifying assumptions and scope boundaries for these mechanisms.

  • V. PARAMETER TUNING AND RANK SELECTION: EM-BiG-AMP tunes unknown prior and likelihood parameters by maximizing the data likelihood using approximate marginal posteriors from BiG-AMP.
  • V. PARAMETER TUNING AND RANK SELECTION: The EM recursion treats X, A, and Z as hidden variables and updates parameters incrementally, one element at a time.
  • V. PARAMETER TUNING AND RANK SELECTION: BiG-AMP requires the rank N, so the paper proposes estimating it from candidate models using penalized likelihood criteria such as AIC or BIC.
  • V. PARAMETER TUNING AND RANK SELECTION: Rank contraction identifies the largest successive singular-value gap and accepts it only when the ratio exceeds a user-specified threshold.
  • V. PARAMETER TUNING AND RANK SELECTION: Rank contraction can require only one convergence run, but it may misestimate rank when singular values decay smoothly.
  • V. PARAMETER TUNING AND RANK SELECTION: The application studies report excellent reconstruction performance, often best in class, with competitive runtimes across matrix completion, robust PCA, and dictionary learning.

A. Problem setup

For matrix completion, BiG-AMP factorizes the unknown low-rank matrix, models incomplete noisy observations with PIAWGN, and estimates missing entries through the inferred factors.

  • A. Problem setup: Matrix completion seeks a rank-N matrix from a subset of possibly noise-corrupted entries.
  • A. Problem setup: BiG-AMP represents the complete matrix as Z=AX and infers A and X from observations under separable priors and likelihoods.
  • A. Problem setup: The estimated factors are multiplied to produce an estimate of the noiseless complete matrix, bZ=bA bX.
  • A. Problem setup: The matrix-completion specialization uses Gaussian iid priors for A and X, with one factor variance fixed to avoid scaling ambiguity.
  • A. Problem setup: PIAWGN supplies the observation likelihood, while scalar-variance assumptions reduce the method to the simpler BiG-AMP-Lite algorithm.
  • A. Problem setup: BiG-AMP’s matrix-completion configuration includes EM tuning, rank-selection recommendations, initialization procedures, and comparisons with state-of-the-art solvers.

1) Low-rank matrices:

Across synthetic and real-world low-rank completion tasks, EM-BiG-AMP achieved strong reconstruction accuracy, often outperforming competitors, while BiG-AMP variants offered competitive runtimes.

  • Noiseless completion: BiG-AMP exhibited the best phase-transition curves, approaching the feasibility boundary across tested sampling ratios and ranks.BiG-AMP-Lite ranked second and matched BiG-AMP except below δ < 0.03.
  • Runtime: BiG-AMP-Lite was generally the second-fastest algorithm, while EM-BiG-AMP was about 3 to 5 times slower than BiG-AMP-Lite but faster than IALM and VSBL at high ranks.LMaFit was usually fastest, although BiG-AMP-Lite was faster at small δ and relatively large N.
  • Unknown-rank completion: In unknown-rank noiseless completion, BiG-AMP and LMaFit had similar NMSE, while BiG-AMP tended to estimate lower ranks at low sampling ratios.VSBL consistently underestimated rank and consequently had inferior NMSE.
  • Noisy completion: In noisy completion, EM-BiG-AMP was the only method among the tested algorithms to avoid the rank-estimation failures exhibited by LMaFit and VSBL across SNR regimes.Below 50 dB it matched VSBL, while above 50 dB it matched LMaFit.
  • Image completion: EM-BiG-AMP produced the best image-completion NMSE, within 3 dB of the NMSE-optimal rank-40 approximation.The comparison used fixed rank N = 40 and median reconstruction NMSE over 10 sampling-index realizations.
  • Collaborative filtering: In collaborative filtering, EM-BiG-AMP with the PIAWLN likelihood matched VSBL and improved on LMaFit at very low training fractions.Under PIAWGN, its NMAE was close to VSBL’s but slightly inferior at larger training fractions.

VII. ROBUST PCA

For robust PCA, the paper models observations as a low-rank component plus sparse outliers and dense noise, then applies BiG-AMP through alternative likelihood or augmented-factor constructions.

  • Problem formulation: RPCA seeks to estimate a low-rank matrix observed with dense noise and large sparse outliers.The model represents the observation as a low-rank product together with outlier and noise matrices.
  • Likelihood-based approach: The first BiG-AMP approach treats the combined outlier and dense-noise terms as additive noise through a two-component Gaussian-mixture likelihood.The mixture weight λ models outlier density, with the outlier component having larger variance.
  • Augmented approach: The second approach treats dense noise as additive while estimating sparse outliers separately in an augmented bilinear model.A known unitary matrix Q is used to rewrite the RPCA model before applying BiG-AMP.
  • Priors and representation: The augmented construction assigns Gaussian priors to low-rank factors, Bernoulli-Gaussian priors to outliers, and zero-variance priors to the designed matrix components.The first N columns of A and first N rows of X represent the low-rank factors, while additional components encode outliers and Q.
  • Parameter learning: EM can tune the remaining RPCA distributional parameters after fixing ν_a0 = 1.The suggested initialization uses medians to reduce the influence of outliers and λ = 0.1 was found effective for most problems.

D. Rank Selection

EM-BiG-AMP estimates unknown rank effectively in RPCA, while BiG-AMP achieves strong phase-transition performance and competitive runtimes against existing methods.

  • Phase Transition Behavior: BiG-AMP-1 and BiG-AMP-2 achieve similar, substantially better RPCA phase-transition curves than the compared algorithms.EM-BiG-AMP-2 and BiG-AMP-2 have nearly identical phase transitions, indicating successful EM learning of the statistical model parameters.
  • Phase Transition Behavior: RPCA phase transitions remain far from the feasibility boundary because outlier locations are unknown and corrupted observations cannot simply be treated as missing.
  • Runtime: BiG-AMP runtimes are competitive: faster than GRASTA and grid-tuned IALM-2, but slower than IALM-1, VSBL, and LMaFit.LMaFit is both fastest and strongest among non-BiG-AMP methods on this synthetic test problem.
  • Rank Estimation: EM-BiG-AMP-2 and LMaFit accurately estimate the rank across true ranks N ∈ [5, 90], whereas VSBL succeeds only for N ≤20 and IALM overestimates rank.
  • Rank Estimation: For true ranks N ≤80, EM-BiG-AMP-2 and LMaFit accurately estimate the low-rank component, with EM-BiG-AMP-2 outperforming LMaFit by several dB.
  • Video Surveillance: In a mall video sequence, rank contraction reduced the estimated background rank to 1 after the first EM iteration, producing background and foreground estimates.

B. Initialization

The dictionary-learning experiments show that EM-BiG-AMP combines near-state-of-the-art noiseless recovery with graceful noise behavior, broad dictionary applicability, and competitive runtime.

  • Initialization: The dictionary-learning study uses sparse training samples, multiple random initializations, and initialization selection based on residual error and average sparsity.
  • Runtime: Within an order-of-magnitude of SPAMS and more than two orders-of-magnitude faster than ER-SpUD(proj) for larger dictionaries, EM-BiG-AMP remains competitive in runtime.
  • Noisy Recovery: At 40 dB SNR, K-SVD, SPAMS, and EM-BiG-AMP degrade gracefully, yielding NMSE ≈ −50 dB below the noiseless phase-transition curves.ER-SpUD(proj) performs poorly in the noisy setting.
  • Overcomplete Dictionaries: For twice-overcomplete dictionaries with N = 2M, EM-BiG-AMP, K-SVD, and SPAMS show results similar to the square-dictionary case.ER-SpUD(proj) was not tested because it applies only to square dictionaries.
  • Square Dictionaries: EM-BiG-AMP’s noiseless square-dictionary phase-transition curve is nearly as good as ER-SpUD(proj)’s and much better than K-SVD’s and SPAMS’s.K-SVD and SPAMS were given oracle information, whereas EM-BiG-AMP was not provided with equivalent knowledge.
  • Overall Findings: Across matrix completion, robust PCA, and dictionary learning, BiG-AMP reports excellent reconstruction accuracy, competitive runtimes, and reduced algorithmic-parameter tuning.

APPENDIX A

Appendix A derives key GAMP-related identities and justifies BiG-AMP approximations using posterior definitions, calculus, and large-system behavior.

  • Derivation: Equations (31) and (32) follow by defining an exponential-family posterior, differentiating its normalization, and applying the stated moment definitions.
  • Approximation Justification: The approximation from (45) to (65) neglects a term argued to average approximately to zero in the large-system limit under iid priors and scalar variances.The same reasoning is stated to apply to the approximation in (66).
Loading 1310.2632v3…