Consistent parameter estimation for Lasso and approximate message passing (Q5916043)

One of the regularization methods for linear models is LASSO. LASSO depends on a tuning parameter \(\lambda\); for the computation of the LASSO estimate one has to solve an optimization problem. Approximate message passing (AMP) is an iterative algorithm for finding the solution of this problem. In the present paper a linear model in which the input variables and the noise terms are i.i.d. zero mean Gaussian variables and investigate the choice of \(\lambda\) and the choice of a threshold parameter for AMP. In difference to well-known methods for choosing the regularization parameter for LASSO, as for example cross validation, the proposed approach is based on the asymptotic behavior of the estimates, that is, the behavior for \(n\to\infty\) and \(p\to\infty\) while \(n/p\to \delta\), where \(n\) is the sample size, \(p\) is the dimension of the underlying parameter vector and \(\delta\) is a fixed number. The authors define an asymptotically optimal threshold parameter for AMP and present a consistent estimator of this optimal parameter. The asymptotically optimal regularization parameter for LASSO is defined as minimizer of almost sure limit of the mean square error of the estimator. Using the connection between the estimates of the optimally-tuned AMP and the solution of LASSO a consistent estimator for the optimal regularization parameter for LASSO is derived. As by-product several interesting properties of the solution paths of LASSO and AMP are given, for example the quasi-convexity of the mean square error of the LASSO (as a function of \(\lambda\)) and the dependence of the size of the active set on the regularization parameter.