3 looses -> loses

In numerical mathematics there is a recent new grand theme called randomized numerical linear algebra (RandNLA). One example (probably even a paradigm) is the "randomized range finder" from the paper "Finding structure with randomness". In a nutshell, you hit a (probably very large) matrix $A$ from the right with a random matrix $\Omega$ (which should be a short matrix) and then use a traditional numerical algorithm to find an orthonormal base of the range of $A\Omega$. By hitting the matrix from the right, one can reduce the number of columns of the matrix and hence, the potential computational effort can be reduced. On the other hand, one looses loses some dimensions of the range of the matrix but one hopes that, due to the randomization, the most important dimensions are kept.

The general idea is that in most cases the interesting quantities are not such "high-dimensional" as they look at first glance. In the case of a high dimensional range of a matrix $A$, it may be that the "usual element" $Ax$ lives in a space of lower dimension.

Interesting questions in this area include: What guarantees can be given for the output of a randomized algorithm? To what extend does the distribution from which the random object in the algorithm is drawn influence the quality of the output? Under what circumstances does randomization pay off (e.g. in terms of computational effort or storage)?

2 Extended description.

In numerical mathematics there is a recent new grand theme called randomized numerical linear algebra (RandNLA). One example (probably even a paradigm) is the "randomized range finder" from the paper "Finding structure with randomness". In a nutshell, you hit a (probably very large) matrix $A$ from the right with a random matrix $\Omega$ (which should be a short matrix) and then use a traditional numerical algorithm to find an orthonormal base of the range of $A\Omega$.

This By hitting the matrix from the right, one can reduce the number of columns of the matrix and hence, the potential computational effort can be reduced. On the other hand, one looses some dimensions of the range of the matrix but one hopes that, due to the randomization, the most important dimensions are kept.

The general idea is that in most cases the interesting quantities are not such "high-dimensional" as they look at first glance. In the case of a high dimensional range of a matrix $A$, it may be that the "usual element" $Ax$ lives in a space of lower dimension.

Interesting questions in this area include: What guarantees can be given for the output of a randomized algorithm? To what extend does the distribution from which the random object in the algorithm is drawn influence the quality of the output? Under what circumstances does randomization pay off (e.g. in terms of computational effort or storage)?

In numerical mathematics there is a recent new grand theme called randomized numerical linear algebra (RandNLA). One example (probably even a paradigm) is the "randomized range finder" from the paper "Finding structure with randomness". In a nutshell, you hit a (probably very large) matrix $A$ from the right with a random matrix $\Omega$ (which should be a short matrix) and then use a traditional numerical algorithm to find an orthonormal base of the range of $A\Omega$.