Fast Debiasing of the LASSO Estimator

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