  An algorithmic limit of compressed sensing or related variable-selection
problems is analytically evaluated when a design matrix is given by an
overcomplete random matrix. The replica method from statistical mechanics is
employed to derive the result. The analysis is conducted through evaluation of
the entropy, an exponential rate of the number of combinations of variables
giving a specific value of fit error to given data which is assumed to be
generated from a linear process using the design matrix. This yields the
typical achievable limit of the fit error when solving a representative
$\ell_0$ problem and includes the presence of unfavourable phase transitions
preventing local search algorithms from reaching the minimum-error
configuration. The associated phase diagrams are presented. A noteworthy
outcome of the phase diagrams is that there exists a wide parameter region
where any phase transition is absent from the high temperature to the lowest
temperature at which the minimum-error configuration or the ground state is
reached. This implies that certain local search algorithms can find the ground
state with moderate computational costs in that region. Another noteworthy
result is the presence of the random first-order transition in the strong noise
case. The theoretical evaluation of the entropy is confirmed by extensive
numerical methods using the exchange Monte Carlo and the multi-histogram
methods. Another numerical test based on a metaheuristic optimisation algorithm
called simulated annealing is conducted, which well supports the theoretical
predictions on the local search algorithms. In the successful region with no
phase transition, the computational cost of the simulated annealing to reach
the ground state is estimated as the third order polynomial of the model
dimensionality.
