Fast Debiasing of the LASSO Estimator

In high-dimensional sparse regression, the textscLasso estimator offers excellent theoretical guarantees but is well-known to produce biased estimates. To address this, citeJavanmard2014 introduced a method to ``debias" the textscLasso estimates for a random sub-Gaussian sensing matrix boldsymbolA. Their approach relies on computing an ``approximate inverse" boldsymbolM of the matrix boldsymbolA^top boldsymbolA/n by solving a convex optimization problem. This matrix boldsymbolM plays a critical role in mitigating bias and allowing for construction of confidence intervals using the debiased textscLasso estimates. However the computation of boldsymbolM is expensive in practice as it requires iterative optimization. In the presented work, we re-parameterize the optimization problem to compute a ``debiasing matrix" boldsymbolW := boldsymbolAMtop directly, rather than the approximate inverse boldsymbolM. This reformulation retains the theoretical guarantees of the debiased textscLasso estimates, as they depend on the product boldsymbolAMtop rather than on boldsymbolM alone. Notably, we provide a simple, computationally efficient, closed-form solution for boldsymbolW under similar conditions for the sensing matrix boldsymbolA used in the original debiasing formulation, with an additional condition that the elements of every row of boldsymbolA have uncorrelated entries. Also, the optimization problem based on boldsymbolW guarantees a unique optimal solution, unlike the original formulation based on boldsymbolM. We verify our main result with numerical simulations.