  We propose a systematic method for constructing a sparse data reconstruction
algorithm in compressed sensing at a relatively low computational cost for
general observation matrix. It is known that the cost of l1-norm minimization
using a standard linear programming algorithm is O(N^3). We show that this cost
can be reduced to O(N^2) by applying the approach of posterior maximization.
Furthermore, in principle, the algorithm from our approach is expected to
achieve the widest successful reconstruction region, which is evaluated from
theoretical argument. We also discuss the relation between the belief
propagation-based reconstruction algorithm introduced in preceding works and
our approach.
