Total variation (TV) regularization is popular in image restoration and
reconstruction due to its ability to preserve image edges. To date, most
research activities on TV models concentrate on image restoration from blurry
and noisy observations, while discussions on image reconstruction from random
projections are relatively fewer. In this paper, we propose, analyze, and test
a fast alternating minimization algorithm for image reconstruction from random
projections via solving a TV regularized least-squares problem. The
per-iteration cost of the proposed algorithm involves a linear time shrinkage
operation, two matrix-vector multiplications and two fast Fourier transforms.
Convergence, certain finite convergence and $q$-linear convergence results are
established, which indicate that the asymptotic convergence speed of the
proposed algorithm depends on the spectral radii of certain submatrix.
Moreover, to speed up convergence and enhance robustness, we suggest an
accelerated scheme based on an inexact alternating direction method. We present
experimental results to compare with an existing algorithm, which indicate that
the proposed algorithm is stable, efficient and competitive with TwIST
\cite{TWIST} -- a state-of-the art algorithm for solving TV regularization
problems.