LowerBoundsonRandomlyPreconditionedLasso viaRobustSparseDesigns

However, this lower bound only holds against deterministic preconditioners, and in many contexts randomization is crucial to the success of preconditioners. We prove a stronger lower bound that rules out randomized preconditioners.