Title | ||
---|---|---|
Rigorous Dynamics and Consistent Estimation in Arbitrarily Conditioned Linear Systems. |
Abstract | ||
---|---|---|
The problem of estimating a random vector x from noisy linear measurements y=Ax+w with unknown parameters on the distributions of x and w, which must also be learned, arises in a wide range of statistical learning and linear inverse problems. We show 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 parameterizations. Previous message passing techniques have required i.i.d. sub-Gaussian A matrices and often fail when the matrix is ill-conditioned. The proposed algorithm, called adaptive vector approximate message passing (Adaptive VAMP) with auto-tuning, applies to all right-rotationally random A. Importantly, this class includes matrices with arbitrarily bad conditioning. We show that the parameter estimates and mean squared error (MSE) of x in each iteration converge to deterministic limits that can be precisely predicted by a simple set of state evolution (SE) equations. In addition, a simple testable condition is provided in which the MSE matches the Bayes-optimal value predicted by the replica method. The paper thus provides a computationally simple method with provable guarantees of optimality and consistency over a large class of linear inverse problems. |
Year | Venue | DocType |
---|---|---|
2017 | NIPS | Conference |
Volume | Citations | PageRank |
abs/1706.06054 | 2 | 0.40 |
References | Authors | |
16 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Alyson K. Fletcher | 1 | 552 | 41.10 |
Mojtaba Sahraee-Ardakan | 2 | 2 | 1.75 |
Philip Schniter | 3 | 1620 | 93.74 |
Sundeep Rangan | 4 | 3101 | 163.90 |