The talk describes a set of recently developed randomized algorithms for computing a data sparse representation of a rank structured matrix (such as an H-matrix, or an HSS matrix). The algorithms are black box in the sense that they interact with the matrix to be compressed only through its action on vectors, making them ideal for tasks such as forming Schur complements or matrix matrix multiplication. In situations where the operator to be compressed (and its transpose) can be applied in O(N) operations, the compression as a whole has linear complexity as well, in many environments. Of particular interest is a recent technique that simultaneously both compresses and factorizes an H-matrix with a strong admissibility criterion.