With suitable definitions of the mappings \(f_t(\cdot )\) , the formulation in (REF ) includes many well-known algorithms as its special cases. A classical example is to use iterative methods [1]} to compute the extremal eigenvalues/eigenvectors of a (spiked) random matrix [2]}, [3]}. Other examples include approximate message passing on dense random graphs [4]}, [5]}, [6]}, [7]}, [8]}, and gradient descent algorithms for solving learning and estimation problems with random design [9]}, [10]}. In this paper, we show that all of these algorithms can be simulated by an efficient matrix-free scheme, if the random matrix \(Q\)  is drawn from an ensemble with translation-invariant properties. Examples of such ensembles include the i.i.d. Gaussian (i.e. the rectangular Ginibre) ensemble, the Haar-distributed random orthogonal ensemble, the Gaussian orthogonal ensemble, and their complex-valued counterparts.
