The basic idea of the HD algorithm follows the so-called principle of deferred decisions [1]}. Intuitively, each iteration of (REF ) only probes \(Q\)  in a one-dimensional space spanned by \(x_t\) . Thus, if the total number of iterations \(T \ll n\) , we only need to expose the randomness of \(Q\)  over a few low-dimensional subspaces. It is then clearly wasteful to fix and store in memory the full matrix in advance. The situation is analogous to that of simulating a simple random walk for \(T\)  steps. We can let the random choices gradually unfold with the progress of the walk, fixing only the randomness that must be revealed at any given step. The challenge in our problem though is that the dynamics in (REF ) can create a complicated dependence structure between the random matrix \(Q\)  and the iteration vectors \(x_t, x_{t-1} \ldots , x_0\) . Nevertheless, we show that this dependence structure can be exactly accounted for by an adaptive and recursive construction of (random) Householder reflectors [2]}, [3]} which exploit the inherent group symmetry of the matrix ensembles.
