  A methodology for using random sketching in the context of model order
reduction for high-dimensional parameter-dependent systems of equations was
introduced in [Balabanov and Nouy 2019, Part I]. Following this framework, we
here construct a reduced model from a small, efficiently computable random
object called a sketch of a reduced model, using minimal residual methods. We
introduce a sketched version of the minimal residual based projection as well
as a novel nonlinear approximation method, where for each parameter value, the
solution is approximated by minimal residual projection onto a subspace spanned
by several vectors picked (online) from a dictionary of candidate basis
vectors. It is shown that random sketching technique can improve not only
efficiency but also numerical stability. A rigorous analysis of the conditions
on the random sketch required to obtain a given accuracy is presented. These
conditions may be ensured a priori with high probability by considering for the
sketching matrix an oblivious embedding of sufficiently large size.
Furthermore, a simple and reliable procedure for a posteriori verification of
the quality of the sketch is provided. This approach can be used for
certification of the approximation as well as for adaptive selection of the
size of the random sketching matrix.
