We have found that approximation based on the truncated singular value decomposition provides an effective trade-off of time for space.
we compute X T X ≈ Lower truncation levels are less accurate, but are faster and require less space: for K singular values, the storage cost is O(KP ), instead of O(P 2 ); the time cost increases by a factor of K. This approximation was not necessary in the experiments presented here, although we have found that it performs well as long as the regularizer is not too close to zero.