Rigorous Dynamics and Consistent Estimation in Arbitrarily Conditioned Linear Systems
We consider the problem of estimating a random vector x from noisy linear measurements y = Ax + w in the setting where parameters θ on the distribution of x and w must be learned in addition to the vector x. This problem arises in a wide range of statistical learning and linear inverse problems. Our main contribution shows that a computationally simple iterative message passing algorithm can provably obtain asymptotically consistent estimates in a certain high-dimensional large system limit (LSL) under very general parametrizations. Importantly, this LSL applies to all right-rotationally random A -a much larger class of matrices than i.i.d. sub-Gaussian matrices to which many past message passing approaches are restricted. In addition, a simple testable condition is provided in which the mean square error (MSE) on the vector x matches the Bayes optimal MSE predicted by the replica method. The proposed algorithm uses a combination of Expectation-Maximization (EM) with a recently-developed Vector Approximate Message Passing (VAMP) technique. We develop an analysis framework that shows that the parameter estimates in each iteration of the algorithm converge to deterministic limits that can be precisely predicted by a simple set of state evolution (SE) equations. The SE equations, which extends those of VAMP without parameter adaptation, depend only on the initial parameter estimates and the statistical properties of the problem and can be used to predict consistency and precisely characterize other performance measures of the method.
The model is p(y | x, \theta_1) p(x | \theta_1) where y | x is a linear system y = A*x + Gaussian noise. We want to infer x and \theta from data. Importantly, p(x | \theta_1) factorizes over elements of x.
The paper takes EM-VAMP from [13], and changes a step for updating \theta_1 (from the EM-VAMP algorithm). As a general comment, I was wondering why the algorithm wasn't called "generalized EM-VAMP" -- if eq (7) is used as "adaptation" (which is preferred according to line 113), then there is no difference and the naming is rather confusing. What is adapted that is *not* adapted in EM-VAMP? Naming and nomenclature aside, and also ignoring that much of the introduction of the paper is a verbatim copy of [13], the paper makes some fundamental contributions:
It provides an asymptotic analysis to EM-VAMP, showing that as the number of latent dimensions in x goes to infinity, the algorithm converges.
Secondly, we can compute the deterministic limit from a set of state evolution equations. The paper's numerical results show that the state evolution equations in eq (24) in the paper predicts the performance (mean squared error of true x vs estimated x^) of EM-VAMP remarkably well per iteration.
The paper then asks, given that the algorithm converges, does it converge to an asymptotically consistent estimate of \theta? If p(x|\theta_1) is identifiable in Gaussian noise, then we can find statistics (essentially, here the "adaptation rule" that generalizes EM-VAMP seems to really come into play) so that convergence of the estimate is a.s. to \theta.
In my humble opinion, the paper provides nice and rigorous analysis to give EM-VAMP a deeper theoretic base.
Postscripts
-----------
Very similar to [a] and [b], the algorithm factorizes the joint into a Gaussian and a non-Gaussian part, and approximates the non-Gaussian part with a contribution (messages) towards the Gaussian part to give a Gaussian belief on x.
[a] Matthias Seeger & Hannes Nickisch, Fast Convergent Algorithms for Expectation Propagation Approximate Bayesian Inference.
[b] Matthias Seeger, Bayesian Inference and Optimal Design for the Sparse Linear Model, JMLR
Could the authors put Figure 1 in a vectorized format? It is hard to read, especially when printed.
small typo, :== in line 508