Summary: An established way to tackle model nonlinearities in projection-based model reduction is via relying on partial information. This idea is shared by the methods of gappy proper orthogonal decomposition (POD), missing point estimation (MPE), masked projection, hyper reduction, and the (discrete) empirical interpolation method (DEIM). The selected indices of the partial information components are often referred to as “magic points.” The original contribution of the work at hand is a novel randomized greedy magic point selection. It is known that the greedy method is associated with minimizing the norm of an oblique projection operator, which, in turn, is associated with solving a sequence of rank-one SVD update problems. We propose simplification measures so that the resulting greedy point selection has the following main features: (1) The inherent rank-one SVD update problem is tackled in a way, such that its dimension does not grow with the number of selected magic points. (2) The approach is online efficient in the sense that the computational costs are independent from the dimension of the full-scale model. To the best of our knowledge, this is the first greedy magic point selection that features this property. We illustrate the findings by means of numerical examples. We find that the computational cost of the proposed method is orders of magnitude lower than that of its deterministic counterpart. Nevertheless, the prediction accuracy is just as good if not better. When compared to a state-of-the-art randomized method based on leverage scores, the randomized greedy method outperforms its competitor.