  We theoretically investigate the performance of $\ell_{1}$-regularized linear
regression ($\ell_1$-LinR) for the problem of Ising model selection using the
replica method from statistical mechanics. The regular random graph is
considered under paramagnetic assumption. Our results show that despite model
misspecification, the $\ell_1$-LinR estimator can successfully recover the
graph structure of the Ising model with $N$ variables using
$M=\mathcal{O}\left(\log N\right)$ samples, which is of the same order as that
of $\ell_{1}$-regularized logistic regression. Moreover, we provide a
computationally efficient method to accurately predict the non-asymptotic
performance of the $\ell_1$-LinR estimator with moderate $M$ and $N$.
Simulations show an excellent agreement between theoretical predictions and
experimental results, which supports our findings.
