Alternating algorithms for total variation image reconstruction from random projections

Yunhai Xiao*, Junfeng Yang, Xiaoming YUAN

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

55 Citations (Scopus)


Total variation (TV) regularization is popular in image reconstruction due to its edgepreserving property. In this paper, we extend the alternating minimization algorithm recently proposed in [37] to the case of recovering images from random projections. Specifically, we propose to solve the TV regularized least squares problem by alternating minimization algorithms based on the classical quadratic penalty technique and alternating minimization of the augmented Lagrangian function. The per-iteration cost of the proposed algorithms is dominated by two matrixvector multiplications and two fast Fourier transforms. Convergence results, including finite convergence of certain variables and q-linear convergence rate, are established for the quadratic penalty method. Furthermore, we compare numerically the new algorithms with some state-of-the-art algorithms. Our experimental results indicate that the new algorithms are stable, efficient and competitive with the compared ones.

Original languageEnglish
Pages (from-to)547-563
Number of pages17
JournalInverse Problems and Imaging
Issue number3
Publication statusPublished - Aug 2012

Scopus Subject Areas

  • Analysis
  • Modelling and Simulation
  • Discrete Mathematics and Combinatorics
  • Control and Optimization

User-Defined Keywords

  • Alternating direction method
  • Image reconstruction
  • Quadratic penalty
  • Random projection
  • Total variation


Dive into the research topics of 'Alternating algorithms for total variation image reconstruction from random projections'. Together they form a unique fingerprint.

Cite this