  We propose a probabilistic way for reducing the cost of classical
projection-based model order reduction methods for parameter-dependent linear
equations. A reduced order model is here approximated from its random sketch,
which is a set of low-dimensional random projections of the reduced
approximation space and the spaces of associated residuals. This approach
exploits the fact that the residuals associated with approximations in
low-dimensional spaces are also contained in low-dimensional spaces. We provide
conditions on the dimension of the random sketch for the resulting reduced
order model to be quasi-optimal with high probability. Our approach can be used
for reducing both complexity and memory requirements. The provided algorithms
are well suited for any modern computational environment. Major operations,
except solving linear systems of equations, are embarrassingly parallel. Our
version of proper orthogonal decomposition can be computed on multiple
workstations with a communication cost independent of the dimension of the full
order model. The reduced order model can even be constructed in a so-called
streaming environment, i.e., under extreme memory constraints. In addition, we
provide an efficient way for estimating the error of the reduced order model,
which is not only more efficient than the classical approach but is also less
sensitive to round-off errors. Finally, the methodology is validated on
benchmark problems.
