Compressed Sensing with Upscaled Vector Approximate Message Passing

Nikolai Skuratovs, Michael E. Davies

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

The Recently proposed Vector Approximate Message
Passing (VAMP) algorithm demonstrates a great reconstruction
potential at solving compressed sensing related linear
inverse problems. VAMP provides high per-iteration improvement,
can utilize powerful denoisers like BM3D, has rigorously
defined dynamics and is able to recover signals measured by
highly undersampled and ill-conditioned linear operators. Yet,
its applicability is limited to relatively small problem sizes due
to the necessity to compute the expensive LMMSE estimator at
each iteration. In this work we consider the problem of upscaling
VAMP by utilizing Conjugate Gradient (CG) to approximate the
intractable LMMSE estimator. We propose a rigorous method
for correcting and tuning CG withing CG-VAMP to achieve
a stable and efficient reconstruction. To further improve the
performance of CG-VAMP, we design a warm-starting scheme
for CG and develop theoretical models for the Onsager correction
and the State Evolution of Warm-Started CG-VAMP (WS-CGVAMP).
Additionally, we develop robust and accurate methods
for implementing the WS-CG-VAMP algorithm. The numerical
experiments on large-scale image reconstruction problems
demonstrate that WS-CG-VAMP requires much fewer CG iterations
compared to CG-VAMP to achieve the same or superior
level of reconstruction.
Original languageEnglish
Pages (from-to)4818-4836
JournalIEEE Transactions on Information Theory
Issue number7
Early online date8 Mar 2022
Publication statusPublished - 1 Jul 2022

Keywords / Materials (for Non-textual outputs)

  • warm-starting
  • Inverse problems
  • Heuristic algorithms
  • conjugate gradient
  • Approximation algorithms
  • expectation propagation
  • Covariance matrices
  • Compressed sensing
  • Image reconstruction
  • Tuning
  • vector approximate message passing


Dive into the research topics of 'Compressed Sensing with Upscaled Vector Approximate Message Passing'. Together they form a unique fingerprint.

Cite this