  A common sparse linear regression formulation is the l1 regularized least
squares, which is also known as least absolute shrinkage and selection operator
(LASSO). Approximate message passing (AMP) has been proved to asymptotically
achieve the LASSO solution when the regression matrix has independent and
identically distributed (i.i.d.) Gaussian entries in the sense that the
averaged per-coordinate l2 distance between the AMP iterates and the LASSO
solution vanishes as the signal dimension goes to infinity before the iteration
number. However, in finite dimensional settings, characterization of AMP
iterates in the limit of large iteration number has not been established. In
this work, we propose an AMP variant by including a parameter that depends on
the largest singular value of the regression matrix. The proposed algorithm can
also be considered as a primal dual hybrid gradient algorithm with adaptive
stepsizes. We show that whenever the AMP variant converges, it converges to the
LASSO solution for arbitrary finite dimensional regression matrices. Moreover,
we show that the AMP variant is locally stable around the LASSO solution under
the condition that the LASSO solution is unique and that the regression matrix
is drawn from a continuous distribution. Our local stability result implies
that in the special case where the regression matrix is large and has i.i.d.
random entries, the original AMP, which is a special case of the proposed AMP
variant, is locally stable around the LASSO solution.
